Zu Hanser-Fachbuch.de
Warenkorb
Peter Tittmann
Graphentheorie
Eine anwendungsorientierte Einführung
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
© 2009-2024 ciando GmbH