Graphen & Algorithmen - Interaktive Studienpläne der TU Ilmenau

Elementare Algebra im Umfang einer Vorlesung Grundlagen und diskrete Strukturen oder Lineare Algebra 1

Die Studierenden kennen nach der Vorlesung typische Berechnungsprobleme und Algorithmen zu deren Lösung, wissen diese zu beschreiben. Sie haben dadurch auch grundlegende Kenntnisse der Theorie endlicher Graphen. Nach den Übungen sind sie fähig, die o. g. Kenntnisse zur Lösung einfacher anwendungsnaher Probleme einzusetzen, andererseits können sie die in der Vorlesung verwendeten Beweistechniken anwenden.

I. Bäume (Breitn- und Tiefensuchbäume, Spannbäume minimalen Gewichts)
II. Matchings (Sätze von Hall und Berge, Tuttes Faktorsatz)
III. Zusammenhang (Max-Flow-Min-Cut-Theorem, Sätze von Menger)
IV. Färbungen (Sätze von Brooks und Vizing, Komplexität von Färbungsproblemen)

Die Inhalte können abhängig vom Dozenten variieren: Das Grundthema lässt hier ungeheuer viel Spielraum.

Tafel

Einschlägige Lehrbücher z.B. von Diestel, Bondy/Murty, Aigner, Korte/Vygen, Schrijver