Graphentheorie (eBook)

Prof. Tittmann hält Vorlesungen zur Mathematik für Ingenieur- und Informatikstudenten an der Hochschule Mittweida.

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