Summer Term 2015

Überblick

In vielen Bereichen der Informatik werden Graphen als Datenstruktur verwendet und dienen auch als Abstraktion für viele verschiedene Probleme. Dieses Proseminar vertieft und erweitert dazu die in "Algorithmen und Datenstrukturen" vermittelten Inhalte zu Graphen. Neben formalen Grundlagen der Graphentheorie werden in diesem Proseminar dabei Probleme auf Graphen wie Färbbarkeit, Clustering, und Routing, als auch praktische Aspekte wie Graphdatenbanken diskutiert.

Seminarthemen

1. Grundlagen der Graphentheorie I
   Typen von Graphen, Bipartite Graphen, Vollständige Graphen, Bäume, Wege, Kreise, Traversierung
2. Grundlagen der Graphentheorie II
   Adjazenzmatrizen, Graphmetriken, Durchmesser von Graphen, Planare Graphen, Satz von Euler
3. Grundlagen der Graphentheorie III
   Zusammenhang, Starker Zusammenhang, Isomorphismus, Algorithmus von Kosaraju
4. Das Vertex-Cover Problem
   Satz von König, Komplexität, Algorithmen
5. Matching
   Matching, Perfekte Matchings, Satz von Tutte, Algorithmus von Edmonds, Algorithmus von Hopcroft-Karp
6. Spannbäume und das Steinerbaumproblem
   Minimale Spannbäume, Algorithmus von Prim, Algorithmus von Kruskal, Steinerbaumproblem, Algorithmen, Komplexität
7. Färbung von Graphen
   Chromatische Zahl, Knotenfärbung planarer Graphen, Komplexität, Algorithmen
8. Hamilton'sche Graphen und das Traveling Salesman Problem
   Hamilton'schheit, Hypohamilton'schheit, Trassable Graphen, Satz von Grinberg, Traveling-Salesman Problem, Komplexität, Algorithmen
9. Visualisierung von Graphen
   Crossing numbers, Graphlayoutstrategien, Force-directed Layout, Coffman-Graham Algorithmus
10. Graph Clustering
    Community detection, Modularität von Graphen, Algorithmus von Girvan-Newman
11. Max-Cut, Min-Cut, und Maximum Flow
    Algorithmus von Ford-Fulkerson, Algorithmus von Goldberg-Tarjan, Max-flow Min-cut Theorem, Max-cut, Approximationsalgorithmen von Max-cut
12. Kürzeste Wege
    Djikstra, Bellmann-Ford, A*, IDA*, Algorithmus von Johnson
13. Graphprobleme in sozialen Netzwerken
    Link Prediction, Barabasi-Albert Modell, Zentralität, PageRank Algorithmus
14. Graphdatenbanken
    Cypher, Gremlin, Neo4J, RDF, Anwendungen, Vergleich relationale Datenbanken

Literaturempfehlungen

• Sven Oliver Krumke and Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen. Springer, 2012.
• Peter Tittmann. Graphentheorie: Eine anwendungsorientierte Einführung. Carl Hanser Verlag, 2011

Termine

Vorbesprechung: 14.04.2015 14:15 (Raum F.522)

Blockseminar: 04.08. 09:15-17:45, 05.08. 09:15-17:45 (Raum B.017)

Teilnahme

Um an dem Proseminar teilzunehmen ist eine Teilnahme an der Vorbesprechung am 14.04.2015, 14:15 (Raum F.522) erforderlich. Wenn Sie Interesse haben an dem Proseminar teilzunehmen, kündigen Sie dies bitte vorab in einer informellen E-Mail an Matthias Thimm an.

Von den Teilnehmern wird eine Präsentation (ca. 30 Minuten) über eines der oben genannten Themen erwartet. Im Anschluss an das Proseminar ist eine Ausarbeitung über das Seminarthema (ca. 12 Seiten) abzugeben.

Bitte beachten Sie bei der Erstellung der Präsentation und der Ausarbeitung folgende allgemeine Richtlinien (nur in Englisch verfügbar): pdf

Proseminar - Graphenalgorithmen

Veranstaltungsnummer: 04448

Lecturers

Prof. Dr. Matthias Thimm

• thimm@uni-koblenz.de
• Alumnus
• B 108
• +49 261 287-2715

Martin Leinberger

• Alumnus