DeutschesFachbuch.de : Graphen für Einsteiger Rund um das Haus vom Nikolaus Von Manfred Nitzsche

INHALTSVERZEICHNIS | öffnen

Inhaltsverzeichnis
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ätzliche Informationen 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ätzliche Informationen 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
[weiter lesen]

REGISTER | öffnen

Stichwortverzeichnis
AAdjazenzmatrix 9
Algorithmus
- für chromatisches Polynom 211-214
- von Dijkstra 54, 93-96, 123
- Greedy 92, 96
- von Hierholzer 27
- von Kruskal 99
Ameise 81
Ampelschaltung 203
APPEL, K. 198
ARISTOTELES 184
Ausgangsgrad 134
Außenfläche 167
Ausstellung 28
BBäcker 54
Baukosten 92
Baum 79, 98, 111, 209
- aufspannender 84-86
- minimaler aufspannender 91-92
befreundet 217
Bekanntschaft 215
Bewertung 53
Bindfäden 89-90
Blatt 79, 90
Bogen 154
Briefträger 34, 96-98, 102, 122-123
Brötchen 54
Brücke 84, 137
CCALEY, A. 86
Chinese Postman Problem 97
chromatisches Polynom 209-214, 224
chromatische Zahl 202-214, 223-224
chromatischen Index 218 -222
DDigraph 133, 154
- eulerscher 139
- hamiltonscher 139, 144
DIJKSTRA, E.W. 96
Diktator 146
DIRAC, P. 42, 55
Dodekaeder 51, 179-180, 183-184, 226
Domino 29, 35
Duschmittel 158
Eebener Graph
Ecke 2, 9
edge 9
Einbahnstraßen 135-137
Einbettung 186
Eingangsgrad 134
elektrische Schaltpläne 134, 174
Elektrizitätswerk 172
Elemente 184
Elternsprechtag 229
EULER, L. 20
Euler-Poincaré-Charakteristik 186
eulersche Formel 175-181
eulersche Polyederformel 178, 187
FFachwerkhäuser 114-117
Fahrgastinformationssystem 95-96 färben 197, 202, 215, 217
Farbmuster 207
Fischteiche 89-90
Fläche 175-186
Flaggen 228
Fluglinien 75, 102, 117
Frühstück 109, 122
Fünfeck, vollständiges 58, 170-173, 177
GGaswerk 172
Grad 4
Graph 2, 9
- bewerteter 53, 91-98, 123, 154
- bipartiter 109, 124, 190, 202, 220-222
- ebener 168, 175-177, 186, 200- einfacher 3, 72, 202
- eulerscher 22, 31, 40, 122, 125
- gelabelter 8, 98
- gerichteter 133, 154
- GWE- 172-174, 177-178
- hamiltonscher 39, 125, 144
- kantenloser 9, 2, 211
- Petersen 13, 59, 157, 189, 227
- plättbarer 169-174, 186, 200
- platonischer 180-183- regulärer 48, 75, 127, 180
- Turnier- 139-149
- vollständiger 30
- vollständiger bipartiter 125, 171
- zusammenhängender 3, 21, 83, 137
größter gemeinsamer Teiler 153
GUAN, M. 97
HHackordnung 157
HAKEN, W. 198
HAMILTON, W.R. 40
Hamiltons Spiel 51
handshaking lemma 72-74, 178
Heiratssatz 120-122
Heiratsvermittlung 118-120
Hexaeder 183
HIERHOLZER, C.F.B. 27
Höhlen 86-89
homöomorphe Abbildung 186
IIkosaeder 179-180, 183-184, 226
Irrgärten 86-90
Isomorphie
- von Graphen 5, 9
- von Digraphen 135
JJordankurve 187
KKante 2, 9
- gerichtete 134, 154
- parallele 3
Kantenfärbung 215-222
Kantenzug 21, 28, 31, 47, 98
- geschlossener 25, 46
- gerichteter 154
Käse 60
KEPLER, J. 184
kleinstes gemeinsames Vielfaches 153
Knoten 2
Kochrezept 133
KÖNIG, D. 220-221
König 146-148
Königsberger Brückenproblem 20
Kohlenwasserstoff 80
Komponente 9
Konfliktgraph 203
Kongress 126
Kreis 46, 111-114
- gerichteter 134
- hamiltonscher 39, 41-45, 47-48, 51
KRUSKAL 99
KURATOWSKI, K. 173
LLabel 8, 98
Labyrinth 86-89
Landkarte 197-200
lateinisches Quadrat 222
Leistungskurs 227
löschen
- Ecke 44, 55
- Kante 211-213
MMatching 119-123
- maximales 120
- perfektes 120, 123, 124
Mauer 192
Maus 60
Mehrfachkanten 3
Montageanleitung 133
Mühlebrett 57, 157, 191
Müllabfuhr 98, 123
Museum 28, 205-207, 224, 228
NNahverkehrsnetz 95-96
n-Eck, vollständiges 30, 35, 47-48, 74, 85-86, 189, 123, 124, 210, 215, 218-220, 224,...
Netzwerk 154
Nikolaus, Haus von ~ 1-5, 10, 21, 33, 58, 100, 127, 156, 189, 226, 228
Nim 150
OOktaeder 34, 179-180, 183-184, 226
Ppaar 109
Paketauto 123
Parkettierung 185-186, 187
Party 75
PETERSEN, J. 13
planar 169, 187
plane 187
Planeten 184
Platine 174
platonischer Körper 179, 183-184, 226
Polyeder 166-169, 175, 201
Polygon 206, 224
Produktionsprozess 54
Pyramide 167, 179
QQuelle 155, 159
RRadgraph 226
Ranking 143-145
Relation 154
runder Tisch 52
Rundfahrt 39, 51, 52-53
Rundgang (Museum) 28
SSchachbrett 48-50, 114-115, 191
Schlinge 3
Sechseck, vollständiges 58, 123, 124, 215
Senke 155, 159
Sitzordnung 52
Springer (Schach) 50
Städtetour 39
Stadtrundfahrten 98
Stammbaum 81
stark zusammenhängend 136-137, 144
Straßenbahn 89-90
Straßendienst 34
Straßennetz 91
Sudoku 222
Sympathie 134
TTabelle 7-8, 9, 35, 156
Tagesablauf 133
Teilergraph 152-153
Teilgraph 44-46, 173
Tetraeder 179-180, 183-184, 226
Tour 21
- eulersche 21, 26, 57
- geschlossene 25
transitiv 144-145
Traveling Salesman Problem 53-54
Triangulieren 206, 224
Turm (Schach) 48-50, 114
[weiter lesen]