Die Arbeit befasst sich mit der fraktionalen Graphentheorie. Ausgehend von den bekannten Problemen der Graphentheorie ist der Kerngedanke in der "Fractional Graph Theory", die bestehenden (ganzzahligen) Konzepte auf reelle Werte zu erweitern.
Anhand anschaulicher Beispiele werden die graphentheoretischen Konzepte der Kantenüberdeckung und Knotenpackung auf den fraktionalen Fall übertragen. Ebenso werden fraktionale Matchings definiert und das fraktionale Hamiltonkreisproblem behandelt.
Im Kern der Arbeit steht die Untersuchung der Färbbarkeit. Eine Vermutung für eine obere Schranke der chromatischen Zahl liefert die Reed'sche Vermutung. Die ausführliche Ausarbeitung für einen Beweis der fraktionalen Version dieser Vermutung ist ein Herzstück der Arbeit. Außerdem findet sich auch der Beweis für eine noch verschärftere lokale Version dieser Schranke.
Inhaltsverzeichnis
-
- Aufbau der Arbeit
- Grundlagen und Definitionen
- Graphentheorie
- Stochastik
- Hypergraphen
- Kantenüberdeckungen
- Knotenpackungen.
- Matchings
- Fraktionale Matchings
- Allgemeines
- Fraktionales Hamiltonkreisproblem
- Das duale Problem
- Färbbarkeit
- Fraktionale Färbbarkeit
- Allgemeines
- Das duale Problem
- Reed'sche Vermutung
- Reed'sche Vermutung im fraktionalen Fall
- Das Lemma
- Folgerungen aus Lemma 5.2
- Vorüberlegungen zum Algorithmus
- Der Algorithmus
- Der Beweis
- Lokale Verschärfung
- Lokale Version von Lemma 5.2.
- Lokale Version von Gleichung (4)
- Der veränderte Algorithmus
- Der angepasste Beweis
- Reed'sche Vermutung im fraktionalen Fall
Zielsetzung und Themenschwerpunkte
Die Arbeit untersucht das Konzept der Fractional Graph Theory und erweitert bestehende (ganzzahlige) Konzepte der Graphentheorie auf reelle Werte. Dabei wird der Fokus auf die Anwendung dieser fraktionalen Ansätze auf verschiedene graphentheoretische Probleme wie Matchings und Färbbarkeit gelegt.
- Einführung und Definition der Fractional Graph Theory
- Anwendungen der Fractional Graph Theory auf Hypergraphen
- Untersuchung von fraktionalen Matchings und deren Eigenschaften
- Anwendung der Fractional Graph Theory auf das Problem der Färbbarkeit
- Beweis einer fraktionalen Version der Reed'schen Vermutung
Zusammenfassung der Kapitel
- Kapitel 1 liefert eine Einführung in die Fractional Graph Theory und beleuchtet die grundlegenden Konzepte aus der Graphentheorie und Stochastik, die in der Arbeit verwendet werden.
- Kapitel 2 untersucht fraktionale Werte für die Kantenüberdeckungszahl und die Knotenpackungszahl im Kontext von Hypergraphen.
- Kapitel 3 beschäftigt sich mit Matchings in Graphen und stellt die Konzepte der fraktionalen Matchings und des Hamiltonkreisproblems vor.
- Kapitel 4 behandelt das Thema der Färbbarkeit in Graphen und stellt die fraktionale Färbbarkeit sowie das dazugehörige duale Problem vor.
- Kapitel 5 konzentriert sich auf die Reed'sche Vermutung und bietet einen Beweis für eine fraktionale Version dieser Vermutung sowie für eine noch verschärftere lokale Variante.
Schlüsselwörter
Fraktionale Graphentheorie, Graphentheorie, Hypergraphen, Matchings, Färbbarkeit, chromatische Zahl, Reed'sche Vermutung, lineare Programmierung, Subadditivitäts-Lemma.
- Quote paper
- Andrea Müller-Mattheis (Author), 2017, Die Untersuchung der Färbbarkeit mithilfe der Fractional Graph Theory, Munich, GRIN Verlag, https://www.grin.com/document/493879
