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