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