Skip to main content

2005 | Buch | 2. Auflage

Graphen für Einsteiger

Rund um das Haus vom Nikolaus

insite
SUCHEN

Über dieses Buch

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 I. Kapitel werden die grundlegenden Begriffe eingeruhrt, die später überall vorkommen. Damit sollten Sie anfangen. Danach können Sie das Buch Kapitel rur 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.

Inhaltsverzeichnis

Frontmatter
1. Erste Graphen
Zusammenfassung
Kinder kennen dieses Bild. Man soll es zeichnen ohne den Stift abzusetzen und ohne eine Linie doppelt zu ziehen. Wer weiß, wie es geht, fängt links unten oder rechts unten an und er kann auch meist einen Spruch dazu aufsagen, zu jedem Strich eine Silbe: “Das — ist — das — Haus — vom — Ni — ko — laus.”
Manfred Nitzsche
2. Über alle Brücken: Eulersche Graphen
Zusammenfassung
In Königsberg (heute Kaliningrad) gibt es einen Fluss, den Pregel, der sich im Stadtgebiet mehrfach teilt. Im 18. Jahrhundert sah der Stadtplan ungefähr so aus, wobei hier nur die Stadtteile und die Brücken eingezeichnet sind.
Manfred Nitzsche
3. Durch alle Städte: Hamiltonsche Graphen
Zusammenfassung
Eine Gruppe Jugendlicher möchte mit einem Euro-Ticket eine Städtetour mit der Bahn machen. Die Fahrt soll in Berlin beginnen, durch alle in dem Netzplan eingezeichneten Städte führen, aber durch jede nur einmal, und wieder in Berlin enden. Es kommt darauf an, dass jede Stadt genau einmal besucht wird, aber nicht, dass jede Strecke abgefahren wird. Die gesuchte Route muss also keine eulersche Tour sein!
Manfred Nitzsche
4. Mehr über Grade von Ecken
Zusammenfassung
Bei einem Tennis-Turnier ist geplant, dass jeder gegen jeden spielt. Aber das Turnier ist noch lange nicht beendet. Manche Spieler haben schon viele Spiele absolviert, andere noch wenige. Bisher haben gespielt: Steffi — Andi, Uwe — Bernd, Jana — Steffi, Jana — Petra, Petra — Bernd, Petra — Andi, Petra — Steffi. Wir können den Spielstand übersichtlich als Graph darstellen, wobei wir die Personen als Ecken und die durchgeführten Spiele als Kanten nehmen.
Manfred Nitzsche
5. Bäume
Zusammenfassung
Wer schon viele Graphen gesehen hat, dem fallen immer mehr Graphen auf. Auch Bäume kann man als Graphen ansehen: Stamm, Äste und Zweige erinnern uns an die Kanten eines Graphen. Dann müssten wir die Astgabeln und die Enden der Zweige als Ecken ansehen.
Manfred Nitzsche
6. Bipartite Graphen
Zusammenfassung
Fünf Jugendliche treffen sich zu einem gemeinsamen Frühstück. Jeder bringt etwas mit. Dazu wird eine Liste angelegt:
  • Steffi Brötchen, Tee
  • Niko Butter, Marmelade
  • Robert Marmelade, Saft
  • Anja Milch, Tee
  • Lars Käse, Brötchen
  • ? Kaffee
Manfred Nitzsche
7. Graphen mit Richtungen: Digraphen
Zusammenfassung
Erinnern wir uns noch einmal an die eulerschen Graphen: Damals ging es um die Frage, ob es einen Spaziergang gibt, bei dem man auf jeder Kante entlanggeht, und zwar auf jeder nur einmal, und zum Ausgangspunkt zurückkehrt. Wenn wir es geschafft haben, konnten wir an jeder Kante einen Pfeil anbringen um die Richtung, in die wir gegangen sind, zu kennzeichnen. Aus gewöhnlichen Kanten werden also gerichtete Kanten. Es lohnt sich solche Graphen genauer anzusehen, weil es zahlreiche Anwendungen gibt, in denen sie vorkommen. Ein Graph, in dem alle Kanten eine Richtung haben, nennt man einen gerichteten Graphen oder kurz einen Digraphen. Das Wort “Digraph” kommt von der englischen Bezeichnung “directed graph”.
Manfred Nitzsche
8. Körper und Flächen
Zusammenfassung
Bisher ging es in diesem Buch um Graphen als Zeichnungen in einer Ebene. Aber wer sagt denn, dass Graphen nicht auch Gebilde im Raum sein können? Die Ecken können wir uns auch im Raum verteilt vorstellen, und die Kanten stellen Verbindungen zwischen ihnen dar. Beispiele dafür gibt es genug: Die Stangen und Seile eines Zirkuszelts kann man so sehen oder auch die elektrischen Leitungen in einem Gebäude. Die folgende Zeichnung zeigt einen verspielten Graphen und einen Würfel. Wir befassen uns in diesem Kapitel mit Körpern und sehen sie als Graphen an. Da kommt es nur darauf an, dass sie Ecken und Kanten haben und in welcher Beziehung sie stehen, Wie lang die Kanten sind, wie groß das Volumen ist, all das sind Fragen, deren Beantwortung sehr wichtg sein kann, mit denen wir uns aber ausnahmsweise einmal nicht befassen. Erstaunlich, dass man trotzdem eine ganze Menge über Körper sagen kann.
Manfred Nitzsche
9. Farben
Zusammenfassung
Wenn im Atlas die einzelnen Länder deutlich zu erkennen sein sollen, müssen sie sich farblich von einander abheben. Man könnte jedem Land eine eigene Farbe geben. Dann brauchte man für eine Europakarte über 30 verschiedene Farben. Das ist ziemlich viel und man wird deshalb versuchen mit weniger Farben auszukommen und mehreren Länder dieselbe Farbe geben. Zu wenige Farben dürfen es aber auch nicht sein, denn benachbarte Länder müssen verschiedene Farben haben, damit sie deutlich zu unterscheiden sind.
Manfred Nitzsche
Was ist was?
Zusammenfassung
Diese Zusammenstellung von Definitionen enthält auch Begriffe. die nur in den zusätzlichen Hinweisen vorkommen. Die Zahlen geben an. auf welcher Seile der Begriff erklärt wird.
Manfred Nitzsche
Backmatter
Metadaten
Titel
Graphen für Einsteiger
verfasst von
Manfred Nitzsche
Copyright-Jahr
2005
Verlag
Vieweg+Teubner Verlag
Electronic ISBN
978-3-322-92380-6
Print ISBN
978-3-8348-0056-5
DOI
https://doi.org/10.1007/978-3-322-92380-6