Graphentheorie
Fakultät für Informatik und Mathematik ©
Name Graphentheorie
Verantwortlich Prof. Dr. Max Fischer
SWS 4
ECTS 5
Sprache(n) Deutsch
Lehrform SU mit Übung
Angebot im Wechsel mit anderen Fächern der gleichen Fachgruppe
Aufwand

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

Voraussetzungen

Solide Programmierkenntnisse in C++

Ziele

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

Inhalt

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
Medien und Methoden

Tafel, Papier, Folien oder Beamer

Literatur
  • Reinhard Diestel, Graphentheorie, Springer, Berlin, 2000
  • F. Harary, Graph Theory, Addison-Wesley, Reading, Mass., 1969
  • Volker Turau, Algorithmische Graphentheorie, Oldenbourg Verlag, 2004
Zuordnungen Curricula
SPO Fachgruppe Code ab Semester Prüfungsleistungen
IG Version 2010 CGBV: Theoretische Grundlagen IG-TTI-0040 1 benotete schriftliche Prüfung 90 Minuten
IG Version 2010 EC: Theoretische Grundlagen IG-TTI-0040 1 benotete schriftliche Prüfung 90 Minuten
IG Version 2010 SWE: Theoretische Grundlagen IG-TTI-0040 1 benotete schriftliche Prüfung 90 Minuten
IS Version 2009 WPF Informatik und Wirtschaft IF-S-M-I07 1 benotete schriftliche Prüfung 90 Minuten
IS Version 2017 WPF Informatik und Wirtschaft IF-S-M-I07 1 benotete schriftliche Prüfung 90 Minuten