Proseminar Graphen

Viele Problemstellungen der Informatik lassen sich gut mit Graphen formalisieren. Eigenschaften von Graphen und deren mathematische Formalisierung werden in der Graphentheorie betrachtet, einem wichtigen Teilgebiet der diskreten Mathematik.
In diesem Prosemimar werden wir komplexere Probleme und deren Lösung betrachten, beispielsweise: bipartite Graphen, Plättbarkeit und Satz von Kuratowski, Färbungen von Graphen und den 4-Farben-Satz, Flüsse in Netzwerken, das Travelling-Salesman-Problem und Heuristiken. Dabei interessieren wir uns auch für die algorithmische Umsetzbarkeit von graphentheoretischen Problemen und für Kriterien, die die effiziente algorithmische Lösbarkeit von Problemen ermöglichen.

Zielgruppe und benötigte Vorkenntnisse:

Das Seminar kann als Proseminar in den Studiengängen der Mathematik und der Informatik gewählt werden.
Die Teilnehmer sollten entweder die Vorkenntnisse aus den Veranstaltungen Mathematik für Informatiker I und II oder den Veranstaltungen Lineare Algebra I und II mitbringen.
Die nötigen graphentheoretischen Grundlagen werden wir in einem ersten Vortrag legen, der als Einzeltermin im November stattfinden wird: Donnerstag, 18.11.2004, 12 c.t. in 04-516

Termine und Anmeldung:

Aus organisatorischen Gründen wird das Proseminar als Blockseminar teilweise ganztägig an zwei Tagen im Januar stattfinden:

Freitag, 4.2.05, 12 Uhr (c.t.)-18:00 Uhr und Samstag, 5.2.05 10:00 Uhr (s.t.)-17:30 Uhr

Veranstaltungsort ist jeweils 04-426.

Achtung: Aus organisatorischen Gründen wurde der Termin um eine Woche nach hinten auf den 4.2. und 5.2. verschoben.

Die Vorbesprechung zur Themenverteilung fand statt am: 28.10.04, 12 Uhr c.t.
Um den benoteten Proseminarschein zu erhalten, ist ein Vortrag auszuarbeiten und zu halten, ein Handout zum Vortrag zu erstellen und die Anwesenheit an den Sitzungen des Proseminars nötig.

Themenliste und Literaturvorschläge

Die aktuelle Themenliste mit den dazugehörigen Literaturvorschlögen gibt es hier zum Donwload: PS, PDF

Kurzübersicht über die Vorträge+Vortragenden:

	Thema	Name Vortragende(r)	Zeit
1	Einleitung	Götz Schwandtner	18.11.04
2	Plättbarkeit	Yael Fleischmann	4.2.05, 12:30 Uhr
3	Vierfarbensatz	Joschka Kupilas	4.2.05, 13:45 Uhr
4	Flüsse in Netzwerken	Gösta Kroll	4.2.05, 15:15 Uhr
5	Matchings	Meng Qin	4.2.05, 16:30-17:45 Uhr
6	TSP: Theorie	René Pickhardt	5.2.05, 10:00 Uhr
7	TSP-Implementierungen	Nils Binz	5.2.05, 11:15-12:30 Uhr
8	Teilstrukturen	Armen Lalayan	5.2.05, 13:30 Uhr
9	Zufallsgraphen	Kurban Aliev	5.2.05, 14:45 Uhr
10	Treewidth	Robert Deußer	5.2.05, 16:00-17:15 Uhr

Download und Infomaterial:

Den Aushang mit Infos zum Proseminar gibt es hier zum Download: ps, ps.gz pdf

Zurück zu meiner Homepage