Die Graphentheorie gehört zu den Gebieten der Mathematik, die sich heute am stärksten entwickeln, zum Teil angestoßen durch Erfordernisse der Praxis, aber auch aus rein mathematischem Interesse. Dieses Kapitel der diskreten Mathematik auch Nicht-Fachleuten zugänglich zu machen, ist der Sinn dieses Buches. Es ist deshalb so geschrieben, dass es im Wesentlichen mathematisch exakt, aber auch ohne mathematische Vorkenntnisse verständlich und vor allem leicht lesbar ist. In Beispielen wird die Denkweise der modernen Mathematik nachvollziehbar und es werden auch Probleme dargestellt, die heute noch ungelöst sind. Der Autor hat wiederholt große Teile aus seinem Buch in verschiedenen Jahrgangsstufen erprobt: den Schülerinnen und Schülern hat Graphentheorie mehr Spaß gemacht als die sonstige Mathematik!
Manfred Nitzsche war Studiendirektor und Fachleiter mit den Fächern Mathematik und Physik am Beethoven-Gymnasium in Berlin.
/ AUS DEM INHALT: / / /
1 Erste Graphen 1
Das Haus von Nikolaus 1
Was ist ein Graph? 2
Auch das ist bei Graphen möglich! 3
Der Grad einer Ecke 4
Verschiedene Graphen - gleiche Graphen? 4
Zusätzliche Informationen 9
Aufgaben 10
Lösungshinweise 14
2 Über alle Brücken: Eulersche Graphen 19
Das Königsberger Brückenproblem 19
Kantenzüge 21
Eulersche Graphen 21
Welche Graphen sind eulersch? 23
Praxis: Eulersche Touren finden 26
Zwei Folgerungen 27
Besuch eines Museums 28
Domino 29
Vollständige Vielecke 30
Zusätzlicheinformationen 31
Aufgaben 31
Lösungshinweise 35
3 Durch alle Städte: Hamiltonsche Graphen 39
Reisepläne 39
Hamiltonsche Graphen 39
Hamiltonsch und eulersch 40
Hamiltonsche Kreise finden 41
Hamiltonsche Graphen neu zeichnen 42
. . . dann ist der Graph nicht hamiltonsch 43
Kreise und Wege 46
Wie viele hamiltonsche Kreise gibt es? 47
Reguläre Graphen 48
Für Schachspieler 48
Hamiltons Spiel 51
Sitzordnungen 52
Eine billige Rundreise 52
Ein vielleicht unlösbares Problem 53
Gesucht: Bäcker mit Kenntnissen in Graphentheorie 54
Zusätzliche Informationen 55
Aufgaben 56
Lösungshinweise 62
4 Mehr über Grade von Ecken 71
Tennis-Turniere 71
Das handshaking lemma 72
Ecken mit ungeradem Grad 73
Jeder gegen jeden 74
Aufgaben 74
Lösungshinweise 75
5 Bäume 79
Was ist ein Baum? 79
Wege in Bäumen 81
Wie viele Kanten hat ein Baum? 82
"Äste absägen" 83
Aufspannende Bäume 84
Labyrinthe, Irrgärten und Höhlen 86
Straßenbahnen, Fischteiche und Bindfäden 89
Eckengrade in Bäumen 90
Die billigsten Straßen 91
Der kürzeste Weg 92
Die kürzeste Tour des Briefträgers 96
Zusätzlicheinformationen 98
Aufgaben 99
Lösungshinweise 103
6 Bipartite Graphen 109
Ein Frühstücksgraph 109
Bipartite Kreise 110
Können Bäume bipartit sein? 111
Bipartite Graphen erkennen 112
Bipartite Graphen für Schachspieler 114
Fachwerkhäuser 115
Heiratsvermittlung mit Graphen 118
Der Heiratssatz 120
Eine Folgerung aus dem Heiratssatz 120
Noch einmal: Der Frühstücksgraph 122
Schwierige Briefträgertouren 122
Zusätzliche Informationen 124
Aufgaben 124
Lösungshinweise 127
7 Graphen mit Richtungen: Digraphen 133
Was ist ein Digraph? 133
Alles hat eine Richtung 134
Wer hat gewonnen? 134
Isomorphie bei Digraphen 135
Lauter Einbahnstraßen 135
Nur noch Einbahnstraßen? 136
Eulersche Digraphen 139
Hamiltonsche Digraphen 139
Turniergraphen 139
Wer ist der beste Spieler? 140
Ranking kann fragwürdig sein 143
Jeder Spieler hat gewonnen! 143
Ein klarer Fall: Es gibt ein eindeutiges Ranking 144
Könige und Vizekönige 146
Hier ist jeder ein König! 147
Wolf, Ziege und Kohlkopf 149
Das Spiel Nim 150
Umfüllaufgaben 151
Graphen für Zahlen 152
Ein Spiel, das Sie gewinnen können 153
Zusätzliche Informationen 154
Aufgaben 155
Lösungshinweise 159
8 Körper und Flächen 165
Räumliche Graphen 165
Andere Wege vom Körper zum Graphen 168
Ebene und plättbare Graphen 168
Sind alle Graphen plättbar? 169
Elektrotechniker bevorzugen plättbare Graphen 174
Ebene Graphen haben Flächen 175
Die eulersche Formel 175
Zwei neue Beweise 177
Weitere Eigenschaften von Körpern aus der Sicht der Graphentheorie . . . 178
Die platonischen Körper 179
Platonische Graphen 180
Es gibt nicht mehr als 5 platonische Graphen 181
Es gibt nur 5 platonische Körper 183
Platonische Körper auf Kugeln 184
Parkett-Fußboden 185
Zusätzliche Informationen 186
Aufgaben 188
Lösungshinweise 192
9 Farben 197
Farbige Landkarten 197
Aus Landkarten werden Graphen 198
Man kann auch Körper anmalen 200
Wir färben alle Graphen 201
Ampelschaltungen 203
Ein moderner Zoo 204
Das Problem mit den Museumswärtern 205
Die chromatische Zahl kann nicht größer sein als 207
Wie viele Farbmuster gibt es? 207
Chromatische Polynome für beliebige Graphen 211
Bekanntschaftsgraphen 215
Befreundet - bekannt - unbekannt 217
Kantenfärbung mit strengen Regeln 217
Der chromatische Index eines vollständigen Vielecks 218
Für den chromatischen Index kommen nur zwei Werte in Frage 220
Lateinische Quadrate und Sudoku-Rätsel 222
Zusätzliche Informationen 223
Aufgaben 225
Lösungshinweise 229
Was ist was? 237
Literatur 241
Stichwortverzeichnis 245