Graphentheorie - Eine anwendungsorientierte Einführung
von: Peter Tittmann
Carl Hanser Fachbuchverlag, 2019
ISBN: 9783446465039
Sprache: Deutsch
170 Seiten, Download: 1851 KB
Format: PDF, auch als Online-Lesen
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 |
Kategorien
Kategorien
Service
Info/Kontakt