Graphentheorie

30 Präsenzstunden Vorlesung, 30 Präsenzstunden Übung, 35 Stunden Vor-/Nachbereitung der Übungen, 55 Stunden Nachbereitung der Vorlesung und Prüfungsvorbereitung

Solide Programmierkenntnisse in einer modernen Programmiersprache, Diskrete Mathematik, Lineare Algebra, Grundlagen der Informatik

Kenntnisse der Methoden und Werkzeuge der Graphentheorie, sowie die Fähigkeit, diese auf Probleme in realen Applikationen abbilden und anwenden zu können.

Die Studierenden ...

• charakterisieren die verschiedenen Arten von Graphen
• wenden Algorithmen auf gegebene Problemstellungen an
• benennen Problemstellungen, die mit Graphenalgorithmen gelöst werden können und schätzen den Aufwand dazu ein

• analysieren gegebene Problemstellungen auf

• Anwendbarkeit von Graphenalgorithmen

• Komplexität des unterliegenden Problems

Objekte und Beziehungen zwischen diesen treten in sehr vielen Applikationen der Informatik auf. Graphen sind eine Verallgemeinerung dieser Systeme aus Objekten und Beziehungen zwischen ihnen. Die Graphentheorie stellt Werkzeuge zur Verfügung, Graphen zu repräsentieren, auf bestimmte Eigenschaften hin zu analysieren, sie effizient zu vergleichen oder zu durchsuchen.

Ausgehend von einfachen Anwendungsfällen werden unter anderem folgende Themengebiete behandelt:

• Klassifizierung, Darstellung und Implementierung sowie Eigenschaften von Graphen
• Eulersche und Hamiltonsche Wege
• Färbungen von Graphen
• Minimale aufspannende Bäume
• Suche in Graphen: Tiefensuche, Breitensuche, kürzeste Wege
• Maximaler Fluss und minimale Schnitte in Netzwerken
• Lösen von Optimierungsproblemen

darüber hinaus werden Themen der Anwendung der Graphentheorie behandelt wie z.B.

• Machine Learning (Embeddings, Graph Neural Networks)
• Logik
• Matroide als Generalisierung von Greedy Algorithmen

Tafel, Papier, Folien oder Beamer

• Reinhard Diestel, Graphentheorie, Springer, Berlin, 2000
• F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969
• Volker Turau, Algorithmische Graphentheorie, Oldenbourg Verlag, 2004
• Dieter Jungnickel, Graphs, Networks and Algorithms, Springer, 2012
• Ahuja, Magnanti, Orlin, Network Flows. Theory, Algorithms and Applications, Prentice Hall, 1993