Klassische Probleme der Graphentheorie (SoSe 2016)

• Die Anmeldung zum Proseminar erfolgt online vom 11.01.2016 bis zum 17.01.2016.
• Die Veranstaltung beinhalten keinen Kurs zu Präsentationstechniken, dieser muss ggf. vor der Teilnahme erfolgreich absolviert werden!

Graphen sind elementare mathematische Strukturen, die eine Menge von Objekten und die zwischen ihnen bestehenden Verbindungen beschreiben. Soziale Netzwerke, Moleküle sowie Straßen- und Rechnernetze sind nur einige anschauliche Beispiele für strukturierte Daten, die sich durch Graphen repräsentieren lassen.

Im Rahmen des Proseminars möchten wir uns mit klassischen graphentheoretischen Problemen und ihren algorithmischen Lösungen befassen. Es sollen ausgewählte Themen wie u.a. Graphisomorphie, Färbungsprobleme, Planarität sowie Matching- und Briefträgerprobleme in Graphen behandelt werden.

1. Graph Theory, Reinhard Diestel, 2010
2. Graph Theory 1736-1936, Norman L. Biggs, E. Keith Lloyd & Robin J. Wilson, 1986
3. Network Analysis: Methodological Foundations, Ulrik Brandes, Thomas Erlebach, 2005
4. Graphen und Algorithmen, Andreas Brandstädt, 1994
5. Graphentheoretische Konzepte und Algorithmen, Sven Krumke, Hartmut Noltemeier, 2009
6. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 2009
7. Combinatorial Optimization, William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver, 1998
8. Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman, Martin Grötschel, Ya-xiang Yuan, Documenta Mathematica, 2012, 43-50
9. A Faster Algorithm for Betweenness Centrality, Ulrik Brandes, Journal of Mathematical Sociology 25(2):163-177, 2001

Die Themenverteilung erfolgt während der Vorbesprechung. Im weiteren Verlauf des Semesters haben die Teilnehmer Zeit, die Ausarbeitung zu schreiben und den Vortrag vorzubereiten. In dieser Zeit wird es keine regelmäßigen Treffen in der Gruppe geben, jedoch ggf. Einzelgespräch zum zugeordneten Thema.

Es handelt sich um ein Blockseminar. Alle Teilnehmer halten kurz nach Ende der Vorlesungszeit einen 30-minütigen Vortrag über das festgelegte Thema. Im Anschluss folgt eine Diskussion über Thema und Vortrag. Es herrscht Anwesenheitspflicht bei allen Vorträgen. Bitte beachten Sie auch die Hinweise zur Foliengestaltung!

Voraussetzung für den Vortrag ist die vorherige Abgabe einer schriftlichen Ausarbeitung, welche 10-12 Seiten umfasst und mit LaTeX erstellt wird. Nach der Abgabe der Ausarbeitung besteht einmalig die Gelegenheit, die Ausarbeitung auf Grundlage der Rückmeldung des Betreuers zu überarbeiten. Mangelhafte Ausarbeitungen und 1:1-Übersetzungen sowie mangelhafte Vorträge führen zum Nicht-Bestehen des Proseminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen.