Skip to main content
main-content
Top

About this book

Dieses essential liefert eine Einführung in die Graphentheorie; Vorkenntnisse werden dabei nicht benötigt. Ein Graph ist ein Gebilde bestehend aus Ecken und verbindenden Kanten. Wir untersuchen Kreise in Graphen (die jede Kante bzw. jede Ecke besuchen sollen), fragen uns, welche Graphen sich überschneidungsfrei zeichnen lassen, und schließlich machen wir uns an die Färbung von Graphen (wobei keine benachbarten Ecken mit derselben Farbe versehen werden sollen). Diese klassischen Themen der Graphentheorie werden durch eine Vielzahl von Illustrationen und einigen historischen Anmerkungen untermalt; motivierende Übungsaufgaben (mit Lösungen) und viele bunte Beispiele erleichtern den Einstieg in dieses aktuelle und vielseitige Gebiet der Mathematik.

Table of Contents

Frontmatter

Kapitel 1. Es war einmal in Königsberg...

Zusammenfassung
Oftmals liest man, dass die Graphentheorie mit Leonhard Eulers Lösung des sogenannten Königsberger Brückenproblems begonnen habe, und entsprechend fangen auch wir mit demselben an.
Katja Mönius, Jörn Steuding, Pascal Stumpf

Kapitel 2. Das Party-Problem

Zusammenfassung
Graphen helfen uns oftmals, Netzwerke zu modellieren und besser zu verstehen, so auch in der folgenden kleinen Geschichte, in der nun erstmals ein (aus der Sesamstraße bekannter) Graf auftritt.
Katja Mönius, Jörn Steuding, Pascal Stumpf

Kapitel 3. Graphen plätten!

Zusammenfassung
Wir starten mal wieder mit etwas zum Tüfteln: Im Flatland (das ist ein Land, das sich, im Gegensatz zu unserer Erde, nicht im dreidimensionalen Raum, sondern im Zweidimensionalen befindet) soll jeder Haushalt mit Gas, Wasser und Strom versorgt werden.
Katja Mönius, Jörn Steuding, Pascal Stumpf

Kapitel 4. Graphen färben!

Zusammenfassung
Graphentheorie ist eine junge mathematische Disziplin mit vielen Anwendungen. So können beispielsweise Graphen bei der Erstellung von Netzwerken, Metroplänen, Stundenplänen oder gar Sudokus helfen. Oft ist es hilfreich, dafür Graphen mit einer bestimmten Färbung ihrer Ecken oder Kanten zu betrachten. Eng damit verbunden, aber weniger anwendungsbezogen, ist die Frage nach Färbungen von Landkarten, die sich der Student Francis Guthrie bereits 1852 stellte: Wie viele Farben werden benötigt, so dass keine benachbarten Länder in derselben Farbe eingefärbt werden?
Katja Mönius, Jörn Steuding, Pascal Stumpf

Kapitel 5. Listenfärbbarkeit

Zusammenfassung
In diesem Kapitelchen gehen wir über den klassischen Färbbarkeitsbegriff hinaus und stellen (und beweisen) mit dem Fünflistenfärbbarkeitssatz ein erstes modernes Ergebnis vor.
Katja Mönius, Jörn Steuding, Pascal Stumpf

Kapitel 6. Die Party geht weiter...

Zusammenfassung
Als sich die kleine Party von Graf Zahl langsam dem Ende zuneigt, fällt ihm in Erinnerung an das Gläserklingen zu Beginn beim Verteilen der nächsten Getränke schließlich noch ein letztes Spiel für seine Gäste ein: Wie oft können sie ihre Gläser miteinander klingen lassen, so dass unter je drei Personen allerdings nicht alle miteinander angestoßen haben?
Katja Mönius, Jörn Steuding, Pascal Stumpf

Backmatter

Additional information

Premium Partner

    Image Credits