Fundamente der Graphentheorie

1 Zusammenhang und Abstand.- 1.1 Graphen und Digraphen.- 1.2 Wege, Kreise und Zusammenhang.- 1.3 Abstandsmaße.- 1.4 Bewertete Graphen.- 1.5 Starker Zusammenhang.- 1.6 Aufgaben.- 2 Wälder, Kreise und Gerüste.- 2.1 Bäume, Wälder und Kreise.- 2.2 Gerüste.- 2.3 Minimalgerüste.- 2.4 Aufgaben.- 3 Eulersche Graphen.- 3.1 Das Königsberger Brückenproblem.- 3.2 Gute Ecken in Eulerschen Graphen.- 3.3 Eulersche Digraphen.- 3.4 Das chinesische Briefträgerproblem.- 3.5 Aufgaben.- 4 Hamiltonsche Graphen.- 4.1 Notwendige Bedingungen für Hamiltonsche Graphen.- 4.2 Hinreichende Bedingungen für Hamiltonsche Graphen.- 4.3 Panzyklische Graphen.- 4.4 Aufgaben.- 5 Turniertheorie.- 5.1 Turniere.- 5.2 Multipartite Turniere.- 5.3 Aufgaben.- 6 Matchingtheorie.- 6.1 Gesättigte und maximale Matchings.- 6.2 Matchings in bipartiten Graphen.- 6.3 Matching-Algorithmen.- 6.4 Aufgaben.- 7 Faktortheorie.- 7.1 Der 1-Faktorsatz von Tutte.- 7.2 Das f-Faktorproblem.- 7.3 Reguläre Faktoren in regulären Graphen.- 7.4 Fastreguläre Faktoren.- 7.5 Gradsequenzen.- 7.6 Aufgaben.- 8 Blöcke, Line-Graphen und Graphenoperationen.- 8.1 Schnittecken und Blöcke.- 8.2 Line-Graphen.- 8.3 Graphenoperationen.- 8.4 Aufgaben.- 9 Unabhängige Mengen und Cliquen.- 9.1 Unabhängige Mengen.- 9.2 Berechnung minimaler Überdeckungen in speziellen Graphen.- 9.3 Perfekte Graphen.- 9.4 Der Satz von Turân.- 9.5 Aufgaben.- 10 Dominanz und Irredundanz.- 10.1 Abschätzungen der Dominanzzahl.- 10.2 Graphenparameter im Vergleich.- 10.3 Bestimmung minimaler Dominanzmengen in Blockgraphen.- 10.4 p-Dominanzmengen.- 10.5 Irredundanzmengen.- 10.6 Aufgaben.- 11 Planare Graphen.- 11.1 Die Eulersche Polyederformel.- 11.2 Der Fünffarbensatz.- 11.3 Der Satz von Kuratowski.- 11.4 Aufgaben.- 12 Eckenfärbung.- 12.1 Die chromatische Zahl.- 12.2 Die (pseudo-) achromatische Zahl.- 12.3 Chromatische Polynome.- 12.4 Aufgaben.- 13 Kanten- und Totalfärbung.- 13.1 Der chromatische Index.- 13.2 Kritische Graphen.- 13.3 Klassifizierung.- 13.4 Totalfärbung.- 13.5 Aufgaben.- 14 Mehrfacher Zusammenhang.- 14.1 Ecken- und Kantenzusammenhang.- 14.2 Mehrfacher Bogenzusammenhang.- 14.3 Die Mengerschen Sätze.- 14.4 Unabhängige Mengen und Hamiltonkreise.- 14.5 Aufgaben.- 15 Netzwerke.- 15.1 Die Theorie von Ford-Fulkerson.- 15.2 Algorithmus von Edmonds-Karp.- 15.3 Anwendungen der Netzwerktheorie.- 16 Ramsey-Theorie.- 16.1 Die klassischen Ramsey-Zahlen.- 16:2 Verallgemeinerte Ramsey-Zahlen.- 16.3 Ramsey-Zahlen von Bäumen.- 17 Lokal semi-vollständige Digraphen.- 17.1 Zwei Struktursätze.- 17.2 Ringförmige lokal semi-vollständige Digraphen.- 17.3 Panzyklische lokal semi-vollständige Digraphen.- Symbolverzeichnis.- Stichwortverzeichnis.... Mehr