Zu Hanser-Fachbuch.de
Warenkorb
Peter Tittmann
Graphentheorie
Eine anwendungsorientierte Einführung
Vorwort
6
Inhaltsverzeichnis
8
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 Brücken und Artikulationen
19
1.2.4 Operationen mit Graphen
19
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 Reguläre Graphen
25
1.4 Isomorphe Graphen
26
1.4.1 Isomorphie
26
1.4.2 Gradfolgen
27
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 Abstände in Graphen
34
2.3.1 Radius, Durchmesser und Zentrum
35
2.3.2 Die Abstandsmatrix
37
2.4 Gerüste
38
2.4.1 Die Anzahl der Gerüste
38
2.4.2 Die Admittanzmatrix und der Satz von Kirchhoff
40
3 Planare Graphen
44
3.1 Planare Einbettungen
44
3.1.1 Ebene Kurven und Einbettungen
44
3.1.2 Flächen eines planaren Graphen
46
3.1.3 Einbettungen auf der Kugel
46
3.1.4 Kreuzungszahl und Dicke
47
3.2 Die Eulersche Polyederformel
48
3.2.1 Polyeder
48
3.2.2 Die Polyederformel für zusammenhängende Graphen
49
3.2.3 Die Polyederformel für nicht zusammenhängende Graphen
51
3.3 Anwendungen der Polyederformel
51
3.3.1 Nichtplanare Graphen
51
3.3.2 Der Satz von Kuratowski
52
3.3.3 Maximale Kantenzahl planarer Graphen
54
3.3.4 Knotengrade in planaren Graphen
54
3.3.5 Platonische Körper
55
3.4 Der duale Graph
56
4 Unabhängige Knoten- und Kantenmengen
60
4.1 Unabhängige Knotenmengen
61
4.1.1 Die Unabhängigkeitszahl
61
4.1.2 Cliquen
64
4.1.3 Die Überdeckungszahl
65
4.2 Matchings
66
4.2.1 Alternierende Wege – der Satz von Berge
67
4.2.2 Der Satz von König
69
4.3 Der Kantengraph
70
4.4 Faktoren
72
5 Färbungen von Graphen
75
5.1 Grundlagen
75
5.1.1 Zulässige Färbungen
75
5.1.2 Die chromatische Zahl
76
5.1.3 Schranken für die chromatische Zahl
77
5.2 Färbungen von planaren Graphen
79
5.3 Das chromatische Polynom
81
5.3.1 Der vollständige Graph
82
5.3.2 Der Baum
82
5.3.3 Die Dekompositionsgleichung
82
5.3.4 Der Kreis
84
5.3.5 Chromatisches Polynom und chromatische Zahl
85
5.3.6 Partitionen der Knotenmenge
86
5.4 Eine Anwendung
87
6 Der Zusammenhang von Graphen
92
6.1 Der Knotenzusammenhang
92
6.2 Der Kantenzusammenhang
95
6.2.1 Schnittmengen
95
6.2.2 Schnitte
96
6.2.3 Die Kantenzusammenhangszahl
97
6.2.4 Knotenzusammenhang und Kantenzusammenhang
97
6.3 Trennende Knotenmengen
98
6.3.1 Anwendung zur Berechnung der Unabhängigkeitszahl
98
6.3.2 Ein Berechnungsbeispiel
99
6.3.3 Die Berechnung des chromatischen Polynoms
100
6.4 Partielle k-Bäume
102
6.4.1 k-Bäume
102
6.4.2 Partielle k-Bäume
103
6.4.3 Serien-Parallel-Graphen
104
7 Bäume
107
7.1 Eigenschaften von Bäumen
107
7.1.1 Die Anzahl der Bäume
108
7.1.2 Der Prüfercode und der Satz von Cayley
109
7.1.3 Isomorphieklassen von Bäumen
111
7.2 Wurzelbäume
111
7.3 Binäre Bäume
114
8 Kreise
118
8.1 Kreise in Graphen
118
8.1.1 Taille und Umfang
119
8.1.2 Basiskreise
120
8.2 Hamiltonkreise
121
8.3 Eulerkreise
124
9 Gerichtete Graphen
128
9.1 Definitionen und Eigenschaften gerichteter Graphen
128
9.1.1 Wege und Erreichbarkeit
129
9.1.2 Zusammenhang und starker Zusammenhang
129
9.1.3 Orientierungen
130
9.1.4 Innen- und Außengrad
131
9.1.5 Quellen und Senken
132
9.1.6 Vektorräume
133
9.1.7 Kozyklen
134
9.1.8 Zyklen- und Kozyklenräume
135
9.2 Turniere
139
9.3 Flüsse in Graphen
142
Lösungen
147
Literaturverzeichnis
159
Symbolverzeichnis
161
Sachwortverzeichnis
162
© 2009-2024 ciando GmbH