Dozenten:
Prof. Dr. Barbara König
Harsh Beohar
Benjamin Cabrera (Kontaktperson)
Christine Mika
Dennis Nolte

Inhalt

Graphen, bestehend aus Knoten und Kanten, kommen in der Informatik in vielen Zusammenhängen vor. Beispielsweise können Rechner- und Straßennetze, das Internet, Nachbarschaftsbeziehungen, endliche Automaten, Transitionssysteme und semantische Beziehungen geeignet durch Graphen beschrieben werden. Es ist daher wichtig, Verfahren und Methoden zu besitzen, die die Struktur von Graphen untersuchen und auch Graphen transformieren können, wenn sich die Topologie des zu untersuchenden Systems ändern sollte. Insbesondere geht es in diesem Seminar um folgende Themen:

• Graphentheorie: Welche Typen von Graphen gibt es? Welche Strukturen treten in Graphen auf? Welche bekannten Sätze über Graphen gibt es? (z.B. Vierfarbentheorem)
• Graphalgorithmen: Wie kann man Graphen am besten algorithmisch verarbeiten? Welche Verfahren gibt es, um Graphen zu untersuchen (z.B. Chinese Postman Problem, Max Flow)? Wie lassen sich Graphen zeichnen/visualisieren?
• Graphtransformation: Wie kann man Graphen mit Hilfe von Regeln transformieren? Wie funktionieren Graphgrammatiken? Wie kann man nebenläufige Systeme mit Hilfe von Graphtransformationsregeln modellieren?
• Soziale Netzwerke als Graphen: Besonders mit dem verstärkten Aufkommen von Sozialen Medien und Sozialen Netwerk Seiten (Facebook, LinkedIn, ...) hat das Interesse an der Modellierung von sozialen Netzwerken durch Graphen stark zugenommen. Interessante Fragen sind zum Beispiel: Wer sind die wichtigen Akteure in einem sozialen Netzwerk? Lassen sich Individuen anhand der Graphenstruktur zu logischen Gruppen zusammenfassen? Wie erzeugen Facebook und Co Vorschläge für Personen die ich kennen könnte?