Der Kurs Graphentheorie ist in erster Linie ein Wahlpflichtmodul der
Mathematik innerhalb des Studiengangs Bachelor in Mathematik und ein
Basismodul innerhalb des Studiengangs Master in Mathematik. Er kann aber
auch im Hauptstudium der Diplomstudiengänge im Fach Mathematik
eingesetzt werden und gehört dort sowohl zur reinen als auch zur
anwendungsorientierten Mathematik.
Graphen und Netze finden ihre
wichtigste Anwendung in der Optimierungstheorie, z.B. bei der Ermittlung
des optimalen Verkehrsflusses in einem Verkehrssystem.
Der Kurs gibt
eine Einführung in die Theorie ungerichteter und gerichteter Graphen.
Der Stoff ist in die folgenden Paragraphen gegliedert:
Grundbegriffe
der Graphentheorie; Zusammenhang und Bäume; Eulertouren und
Hamiltonkreise; Zyklenraum und Schnittraum; Flüsse in Netzwerken und die
Mengerschen Sätze; Unabhängige Mengen und Überdeckungen; Färbung von
Graphen.
Breiter Raum ist der strukturellen Behandlung von Graphen
und Digraphen gewidmet. Die algorithmische Behandlung konzentriert sich
auf die Analyse einiger besonders wichtiger Algorithmen, die informell
beschrieben werden. Pseudocode-Implementierungen von Algorithmen sind
nicht vorgesehen.
Vorausgesetzt wird mathematisches Grundwissen über Mengen und Abbildungen sowie gute Kenntnisse der Linearen
Algebra.