Graphentheorie

Wie lassen sich Beziehungen, Verbindungen und Strukturen mathematisch beschreiben? Die Graphentheorie entwickelt dafür eine einheitliche Sprache. Sie gehört zu den grundlegenden Gebieten der diskreten Mathematik und besitzt zugleich zahlreiche Verbindungen zur Informatik und zu Anwendungen in verschiedenen Bereichen. Dieses Lehrbuch führt systematisch in die Graphentheorie ein. Beginnend mit den grundlegenden Begriffen werden Graphen, Knotengrade, Wege und Kreise, Zusammenhang, Bäume und Wälder sowie bipartite Graphen behandelt. Darauf aufbauend folgen Paarungen und der Satz von Menger, planare Graphen und der Satz von Kuratowski sowie Graphfärbungen, Flüsse in Netzwerken und Hamiltonkreise. Ein weiterer Schwerpunkt liegt auf Teilgraphen und Minoren sowie auf Baumzerlegungen und Baumweite. Besonderer Wert wird auf ein klares Verständnis der mathematischen Strukturen gelegt. Präzise Definitionen, vollständige Beweise und anschauliche Abbildungen erläutern die zentralen Begriffe und Zusammenhänge. Zahlreiche Übungsaufgaben mit ausführlich dargestellten Lösungen ermöglichen es, die behandelten Methoden selbstständig anzuwenden und das eigene Verständnis zu überprüfen. Das Buch eignet sich insbesondere für Studierende der Mathematik und Informatik in einem ersten universitären Kurs zur Graphentheorie sowie für alle, die sich das Gebiet im Selbststudium systematisch erschließen möchten. Ein abschließender Ausblick führt unter anderem in die Ramseytheorie, Zufallsgraphen und die moderne Graphminorentheorie.