====== Klassische Probleme der Graphentheorie (SoSe 2016) ======

| Titel  | Klassische Probleme der Graphentheorie |
|        | Classical Problems in Graph Theory     |
| Veranstalter | [[staff:kriege|Dr. Nils Kriege]] |
| Veranstaltungsart    | Proseminar ([[http://www.cs.tu-dortmund.de/nps/de/Studium/Ordnungen_Handbuecher_Beschluesse/Modulhandbuecher/Bachelor_Inf/INF/INF-P/INF-BSc-110.pdf|INF-BSc-110]], Element 2)              |
| Veranstaltungsnummer | [[https://www.lsf.tu-dortmund.de/qisserver/rds?state=verpublish&status=init&vmfile=no&publishid=174698&moduleCall=webInfo&publishConfFile=webInfo&publishSubDir=veranstaltung|040603]] |
| SWS                  | 2                        |
| Max. Teilnehmer      | 12                       |

===== Allgemeine Hinweise =====
  * Die Anmeldung zum Proseminar erfolgt [[http://www.cs.tu-dortmund.de/nps/de/Studium/besondere_Lehrveranstaltungen/Proseminare/index.html|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!

===== 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 =====
/*
<WRAP info center round big 60% bigger>
  * **Die Themenvergabe erfolgt im Rahmen der Vorbesprechung.**
  * **Literaturhinweise zu den einzelnen Themen werden ausgegeben.**
</WRAP>
*/
^ Nr. ^ Thema ^ Quellen ^ Teilnehmer ^ 
|  1.| Eulerpfade |  2, 4, 8 |  Jonas Wielage  |
|  2.| <del>Hamiltonkreise</del> |  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.| <del>Betweenness Zentralität</del> |  9 | |


==== Literatur ====
  - **Graph Theory**, Reinhard Diestel, 2010
  - **Graph Theory 1736-1936**, Norman L. Biggs, E. Keith Lloyd & Robin J. Wilson, 1986
  - **Network Analysis: Methodological Foundations**, Ulrik Brandes, Thomas Erlebach, 2005
  - **Graphen und Algorithmen**, Andreas Brandstädt, 1994
  - **Graphentheoretische Konzepte und Algorithmen**, Sven Krumke, Hartmut Noltemeier, 2009
  - **Introduction to Algorithms**, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 2009
  - **Combinatorial Optimization**, William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver, 1998
  - **Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman**, Martin Grötschel, Ya-xiang Yuan, Documenta Mathematica, 2012, 43-50
  - **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  |  <color #00a700>**Mittagspause**</color>      |  <color #00a700>**Mittagspause**</color>  |
^  13:30 -- 14:15  |  **Planare Graphen** \\ Franka Bause          |  <color #0000a7>**Lehrevaluation**</color>  |
^  :::          |  :::                                          |  **Statistiken für Graphen** \\ Robin Möhring  |
^  14:15 -- 15:00  |  **Das Vier-Farben-Problem** \\ Fabian Cziuk  |  :::  |
^  :::          |  :::                                          |  <color #0000a7>**Abschlussrunde**</color>  |
^  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 [[http://ls11-www.cs.tu-dortmund.de/people/chimani/seminarfolien.html|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 |