Eines der größten Probleme der Graphentheorie ist das (Ecken)-Färbungsproblem. Mathematiker haben großes Interesse daran, Erkenntnisse für die sogenannte chromatische Zahl (G) eines Graphen zu erzielen. Eine der wohl bekanntesten und plausibelsten Abschätzungen besagt, dass wir mindestens die gleiche Anzahl an Farben benötigen, wie wir Knoten in der größtmöglichen Clique des zu färbenden Graphen haben. Nehmen wir nun einmal an, dass uns die chromatische Zahl eines Graphen bereits vorliegt. Die Frage, die sich nun stellt ist: In wie weit kann man dadurch Aussagen über die im Graphen enthaltenen Cliquen machen? Diese und andere Fragen stellte sich der Mathematiker Hugo Hadwiger Mitte des 20. Jahrhunderts und präsentierte sie in Form einer Vermutung der mathematischen Öffentlichkeit. Bis heute gibt es keinen vollständig erbrachten Beweis für die allgemeine Gültigkeit der Vermutung. Dennoch gibt es bis heute eine hohe Zahl an Resultaten bezüglich der Vermutung, die bewiesen werden konnten. Eines dieser Ergebnisse wollen wir in dieser Arbeit behandeln: den Beweis von Hadwigers Vermutung für Kantengraphen.
Inhaltsverzeichnis
1 Einleitung
1.1 Grundlagen
1.2 Die Vermutung
2 Vorbereitungen
2.1 Mengers Satz
2.2 Vizings Adjazenz-Lemma
3 Der Beweis für Kantengraphen
Zielsetzung & Themen
Die Arbeit befasst sich mit der Hadwiger-Vermutung, einer zentralen Fragestellung der Graphentheorie, die den Zusammenhang zwischen der chromatischen Zahl eines Graphen und dessen Minorstruktur untersucht. Das primäre Ziel ist es, den Beweis von Reed und Seymour für die Gültigkeit dieser Vermutung spezifisch für die Klasse der Kantengraphen detailliert darzulegen und mathematisch zu erläutern.
- Grundlagen der Graphentheorie und Definition der Hadwiger-Vermutung
- Einführung in die färbungstheoretischen Konzepte von Vadim G. Vizing
- Detaillierte Analyse des Vizing-Fächers als methodisches Hilfsmittel
- Herleitung und Beweis der Hadwiger-Vermutung für Kantengraphen nach Reed und Seymour
- Anwendung des Satzes von Menger im Kontext der Graphenpartitionierung
Auszug aus dem Buch
1.2 Die Vermutung
Betrachten wir noch einmal die Abschätzung χ(G) ≥ ω(G) aus der Einleitung. Wir fragen uns: Wie gut ist diese Schranke? Hat ein Graph mit niedriger Clique-Zahl auch eine niedrige chromatische Zahl? Leider müssen wir die Frage verneinen. Mycielski [13] hat beispielsweise gezeigt, dass Graphen G mit beliebig großer chromatischer Zahl χ(G) existieren, die nicht einmal Dreiecke besitzen, für die also ω(G) = 2 ist. Und dennoch hat man das Gefühl, dass ein n-chromatischer Graph, wenn er schon keinen Untergraphen Kn enthält, doch einen Untergraphen enthalten muss, der in einem gewissen Sinne die Struktur des vollständigen Graphen Kn widerspiegelt. Genau das ist der Inhalt der berühmten Vermutung, die Hadwiger 1943 ausgesprochen hat.
Vermutung (Hadwiger, 1943). Für jeden einfachen, endlichen Graphen G = (V, E) und für alle natürlichen Zahlen n gilt: χ(G) ≥ n ⇒ Kn ≺ G.
Hierbei bezeichnen wir den Graphen Kn als Minor eines Graphen G, kurz Kn ≺ G, wenn wir Kn durch Kantenkontraktion und durch das Weglassen von Kanten und Knoten aus G gewinnen lassen. Kn bezeichnet hierbei den vollständigen Graphen mit n Knoten. Unter Kantenkontraktion verstehen wir dabei die Entfernung einer Kante e aus einem Graphen G, indem die beiden anliegenden Knoten zu einem neuen Knoten w vereinigt werden.
Zusammenfassung der Kapitel
1 Einleitung: Dieses Kapitel führt in das Färbungsproblem von Graphen ein und erläutert die Hadwiger-Vermutung sowie die Bedeutung von Kantengraphen im Kontext der graphentheoretischen Forschung.
2 Vorbereitungen: Hier werden notwendige mathematische Grundlagen, insbesondere Mengers Satz und Vizings Adjazenz-Lemma, definiert und bewiesen, die für das Verständnis des Beweises im Hauptteil essenziell sind.
3 Der Beweis für Kantengraphen: Das abschließende Kapitel präsentiert den Beweis von Reed und Seymour, der zeigt, dass die Hadwiger-Vermutung für die Klasse der Kantengraphen korrekt ist, indem die Existenz spezifischer Minorstrukturen nachgewiesen wird.
Schlüsselwörter
Graphentheorie, Hadwiger-Vermutung, Kantengraphen, chromatische Zahl, Minor, Kantenkontraktion, Vizing-Fächer, Mengers Satz, Knotenfärbung, Kantenfärbung, vollständiger Graph, induktiver Beweis, Graphenpartitionierung, Färbungsproblem, Kombinatorik.
Häufig gestellte Fragen
Worum geht es in der Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit der mathematischen Untersuchung der Hadwiger-Vermutung in der Graphentheorie und deren spezieller Gültigkeit für die Klasse der Kantengraphen.
Was sind die zentralen Themenfelder?
Die Schwerpunkte liegen auf der Graphenfärbung, dem Minor-Konzept, der Anwendung des Satzes von Menger sowie den Färbungsresultaten von Vizing.
Was ist das primäre Ziel der Arbeit?
Das Ziel ist die präzise Darstellung und Nachvollziehbarkeit des Beweises von Reed und Seymour zur Hadwiger-Vermutung für Kantengraphen.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt mathematische Beweisführungen, insbesondere Induktionsbeweise über die Anzahl der Knoten und Kanten eines Graphen, sowie strukturelle Analysen von Graphenpartitionen.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in theoretische Vorbereitungen, wie das Adjazenz-Lemma nach Vizing, und den eigentlichen Beweisschritt für Kantengraphen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind insbesondere Hadwiger-Vermutung, Minor, Kantengraph, chromatische Zahl und Vizing-Fächer.
Was ist die Bedeutung eines Vizing-Fächers?
Der Vizing-Fächer dient als methodisches Konstrukt, um im Beweis Aussagen über die Verfügbarkeit von Farben an Knoten und die Struktur von Kantenfärbungen zu treffen.
Warum ist die Unterscheidung der Fälle beim Induktionsschluss wichtig?
Die Fallunterscheidung ermöglicht es, je nach Beschaffenheit der Knotenanzahl oder des Knotengrades unterschiedliche strukturelle Eigenschaften des Graphen zu nutzen, um die Existenz des Minors zu belegen.
- Quote paper
- Anonym (Author), 2017, Graphentheorie. Zum Beweis von Hadwigers Vermutung für Kantengraphen, Munich, GRIN Verlag, https://www.grin.com/document/916377
