Einführung in die Graphentheorie: Ein farbenfroher Einstieg in die Diskrete Mathematik

Von Katja Mönius, Jörn Steuding und Pascal Stumpf

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.

• Sprache: Deutsch
• Herausgeber: Springer Spektrum
• Erscheinungsdatum: 7. Juli 2021
• ISBN: 9783658331085

Buchvorschau

© Der/die Autor(en), exklusiv lizenziert durch Springer Fachmedien Wiesbaden GmbH, ein Teil von Springer Nature 2021

K. Mönius et al.Einführung in die Graphentheorieessentialshttps://doi.org/10.1007/978-3-658-33108-5_1

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

Katja Mönius¹  , Jörn Steuding¹   und Pascal Stumpf¹  

(1)

Institut für Mathematik, Universität Würzburg, Würzburg, Deutschland

Katja Mönius (Korrespondenzautor)

Email: [e-mail]

Jörn Steuding

Email: [e-mail]

Pascal Stumpf

Email: [e-mail]

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.

../images/502327_1_De_1_Chapter/502327_1_De_1_Figa_HTML.png

Im 18. Jahrhundert kursierte im damals preußischen Königsberg (heute Kaliningrad in der russischen Enklave zwischen Polen und Litauen) die Frage, ob es einen Rundgang durch die Stadt gebe (siehe obige Abbildung), bei dem alle sieben Brücken über den Fluss Pregel genau einmal überquert werden? Der junge Euler löste 1735/1736 das Rätsel wie folgt: Er benannte die vier Stadtteile als A, B, C, D und die angrenzenden sieben Brücken als a, b, c, d, e, f, g, was ermöglicht, Wege als abwechselnde Folge von Groß- und Kleinbuchstaben zu notieren, wie auch das Beispiel

$$ AaBfD\,\ldots \,cA $$

illustriert. Ein hypothetischer geschlossener Rundweg, der jede Brücke genau einmal benutzt, würde dann mit genau sieben Kleinbuchstaben (für die sieben Brücken) und demzufolge acht Großbuchstaben notiert werden, wobei am Anfang und am Ende der Kette derselbe stünde; deshalb ist es auch egal, mit welchem der Großbuchstaben oder Stadtteile man begönne. Euler beobachtete nun, dass dabei der Inselstadtteil, den wir etwa mit A notieren, aufgrund seiner fünf abzweigenden Brücken genau dreimal auftreten müsste, während die Buchstaben der anderen Stadtteile entsprechend genau zweimal zu verzeichnen wären. Läuft man nämlich auf einem Rundweg in einen Stadtteil hinein, so muss man ja auch wieder hinaus. Sollen alle angrenzenden fünf Brücken des Inselstadtteils A überquert werden, so benötigt man dazu drei Besuche der Insel, während die anderen Stadtteile mit ihren jeweils drei Brücken jeweils genau zweimal betreten werden müssen. Insgesamt ergäbe sich also so eine Zeichenkette von