Graphentheorie

Dozent

Prof. Dr. Bruhn-Fujimoto

Übungsleiter

Dr. Christian Löwenstein

Laura Gellert


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.

Aktuelles