Vorlesung über "Graphentheorie"

Die klassische Querschnittsdisziplin in Wissenschaft und Technik ist die Mathematik. In den letzten Jahrzehnten hat sich auch die Informatik zu einer Querschnittsdisziplin entwickelt. In vielen Anwendungen aus diesen Bereichen spielt die Darstellung komplexer Strukturen und deren Beziehungen zueinander eine wichtige Rolle. Um diese Informationen zu modellieren, und um dann mathematische und informatische Methoden anwenden zu können, wird die abstrakte Datenstruktur des Graphen benutzt.

Graphen sind in der Mathematik und Informatik ein weitverbreitetes Werkzeug um verschiedenartigste Daten und Strukturen intuitiv darzustellen. Ein Graph G=(V,E) besteht aus einer endlichen Menge V von Knoten und einer endlichen Menge E von Kanten, die Verbindungen zwischen je zwei Knoten darstellen. In diesem Zusammenhang beschreiben die Knoten des Graphen Objekte und die Kanten Beziehungen, die zwischen den Objekten bestehen.

Das eigenständige Gebiet der Graphentheorie, welches gleichermaßen in der Kombinatorik und der Informatik beheimatet ist, behandelt klassische Probleme, e.g. das Problem eine Landkarte mit vier Farben einzufärben und aktuelle Fragestellungen, z.B. das Frequenzvergabeproblem aus dem Bereich des Mobilfunks. In der Vorlesung "Graphentheorie" sollen sowohl unter strukturellen als auch algorithmischen Aspekten graphentheoretische Konzepte, Modelle und Methoden vorgestellt werden. Nach einer kurzen Einführung sollen u.a. folgende Themen behandelt werden: Zusammenhang und Abstand, Eulertouren und Hamiltonkreise, Planare Graphen, Faktoren und Matching, Färbungen, Perfekte Graphen, Ramseytheorie.

Literaturempfehlungen werden im Laufe der Vorlesung gegeben. Die Vorlesung wendet sich an Studenten des Hauptstudiums. In den begleitenden Übungen wird der Vorlesungsstoff vertieft. Bei aktiver Mitarbeit in den Übungen und erfolgreicher Teilnahme an der zum Semesterende stattfindenden Klausur kann ein Übungsschein erworben werden.

Termine

Dienstags 10-12 und mittwochs 10-12, in Hörsaal 301, Pohlighaus.

Literatur

Literaturempfehlungen werden im Laufe der Vorlesung gegeben