Table of Contents

Klassische Probleme der Graphentheorie (SoSe 2016)

Titel Klassische Probleme der Graphentheorie
Classical Problems in Graph Theory
Veranstalter Dr. Nils Kriege
Veranstaltungsart Proseminar (INF-BSc-110, Element 2)
Veranstaltungsnummer 040603
SWS 2
Max. Teilnehmer 12

Allgemeine Hinweise

Inhalt

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.

Themen

Nr. Thema Quellen Teilnehmer
1. Eulerpfade 2, 4, 8 Jonas Wielage
2. Hamiltonkreise 2, 4
3. Minimale Spannbäume 6 David Feininger
4. Planare Graphen 1, 2 Franka Bause
5. Das Vier-Farben-Problem 2, 4 Fabian Cziuk
6. Flußprobleme 4, 6 Nicole Funk
7. Zuordnungsprobleme 5, 7 Irina Solovyeva
8. Briefträgerprobleme 7, 8 Julian Meise
9. Graphisomorphie 3 Cihat Altin
10. Statistiken für Graphen 3 Robin Möhring
11. Kürzeste Wege 6 Christoph Meyer
12. Betweenness Zentralität 9

Literatur

  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

Zeitplan

Mittwoch, 27.07.2016 Donnerstag, 28.07.2016
10:00 – 10:45 Eulerpfade
Jonas Wielage
Zuordnungsprobleme
Irina Solovyeva
10:45 – 11:30 Minimale Spannbäume
David Feininger
Briefträgerprobleme
Julian Meise
11:30 – 12:15 Kürzeste Wege
Christoph Meyer
Graphisomorphie
Cihat Altin
12:15 – 13:30 Mittagspause Mittagspause
13:30 – 14:15 Planare Graphen
Franka Bause
Lehrevaluation
Statistiken für Graphen
Robin Möhring
14:15 – 15:00 Das Vier-Farben-Problem
Fabian Cziuk
Abschlussrunde
15:00 – 15:45 Flußprobleme
Nicole Funk

Ablauf & Termine

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.

Termin Datum Zeit Ort
Vorbesprechung 14.04.2016 16:15 – 17:45 R202, OH14
Abgabe des Ausarbeitungskonzepts 22.05.2016 23:59
Abgabe der Ausarbeitung 05.06.2016 23:59
Abgabe der Ausarbeitung (Überarbeitete Version) 26.06.2016 23:59
Abgabe der Präsentationsfolien (Konzept) 03.07.2016 23:59
Abgabe der Präsentationsfolien 10.07.2016 23:59
Vorträge 27.07.2016 10:00 – 16:00 R202, OH14
28.07.2016 10:00 – 15:00 R202, OH14