Sie sind hier

Proseminar "Graphenalgorithmen"

Ü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: 15.02.2017 10:15 (Raum E.427)

Proseminar: Montags 14:15-15:45 Uhr (Raum H.009), erste Veranstaltung am 08.05.2017

Teilnahme

Um an dem Proseminar teilzunehmen ist eine Teilnahme an der Vorbesprechung am 15.02.2017 10:15 (Raum E.427) 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

Veranstaltung in KLIPS: Proseminar

Beteiligte: 

Dr. Matthias Thimm

thimm@uni-koblenz.de

Publications:
N/A