Graphentheorie

Die Graphentheorie ist ein sehr aktives Teilgebiet der Diskreten Mathematik mit starker Nähe zur Informatik. Es ist ohne großen Begriffsapparat relativ leicht zugänglich und kombiniert strukturelle Resulate mit algorithmischen Methoden und Denkweisen. Da die grundlegenden diskreten Algorithmen (Shortest Paths, Minimum Spanning Tree, Flows, etc.) in den Optimierungsvorlesungen besprochen werden, sollen in dieser Vorlesung die strukturellen Aspekte sowie die Theorie zu den algorithmisch schweren Problemen im Vordergrund stehen.

Folgende Themen sind geplant:

Grundbegriffe
Wege und Kreise
Matchings
Zusammenhang
Planare Graphen
Färbungen, Unabhängigkeit, Dominanz
Extremale Probleme und Teilstrukturen

Hier einige Lehrbücher:

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.
R. Diestel, Graphentheorie, 4te Auflage, Springer 2010.
D.B. West, Introduction to Graph Theory, Prentice-Hall 2005.
L. Volkmann, Graphen an allen Ecken und Kanten, 2006.

Hier die Antworten auf einige praktische Fragen zu http://campusonline.uni-ulm.de/qislsf/rds?state=verpublish&status=init&vmfile=no&publishid=34774&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltungVorlesung und Übung.

Der Modus zu den Hausaufgaben ist wie folgt: Das neue Übungsblatt wird im Allgemeinen am Donnerstag einer Woche hier abrufbar sein. Die Hausaufgabe des Blattes ist am kommenden Mittwoch vor der Übung abzugeben.

Zu dieser Vorlesung gibt es kein offizielles Skript.

Übungsblätter (Musterlösungen sind im SLC zu finden):

Blatt 1

Blatt 2

Blatt 3

Blatt 4

Blatt 5

Blatt 6

Blatt 7

Blatt 8

Blatt 9

Blatt 10

Blatt 11

Blatt 12

Blatt 13

 

Probeklausur mit Lösungen

Termin der Klausur: 14.02.2011, 14:00-16:00 Uhr, H16
Termin der Einsicht: 15.02.2011, 14:00 Uhr, E04 (Büro von Philipp Schäfer, He 22)

Termin der Nachschreibeklausur: 28.03.2011, 14:00-16:00 Uhr, H20