Inhaltsverzeichnis

Vorwort

Vorwort

Liebe Leserin, lieber Leser!

Dies ist ein mathematisches Sachbuch. Es behandelt ein Thema der Mathematik, das Sie aus Ihrer Schulzeit wahrscheinlich nicht kennen, die Graphentheorie. Ihre Anfänge reichen zwar bis ins 18. Jahrhundert zurück, aber richtig intensiv haben sich die Mathematiker erst in den letzten Jahrzehnten mit diesem Teil der Mathematik beschäftigt. Wenn Sie dieses Buch lesen, befassen Sie sich also mit einem aktuellen Thema der Mathematik, und Sie werden auch auf Fragen stoßen, auf die heute noch niemand eine Antwort weiß.

Mathematik ist immer auch Spiel, natürlich ein Denkspiel. Dieser Aspekt kommt hier nicht zu kurz. Aber manches, was zunächst wie Spielerei aussieht, kann man nutzbringend verwerten, wie Sie sehen werden. Auch das Umgekehrte ist wahr: Viele Teile der Graphentheorie sind aus praktischen Bedürfnissen entstanden.

Braucht man Vorkenntnisse?

An einzelnen Stellen kommen Brüche und Klammerausdrücke vor, aber sonst brauchen Sie eigentlich keine mathematischen Vorkenntnisse. Am meisten wird bei der Untersuchung der platonischen Körper gerechnet, aber auch nur mit Brüchen, außerdem gibt es bei den chromatischen Polynomen einiges zu rechnen. Man kann diese Abschnitte auslassen und versteht den Rest trotzdem.

Wie liest man dieses Buch?

Im 1. Kapitel werden die grundlegenden Begriffe eingeführt, die später überall vorkommen. Damit sollten Sie anfangen. Danach können Sie das Buch Kapitel für Kapitel durcharbeiten. Es ist aber auch möglich in jedes andere Kapitel einzusteigen. Dabei werden Sie hin und wieder auf unbekannte Begriffe stoßen. Für diesen Fall ist die Liste der Definitionen ("Was ist was?") auf gelbem Papier am Ende des Buches gedacht.

Es darf nicht verschwiegen werden, dass jedes Mathematikbuch ein Arbeitsbuch ist. Sie sollten also bereit sein sich hin und wieder anzustrengen: Man muss nämlich die Begriffe genau kennen, um die Texte, in denen sie vorkommen, wirklich zu verstehen. Dazu dienen die Übungsaufgaben am Ende eines jeden Kapitels. Sie sollten einige von ihnen lösen. Suchen Sie sich die heraus, die Sie reizvoll finden! Lösungshinweise finden Sie jeweils nach den Aufgaben. Übrigens ist der Weg über Aufgaben und Anwendungen eine gute Möglichkeit in die Welt der Graphen einzudringen. Sie können deshalb auch versuchen, zuerst Aufgaben zu lösen und sich dann bei Bedarf die nötigen Informationen im vorangehenden Kapitel holen.

Das Wichtigste ist aber: Lassen Sie sich auf die hier vorgestellten Denkweisen ein, auch wenn es nicht immer einfach ist.

Ein Wort an die Mathe-Profis

Dies ist ein Mathematikbuch für Laien. Anders als in mathematischen Fachbüchern wird hier eher anschaulich vorgegangen. Wenn kein Fehler entstehen kann, werden manche Begriffe ohne exakte Definition benutzt, und auch die Beweise halten nicht an allen Stellen den strengen Augen eines professionellen Mathematikers stand. Das ist auch der Grund, warum ein Student, der sich von seinem Professor über Graphentheorie prüfen lassen möchte, dieses Buch gut zur Einstimmung und als Ergänzung lesen kann, sich aber dann ein richtiges Fachbuch vornehmen sollte.

Zusätzliche Informationen

Unter dieser Überschrift finden Sie am Ende der Kapitel präzisierende Hinweise. Sie sind für Leserinnen und Leser gedacht, denen die im Text angebotene Begriffsbildung oder die Beweisführung zu ungenau war. Vielleicht erhalten Sie wenigstens in einigen Punkten eine befriedigende Antwort. Aber es bleibt dabei: Lückenlose mathematische Strenge ist nicht das Ziel dieses Buchs, mathematisches Verstehen im Bereich der Graphen schon eher.

Hinweise für Lehrerinnen und Lehrer

Graphen bieten interessanten Stoff für einzelne Stunden, aber auch für längere Unterrichtseinheiten, und zwar in jeder Jahrgangsstufe, natürlich auch für Arbeitsgemeinschaften und Mathematik-Zirkel. Das Buch soll Ihnen - durch die im Vergleich zu Hochschul-Lehrbüchern vereinfachte Art der Darstellung und durch die große Zahl von Beispielen und Übungsaufgaben - die Unterrichtsvorbereitung erleichtern. Für Seminararbeiten in der Oberstufe und im Rahmen von selbstorganisiertem Lernen können sich aufgeweckte Schülerinnen und Schüler Teile von aktueller Mathematik selbst erarbeiten.

Mögliche Einstiege in das Thema können - wie in diesem Buch - bestimmte Linienzüge sein. Aber auch Probleme der Raum-Geometrie (GWE-Problem, platonische Körper) oder Färbungsaufgaben können am Anfang stehen oder auch das Einzige aus der Graphentheorie sein.

Eine Vereinfachung in der Begrifflichkeit und Formulierung mancher Sätze ergibt sich, wenn Sie das, was hier "einfacher Graph" genannt wird, als "Graph" bezeichnen. Bei Bedarf müssten Sie dann Graphen, die nicht einfach sind, "Multigraphen" nennen. Der Königsberger Brückengraph ist dann bereits ein Multigraph. Diese Alternative ist besonders dann interessant, wenn Sie nicht vorhaben, mehr als die Themen "Körper" oder "Farben" zu behandeln.

Zu den hier angebotenen Aufgaben können Sie sich leicht anspruchsvollere Alternativen ausdenken, wenn die hier angebotenen Aufgaben zu einfach erscheinen.

Das Thema ist geeignet die kreativen Fähigkeiten der Schüler zu fördern und das Problemlösen zu üben. "Zeichne Graphen mit der Eigenschaft . . .?" ist reizvoll genug und die Suche nach sämtlichen Lösungen ergibt sich oftmals von selbst. Manche Aufgaben lassen sich auch so umformulieren, dass sie offener sind und unterschiedliche Lösungen zulassen. Auch dass Schüler selbst Aufgaben erfinden, ist beim Thema "Graphentheorie" sehr gut möglich.

Im Gegensatz zum erklärenden Teil kommen in den Aufgaben viele Zählaufgaben vor. Auch hier wird die kreative Seite der Schüler angesprochen: Sie müssen selbst geeignete Zählstrategien suchen. Man kann diese kombinatorische Seite der Graphentheorie noch ausbauen.

"Graphentheorie macht mehr Spaß als Mathe", der Schüler, der das gesagt hat, hat wohl etwas nicht ganz verstanden, aber er drückt das aus, was viele Schüler im Unterricht über Graphen empfinden.

Danke!

Für geduldige fachliche Unterstützung danke ich Hans Mielke. Viele Verbesserungen von Formulierungen verdanke ich Birgit Mielke, und Reinhard Nitzsche danke ich für zahlreiche Computer-Hilfen. Viele Kolleginnen und Kollegen haben mich bei meiner Arbeit beraten und vor allem ermutigt. Dank auch an Leserinnen und Leser der 1. und 2. Auflage, die mich durch diverse Anfragen zu einigen Umformulierungen veranlasst haben, und an die Mitarbeiterinnen und Mitarbeiter des Verlags Vieweg+Teubner für vielfältige Unterstützung.

Nicht zuletzt danke ich den Schülerinnen und Schülern des Beethoven-Gymnasiums in Berlin, die - ohne es zu wissen - mir manche Anregungen für Beispiele und Formulierungen gegeben haben.

Gegenüber der 1. und 2. Auflage enthält das Buch einige Ergänzungen und zusätzliche Aufgaben.

Und jetzt viel Spaß beim Lesen in einem Kapitel der aktuellen Mathematik!

Berlin, März 2009

Manfred Nitzsche

Klappentext

Graphen für Einsteiger

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. In der dritten Auflage wurden Zeichnungen verbessert und weitere Beispiele und Aufgaben hinzugefügt.

Der Inhalt

Erste Graphen - Über alle Brücken: Eulersche Graphen - Durch alle Städte: Hamiltonsche Graphen - Mehr über Grade von Ecken - Bäume - Bipartite Graphen - Graphen mit Richtungen - Körper und Flächen - Farben

STUDIUM

Die Zielgruppen

Menschen, die wissen wollen, was Mathematiker heute machen Studierende der Mathematik, der Informatik und des Lehramts für einen ersten Einblick Lehrerinnen und Lehrer an Gymnasien (Mathematik und Informatik) Hochschullehrer, die propädeutische Schülerseminare in Mathematik durchführen Wissenschaftler aus anderen Fachgebieten, die sich einen Überblick über Graphentheorie verschaffen wollen

Schüler mit besonderem mathematischem Interesse, etwa ab Klasse 9

ISBN 978-3-8348-0813-4

www.viewegteubner.de

Register

Stichwortverzeichnis

A

Adjazenzmatrix 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

B

Bä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

C

CALEY, A. 86
Chinese Postman Problem 97
chromatisches Polynom 209-214, 224
chromatische Zahl 202-214, 223-224
chromatischen Index 218 -222

D

Digraph 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

E

ebener 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

F

Fachwerkhä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

G

Gaswerk 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

H

Hackordnung 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

I

Ikosaeder 179-180, 183-184, 226
Irrgärten 86-90
Isomorphie

- von Graphen 5, 9
- von Digraphen 135

J

Jordankurve 187

K

Kante 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

L

Label 8, 98
Labyrinth 86-89
Landkarte 197-200
lateinisches Quadrat 222
Leistungskurs 227
löschen

- Ecke 44, 55
- Kante 211-213

M

Matching 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

N

Nahverkehrsnetz 95-96
n-Eck, vollständiges 30, 35, 47-48, 74, 85-86, 189, 123, 124, 210, 215, 218-220, 224, 228
Netzwerk 154
Nikolaus, Haus von ~ 1-5, 10, 21, 33, 58, 100, 127, 156, 189, 226, 228
Nim 150

O

Oktaeder 34, 179-180, 183-184, 226

P

paar 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

Q

Quelle 155, 159

R

Radgraph 226
Ranking 143-145
Relation 154
runder Tisch 52
Rundfahrt 39, 51, 52-53
Rundgang (Museum) 28

S

Schachbrett 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

T

Tabelle 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
Turnier 7, 74, 139

U

Überfahrt-Problem 149-150
Umfüllaufgabe 151
unbekannt 217
Unterteilung 173

V

Versorgungssystem 85
vertex 9
Viereck, vollständiges 58, 110
Vierfarbensatz 200
Vizekönig 146
VIZING, V.G. 220, 229
Vokale 184

W

Wald 98
Wasserwerk 172
Watchman Problem 206
Weg 46, 81-82, 98
- gerichteter 134, 140-143
- kürzester 92-96, 123
Wohnung 33, 101
Wolf, Ziege und Kohlkopf 149
Würfel 34, 166-167, 179-180, 183-184, 188, 226
- nicht transitive 153
Würfelnetz 188

Z

Zoologischer Garten 204
zusammenziehen 212

Autor

Der Autor

Manfred Nitzsche war viele Jahre Studiendirektor und Fachleiter mit den Fächern Mathematik und Physik am Beethoven-Gymnasium in Berlin.

Reviews

"Ein recht unterhaltsames Buch rund um die Graphentheorie." Die Wurzel, 02/2006 "Der Autor war Fachleiter für Mathematik an einem Berliner Gymnasium. Er hat sein Buch für Kollegen und Schüler mit besonderem Interesse geschrieben. Es eignet sich aber auch bestens für Studierende der Mathematik (insbesondere des Lehramts) für einen ersten Einblick." PM Praxis der Mathematik in der Schule, 03/2005 "Der Gymnasiallehrer Nitzsche gibt neun ansprechende, lebendig und anschaulich gestaltete Kapitel über eulersche, hamiltonsche und bipartite Graphen, Digraphen, Farben, Körper und Flächen." ekz-Informationsdienst, 50/04