Graphentheorie

1 - Vorwort [Seite 6]
2 - 1 Graphen [Seite 12]
2.1 - 1.1 Definitionen [Seite 13]
2.1.1 - 1.1.1 Knotengrade [Seite 14]
2.1.2 - 1.1.2 Wege und Kreise [Seite 16]
2.1.3 - 1.1.3 Zusammenhang [Seite 16]
2.2 - 1.2 Operationen mit Graphen [Seite 17]
2.2.1 - 1.2.1 Entfernen von Knoten und Kanten [Seite 17]
2.2.2 - 1.2.2 Fusion und Kontraktion [Seite 18]
2.2.3 - 1.2.3 Bruecken und Artikulationen [Seite 19]
2.2.4 - 1.2.4 Operationen mit Graphen [Seite 20]
2.3 - 1.3 Spezielle Graphen [Seite 21]
2.3.1 - 1.3.1 Der vollständige Graph [Seite 21]
2.3.2 - 1.3.2 Weg und Kreis [Seite 22]
2.3.3 - 1.3.3 Bäume [Seite 22]
2.3.4 - 1.3.4 Bipartite Graphen [Seite 24]
2.3.5 - 1.3.5 Regulaere Graphen [Seite 25]
2.4 - 1.4 Isomorphe Graphen [Seite 26]
2.4.1 - 1.4.1 Isomorphie [Seite 26]
2.4.2 - 1.4.2 Gradfolgen [Seite 27]
2.5 - 2.4 Spannbaeume [Seite 38]
2.6 - 2.4.1 Die Anzahl der Spannbaeume [Seite 38]
3 - 2 Graphen und Matrizen [Seite 30]
3.1 - 2.1 Die Adjazenzmatrix eines Graphen [Seite 30]
3.1.1 - 2.1.1 Potenzen der Adjazenzmatrix [Seite 31]
3.1.2 - 2.1.2 Zerlegbare Matrizen [Seite 32]
3.2 - 2.2 Die Inzidenzmatrix [Seite 33]
3.2.1 - 2.2.1 Die Gradmatrix [Seite 34]
3.3 - 2.3 Abstaende in Graphen [Seite 34]
3.3.1 - 2.3.1 Radius, Durchmesser und Zentrum [Seite 35]
3.3.2 - 2.3.2 Die Abstandsmatrix [Seite 37]
3.4 - 2.4 Spannbaeume [Seite 38]
3.4.1 - 2.4.1 Die Anzahl der Spannbaeume [Seite 38]
3.4.2 - 2.4.2 Die Admittanzmatrix und der Satz von Kirchho [Seite 41]
4 - 3 Planare Graphen - die Eulersche Polyederformel [Seite 45]
4.1 - 3.1 Planare Einbettungen [Seite 45]
4.1.1 - 3.1.1 Ebene Kurven und Einbettungen [Seite 45]
4.1.2 - 3.1.2 Flaechen eines planaren Graphen [Seite 47]
4.1.3 - 3.1.3 Einbettungen auf der Kugel [Seite 47]
4.1.4 - 3.1.4 Kreuzungszahl und Dicke [Seite 48]
4.2 - 3.2 Die Eulersche Polyederformel [Seite 49]
4.2.1 - 3.2.1 Polyeder [Seite 49]
4.2.2 - 3.2.2 Die Polyederformel f?ur zusammenhaengende Graphen [Seite 50]
4.2.3 - 3.2.3 Die Polyederformel fuer nicht zusammenhaengende Graphen [Seite 52]
4.3 - 3.3 Anwendungen der Polyederformel [Seite 52]
4.3.1 - 3.3.1 Nichtplanare Graphen [Seite 52]
4.3.2 - 3.3.2 Der Satz von Kuratowski [Seite 53]
4.3.3 - 3.3.3 Maximale Kantenzahl planarer Graphen [Seite 55]
4.3.4 - 3.3.4 Knotengrade in planaren Graphen [Seite 55]
4.3.5 - 3.3.5 Platonische Koerper [Seite 56]
4.4 - 3.4 Der duale Graph [Seite 57]
5 - 4 Unabhaengige Knoten- und Kantenmengen [Seite 61]
5.1 - 4.1 Unabhaengige Knotenmengen [Seite 62]
5.1.1 - 4.1.1 Die Unabhaengigkeitszahl [Seite 62]
5.1.2 - 4.1.2 Cliquen [Seite 65]
5.1.3 - 4.1.3 Die Ueberdeckungszahl [Seite 66]
5.2 - 4.2 Matchings [Seite 67]
5.2.1 - 4.2.1 Alternierende Wege - der Satz von Berge [Seite 68]
5.2.2 - 4.2.2 Der Satz von K?onig [Seite 70]
5.3 - 4.3 Der Kantengraph [Seite 71]
5.4 - 4.4 Faktoren [Seite 73]
6 - 5 Faerbungen von Graphen [Seite 77]
6.1 - 5.1 Grundlagen [Seite 77]
6.1.1 - 5.1.1 Zulaessige Faerbungen [Seite 77]
6.1.2 - 5.1.2 Die chromatische Zahl [Seite 78]
6.1.3 - 5.1.3 Schranken fuer die chromatische Zahl [Seite 79]
6.2 - 5.2 Faerbungen von planaren Graphen [Seite 81]
6.3 - 5.3 Das chromatische Polynom [Seite 83]
6.3.1 - 5.3.1 Der vollst?andige Graph [Seite 84]
6.3.2 - 5.3.2 Der Baum [Seite 84]
6.3.3 - 5.3.3 Die Dekompositionsgleichung [Seite 84]
6.3.4 - 5.3.4 Der Kreis [Seite 86]
6.3.5 - 5.3.5 Chromatisches Polynom und chromatische Zahl [Seite 87]
6.3.6 - 5.3.6 Partitionen der Knotenmenge [Seite 87]
6.4 - 5.4 Eine Anwendung [Seite 89]
7 - 6 Der Zusammenhang von Graphen [Seite 94]
7.1 - 6.1 Der Knotenzusammenhang [Seite 94]
7.2 - 6.2 Der Kantenzusammenhang [Seite 97]
7.2.1 - 6.2.1 Schnittmengen [Seite 97]
7.2.2 - 6.2.2 Schnitte [Seite 98]
7.2.3 - 6.2.3 Die Kantenzusammenhangszahl [Seite 99]
7.2.4 - 6.2.4 Knotenzusammenhang und Kantenzusammenhang [Seite 99]
7.3 - 6.3 Trennende Knotenmengen [Seite 100]
7.3.1 - 6.3.1 Anwendung zur Berechnung der Unabhaengigkeitszahl [Seite 100]
7.3.2 - 6.3.2 Ein Berechnungsbeispiel [Seite 101]
7.3.3 - 6.3.3 Die Berechnung des chromatischen Polynoms [Seite 102]
7.4 - 6.4 Partielle k-Baeume [Seite 104]
7.4.1 - 6.4.1 k-Baeume [Seite 104]
7.4.2 - 6.4.2 Partielle k-Baeume [Seite 105]
7.4.3 - 6.4.3 Serien-Parallel-Graphen [Seite 106]
8 - 7 Baeume [Seite 109]
8.1 - 7.1 Eigenschaften von Baeumen [Seite 109]
8.1.1 - 7.1.1 Die Anzahl der Baeume [Seite 110]
8.1.2 - 7.1.2 Der Pruefercode und der Satz von Cayley [Seite 111]
8.1.3 - 7.1.3 Isomorphieklassen von B?aumen [Seite 113]
8.2 - 7.2 Wurzelbaeume [Seite 113]
8.3 - 7.3 Binaere Baeume [Seite 116]
9 - 8 Kreise [Seite 120]
9.1 - 8.1 Kreise in Graphen [Seite 120]
9.1.1 - 8.1.1 Taille und Umfang [Seite 121]
9.1.2 - 8.1.2 Basiskreise [Seite 122]
9.2 - 8.2 Hamiltonkreise [Seite 123]
9.3 - 8.3 Eulerkreise [Seite 126]
9.4 - 9 Gerichtete Graphen [Seite 130]
9.4.1 - 9.1 Definitionen und Eigenschaften gerichteterGraphen [Seite 130]
9.4.1.1 - 9.1.1 Wege und Erreichbarkeit [Seite 131]
9.4.1.2 - 9.1.2 Zusammenhang und starker Zusammenhang [Seite 131]
9.4.1.3 - 9.1.3 Orientierungen [Seite 132]
9.4.1.4 - 9.1.4 Innen- und Aussengrad [Seite 133]
9.4.1.5 - 9.1.5 Quellen und Senken [Seite 134]
9.4.1.6 - 9.1.6 Vektorr?aume [Seite 135]
9.4.1.7 - 9.1.7 Kozyklen [Seite 136]
9.4.1.8 - 9.1.8 Zyklen- und Kozyklenraeume [Seite 137]
9.4.2 - 9.2 Turniere [Seite 141]
9.4.3 - 9.3 Fl?usse in Graphen [Seite 144]
10 - Loesungen [Seite 149]
11 - Literaturverzeichnis [Seite 163]
12 - Symbolverzeichnis [Seite 165]
13 - Sachwortverzeichnis [Seite 166]