Lehrveranstaltungshandbuch Graphentheorie


Verantwortlich: Prof. Dr. Hubert Randerath

Lehrveranstaltung

Befriedigt Modul (MID)

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

Diese Seite läuft auf FoswikiDas Urheberrecht © liegt bei den mitwirkenden Autoren. Alle Inhalte dieser Kollaborations-Plattform sind Eigentum der Autoren.
Ideen, Anfragen oder Probleme bezüglich Foswiki? Feedback senden