Detailansicht
Untersuchungen zur Matroidtheorie
Alexander Donà
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Lehramt Sek (AB) Unterrichtsfach Latein Unterrichtsfach Mathematik
Betreuer*in
Michael Schlosser
DOI
10.25365/thesis.77279
URN
urn:nbn:at:at-ubw:1-20512.83454.775998-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Die vorliegende Arbeit befasst sich mit den Grundlagen der Matroidtheorie und behandelt neben unterschiedlichen Axiomensystemen für Matroide ausgewählte Matroidarten, Eigenschaften und Anwendungen von Matroiden. Die erfolgreiche Lektüre der Arbeit setzt kein Vorwissen zur Matroidtheorie voraus; grundlegende Kenntnisse im Bereich der linearen Algebra und der Graphentheorie sind dem schnelleren Verständnis gewiss dienlich, werden an erforderlicher Stelle aber auch stets in knapper Form vorgestellt, sodass auch etwaige anfängliche Wissenslücken dem verständigen Lesen nicht im Wege stehen sollten. Der Aufbau der Arbeit ist folgendermaßen gewählt: Ausgehend von der Betrachtung einer Matrix werden in Kapitel 2.1.1 jedem Matroid zugrundeliegende wesentliche Eigenschaften herausgearbeitet und diese für eine erste Definition (Definition 3) von Matroiden herangezogen. In Kapitel 2.1.2 wird der Bezug zwischen Graphentheorie und Matroidtheorie deutlich gemacht und somit die Matroidtheorie als Brücke zwischen linearer Algebra und der Graphentheorie dargelegt. Über die Verallgemeinerung vertrauter Begriffe aus linearer Algebra (Basen, Rang, lineare Hülle) und Graphentheorie (Kreis) werden in den verbleibenden Abschnitten aus Kapitel 2 weitere Axiomensysteme für Matroide vorgestellt. Alle weiterführenden Kapitel dienen der Vertiefung des Verständnisses der Matroide. In Kapitel 3 bedienen wir uns der Axiomensysteme aus Kapitel 2, um daraus Matroide zu generieren, deren Ursprung nicht zwangsläufig eine Matrix oder ein Graph sein muss - und erweitern somit den Blick auf Matroide fundamental. In besonderer Weise betrachten wir in Abschnitt 3.1 uniforme Matroide und zeigen mittels des uniformen Matroids U2,4, dass nicht allen Matroiden ein Graph zugrunde liegen muss. In Abschnitt 3.2 erarbeiten wir grundlegende Gedanken zu Transversalmatroiden, die am Ende der Arbeit in einer Anwendung des Kruskal-Algorithmus’ (Abschnitt 5.2.1) nochmals aufgegriffen werden. Kapitel 4 verallgemeinert den Begriff der Dualität aus der Graphentheorie. Innerhalb der Matroidtheorie ergibt sich dadurch eine effektive Möglichkeit, aus bereits bekannten Matroiden neue Matroide zu generieren, zudem führt Dualität zu einem tieferen Verständnis der Zusammenhänge besonderer Mengen innerhalb eines Matroids. Die Krönung dieses Kapitels folgt im Beweis von Theorem 33, dass das Vámos-Matroid V8 keine ihr zugrundeliegende Matrix hat. Im letzten Kapitel der Arbeit werden schließlich ausgewählte kombinatorische Fragestellungen und Vermutungen zur Matroidtheorie genauer untersucht. Im Zuge dieser Betrachtung lernen wir ein Verfahren kennen, um die Anzahl nicht-isomorpher Matroide mit einer Grundmenge, deren Mächtigkeit 9 nicht übersteigt, zu bestimmen. Das Gros der vorgestellten Ideen besteht aus unbewiesenen Vermutungen und macht deutlich, wie viel Erforschungspotenzial die Matroidtheorie auch knapp 100 Jahre nach ihrer Entwicklung birgt. In Kapitel 5.1.3 nehmen wir auf die Heron-Rota-Welsh-Vermutung Bezug, für deren kürzlich erbrachten Beweis June Huh 2022 mit der Fields-Medaille bedacht wurde, wodurch die Matroidtheorie in den Fokus der mathematischen Fachwelt rückte. Die vorliegende Arbeit schließt mit einer genaueren Untersuchung von Greedy-Algorithmen ab und liefert in Theorem 41 die fundamentale Erkenntnis, dass Greedy-Algorithmen nur für Matroide verlässlich funktionsfähig sind. Eine Anwendungen des Greedy-Algorithmus’ innerhalb der Graphentheorie und eine Anwendung für Transversalmatroide (Kapitel 5.2.1) streichen die Faszination und Anwendungsmöglichkeiten der Matroidtheorie abschließend heraus.
Schlagwörter
Schlagwörter
(Deutsch)
Matroidtheorie Lineare Algebra Graphentheorie Greedy-Algorithmus Matroid
Autor*innen
Alexander Donà
Haupttitel (Deutsch)
Untersuchungen zur Matroidtheorie
Paralleltitel (Englisch)
Investigations into matroid theory
Publikationsjahr
2024
Umfangsangabe
84 Seiten : Illustrationen
Sprache
Deutsch
Beurteiler*in
Michael Schlosser
Klassifikationen
31 Mathematik > 31.12 Kombinatorik. Graphentheorie ,
31 Mathematik > 31.20 Algebra. Allgemeines
AC Nummer
AC17390959
Utheses ID
73854
Studienkennzahl
UA | 199 | 519 | 520 | 02