Summer Term 2021

Ü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: 24.02.2021 10:00 Uhr (online in BigBlueButton)

Teilnahme

Wenn Sie an dem Proseminar teilnehmen möochten, melden Sie sich bitte bis zum 23.02.2021 unter Nennung Ihrer 3 favorisierten Themen mit einer informellen E-Mail bei Matthias Thimm an. Die finale Themenvergabe findet in der Vorbesprechung am 24.02.2021 10:00 Uhr (online in BigBlueButton) statt. Eine Teilnahme an dieser Vorbesprechung ist erforderlich.

Jeder Teilnehmer erarbeitet im Rahmen des Proseminars einen Vortrag (maximal 30 Minuten Vortragszeit) und reicht diesen digital als Video ein (beispielsweise ein Screencast oder eine Aufzeichnung vor einer Tafel, etc.). Das Video muss spätestens am 31.08.2021 eingereicht werden.

Am Ende des Proseminars, d.h. am Ende des Sommersemesters 2021, ist eine schriftliche Ausarbeitung abzugeben, die das gewählte Thema auf max. 12 Seiten präsentiert (Nutzen Sie für die Ausarbeitungen bitte die LaTeX-Vorlage der LNCS Proceedings Reihe. Die Struktur der Ausarbeitung soll der Struktur der Präsentation folgen, aber dessen Inhalte weiter ausarbeiten.

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

Lecturers

Isabelle Kuhlmann

• Alumnus

Prof. Dr. Matthias Thimm

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