Graphentheorie
Dozent
Übungsleiter
Vorlesungstyp
4 Stunden Vorlesung und 2 Stunden Übung.
Ort und Zeit
Mo 14-16 N24/226 und Di 12-14 N24/226
Übung Mi 14-16 N24/131
Klausur
1. Klausur: Di 18/02/2014 von 14:00 bis 16:00 in H2
Zielgruppe
Bachelor Mathematik/Wirtschaftsmathematik/Mathematische Biometrie und Lehramt Mathematik.
Allgemeines
Diese Vorlesung dient als Grundlage für weitere Graphentheorievorlesungen im Masterstudium.
Vorleistung
Zum bestehen der Vorleistung müssen Sie eine Übungsaufgabe an der Tafel vorrechnen und benötigen 50% der Punkte der Übungszettel. Die Übungszettel dürfen Sie alleine oder in Gruppen von zwei Personen abgeben. Die Namen und Matrikelnummern müssen deutlich auf dem Übungsblatt vermerkt sein.
Übungsblätter
Die Übungsblätter finden Sie im slc.
Inhalt
Diese Vorlesung beschäftigt sich mehr mit strukturellen Eigenschaften von Graphen im Gegensatz zur Informatik und Optimierung, wo meinst algorithmische Probleme im Mittelpunkt stehen.
Der 4-Farbensatz ist wohl einer der bekanntesten Sätze der Graphentheorie:
Eine Landkarte kann mit 4 Farben so gefärbt werden, dass zwei benachbarte Länder nicht die gleiche Farbe bekommen.
Wir werden in dieser Vorlesung eine abgeschwächte Version mit 5 Farben beweisen.
Weitere Themengebiete:
Grundbegriffe
Wege und Kreise
Matchings
Zusammenhang
Planare Graphen
Färbungen
Extremalgraphen
Literatur
R. Diestel, Graphentheorie, 4te Auflage, Springer 2010.
B. Bollobas, Modern Graph Theory, Springer 1998.
J.A. Bondy und U.S.R. Murty, Graph Theory, Springer 2008.
J.A. Bondy und U.S.R. Murty, Graph Theory with Applications, 1976.
D.B. West, Introduction to Graph Theory, Prentice-Hall 2005.
L. Volkmann, Graphen an allen Ecken und Kanten, 2011.