Modulcode:	Inf-GraphTheo
Englische Bezeichnung:	Graphtheory
Modulverantwortliche(r):	Prof. Dr. Anand Srivastav
Turnus:	jedes Jahr im WS (WS11/12 WS12/13 WS13/14 WS14/15 WS16/17 WS17/18)
Präsenzzeiten:	4V 2Ü
ECTS:	9
Workload:	270 Std.
Dauer:	ein Semester
Modulkategorien:	WI (MSc Inf (15)) WI (MSc WInf (15)) MSc Math (Export) TG (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

Die Vorlesung ist eine Einführung in die Graphentheorie für Studierende der Informatik und Mathematik.

Lernziele:

Erlernen von Techniken zur Analyse von Graphenstrukturen. Verständnis der Modellierung von kombinatorischen Aufgaben mittels Graphen. Erlernen kombinatorischer Argumente in komplexen Aufgaben.

Lehrinhalte:

Kürzeste Wege, Minimale Spannbäume, Paarungen (Matchings), Flüsse, Zusammenhang, Färbungen, Zufällige Graphen, Ramseytheorie, Extremale Graphen, Expandergraphen, Regularitätslemma, Gleichgewichtsgraphen (Spieltheorie), Planarität, Vertiefungen und Ergänzungen.

Weitere Voraussetzungen:

In Informatik: Grundmodule Mathematik A-C. In Mathematik: Module Analysis I, II und Lineare Algebra I, II.

Prüfungsleistung:

Abschließende schriftliche Klausur.

Die Hausaufgaben gehen zur Verbesserung der Modulnote nach bestandener Klausur ein. Im zweiten Prüfungszeitraum erfolgt bei geringen Teilnehmerzahlen statt einer schriftlichen Klausur eine mündliche Prüfung. Die Hausaufgaben werden wie oben berücksichtigt.

Lehr- und Lernmethoden:

Lösen von Übungsaufgaben, Präsentation von Lösungen, Korrektur in Anwesenheit.

Verwendbarkeit:

Als Vorbereitung einer Bachelorabschlussarbeit oder als einführende Grundlage für Masterstudiengänge.

Literatur:

Skript zur Vorlesung, weitere Literatur wird in der Vorlesung bekannt gegeben.

Verweise:

Kommentar:

Das Modul wurde bis zum Wintersemester 2010/11 mit 8 Leistungspunkten als Bachelorwahlpflichtmodul angeboten.

Dieses Modul kann auch im Wahlpflichtbereich des Bachelorstudiengangs Informatik gehört werden.