Lehrveranstaltungshandbuch Graphentheorie

---

Verantwortlich: Prof. Dr. Hubert Randerath

Lehrveranstaltung

Befriedigt Modul (MID)

• aktuelle
  • Ba TIN2012 GRT

Organisation

Version erstellt 2012-04-23 VID 1 gültig ab SS 2013 gültig bis

Bezeichnung Lang Graphentheorie LVID F07_GRT LVPID (Prüfungsnummer)

Semesterplan (SWS) Vorlesung 2 Übung (ganzer Kurs) 1 Übung (geteilter Kurs) Praktikum 1 Projekt Seminar Tutorium (freiwillig)

Präsenzzeiten Vorlesung 30 Übung (ganzer Kurs) 15 Übung (geteilter Kurs) Praktikum 15 Projekt Seminar Tutorium (freiwillig)

max. Teilnehmerzahl Übung (ganzer Kurs) Übung (geteilter Kurs) Praktikum 18 Projekt Seminar

Gesamtaufwand: 150

Unterrichtssprache

• Deutsch

Niveau

• Bachelor

Notwendige Voraussetzungen

• Mathematisches Grundlagenwissen
• Grundlagenwissen der Praktischen Informatik
• Grundlagenwissen über Algorithmen und Datenstrukturen

Literatur

• Diskrete Mathematik, M. Aigner, Vieweg-Verlag
• Graphentheorie, R. Diestel, Springer Verlag
• Graphentheorie, P. Tittman, Fachbuchverlag Leipzig
• Graphen an allen Eckern und Kanten, L. Volkmann, RWTH Aachen

Dozenten

• Prof. Dr. Hubert Randerath

Wissenschaftliche Mitarbeiter

• Dipl.-Math. Katharina Hammersen

Zeugnistext

Graphentheorie

Kompetenznachweis

Form
sMP	Regelfall (bei großer Prüfungszahl: sK)

Aufwand [h]
sMP	10

Intervall: 3/Jahr

---

Lehrveranstaltungselemente

Vorlesung / Übung

Lernziele

Lerninhalte(Kenntnisse)

• Grundlagen der Kombinatorik und Asymptotische Analyse: Kombinatorische Grundprinzipien, Elementare Zählprinzpien, Permutationen, Variationen und Kombinationen, Prinzip der Inklusion und Exklusion, Wachstum von Funktionen, Laufzeit von Algorithmen, Komplexitätsklassen.
• Grundlagen der Graphentheorie: Definition Graph, vollständige und bipartite Graphen, Isomorphie von Graphen, Adjazenz- und Inzidenzmatrix, Wege und Kreise, Zusammenhang von Graphen, gerichtete Graphen; Wälder, Bäume, Elementare Graphenparameter. 
• Traversierung in Graphen und das kürzeste Wege Problem: Breitensuche, Tiefensuche, Topologische Sortierung, Eulertouren, Hamiltonkreise, Dijkstra-Algorithmus, Bellman-Ford-Algorithmus.
• Matchings und Flüsse: Matchings, Ungarische Methode, Edmonds-Algorithmus, Netzwerke, Flüsse, zuässige Flüsse, Max-Flow-Min-Cut, Ford-Fulkersen-Algorithmus, Edmonds-Karp-Algorithmus..
• Färbungen:  Knotenfärbungen, Kantenfärbungen, Listenfärbungen, Turniere und Spielpläne, Planare Graphen, Vier-Farben-Satz, Perfekte Graphen, Färbungsalgorithmen. 

Fertigkeiten

• Die Studierenden beherrschen grundlegende Kenntnisse über Graphen und Algorithmen
• Sie sind in der Lage Verfahren und Konzepte der Graphentheorie zur Beschreibung und algorithmischen Lösung von Problemstellungen der Informatik, der Technik und des täglichen Lebens anzuwenden. 

Begleitmaterial

• elektronische Vortragsfolien zur Vorlesung
• elektronische Übungsaufgabensammlung

Besondere Voraussetzungen

Besondere Literatur

Besonderer Kompetenznachweis

Form
bÜA	Präsenzübung

Beitrag zum LV-Ergebnis
bÜA	unbenotet

Intervall: 1/Jahr

Praktikum

Lernziele

Lerninhalte(Kenntnisse)

• Grundlagen: Graphentheorie mit Maple
• Ausgewählte Graphenalgorithmen mit Maple

Fertigkeiten

• Die Studierende sind in der Lage einfache graphentheoretische Probleme mit Maple zu lösen

Begleitmaterial

• elektronisches Entwicklungswerkzeug: MAPLE
• elektronisches Tutorial: praktikumsspezifische Einführung in Maple

Besondere Voraussetzungen

Besondere Literatur

• Exploring Discrete Mathematics with Maple, Kenneth Rosen (McGraw-Hill Verlag)

Besonderer Kompetenznachweis

Form
bSZ	Präsenzübung

Beitrag zum LV-Ergebnis
bSZ	unbenotet; Voraussetzung für die mündliche Prüfung

Intervall: 1/Jahr