1. Deutsch
  2. English

Modulbeschreibung

Graphentheorie und Optimierung

Lehrveranstaltungen:

TitelTypSWSZeitraum
Graphentheorie und OptimierungVorlesung2Sommersemester
Graphentheorie und OptimierungGruppenübung2Sommersemester

Modulverantwortlich:

Prof. Anusch Taraz

Zulassungsvoraussetzungen:

Keine

Empfohlene Vorkenntnisse:

Modulziele / angestrebte Lernergebnisse:

Fachkompetenz

Wissen
Fertigkeiten

Personale Kompetenzen

Sozialkompetenz
Selbstständigkeit

Leistungspunkte Modul:

6 LP

Studienleistung:

Klausur

Arbeitsaufwand in Stunden:

Eigenstudium: 124, Präsenzstudium: 56


Lehrveranstaltung: Graphentheorie und Optimierung

Dozent:

Anusch Taraz

Sprache:

Deutsch & Englisch

Zeitraum:

Sommersemester

Inhalt:

  • Graphen, Durchlaufen von Graphen, Bäume
  • Planare Graphen
  • Kürzeste Wege
  • Minimale Spannbäume
  • Maximale Flüsse und minimale Schnitte
  • Sätze von Menger, König-Egervary, Hall
  • NP-vollständige Probleme
  • Backtracking und Heuristiken
  • Lineare Programmierung
  • Dualität
  • Ganzzahlige lineare Programmierung

Literatur:

  • M. Aigner: Diskrete Mathematik, Vieweg, 2004
  • T. Cormen, Ch. Leiserson, R. Rivest, C. Stein: Algorithmen - Eine Einführung, Oldenbourg, 2013
  • J. Matousek und J. Nesetril: Diskrete Mathematik, Springer, 2007
  • A. Steger: Diskrete Strukturen (Band 1), Springer, 2001
  • A. Taraz: Diskrete Mathematik, Birkhäuser, 2012
  • V. Turau: Algorithmische Graphentheorie, Oldenbourg, 2009
  • K.-H. Zimmermann: Diskrete Mathematik, BoD, 2006

Leistungspunkte Lehrveranstaltung:

6 LP