Technische Universität München, Fakultät für Informatik

Graphentheorie: Theorie der Relationen

Dr. Thomas Ströhlein

Bereich: Informatik III, VO (2), sonstige Vorlesungen

Die Vorlesung kann für Studierende der Informatik mit Nebenfach Mathematik als Mathematik-Vorlesung im Teilbereich B angegeben werden; Studierende der Informatik mit anderem Nebenfach müssen für eine Prüfung im Bereich Informatik III einen gesonderten Antrag stellen. (Die Professoren W. Brauer und E. Mayr haben sich bereit erklärt zu prüfen.)

Die Vorlesung vermittelt die Fähigkeit relationale Beziehungen formal zu beschreiben und ihre algebraischen und verbandstheoretischen Eigenschaften zu beherrschen und auszunutzen.

Inhalt: (ohne Punkt 5. falls 2stündig, 1semestrig):

1. Algebra der Relationen
Boolesche Operationen auf Relationen; Transposition von Relationen; Produkt von Relationen

2. Heterogene Relationen
Funktionen und Abbildungen; Eindeutiger und mehrdeutiger Anteil; Difunktionalität; 1-stellige Relationen: Punkte und Teilmengen

3. Homogene Relationen
Ordnungen und Äquivalenzen; Hüllenbildungen und Hasse-Diagramme; Terminierende Erreichbarkeit und Initialteil; Konfluenz und Church-Rosser-Theoreme; Extrema, Schranken und Grenzen

4. Fixpunktsätze und Antimorphie
Fixpunkte einer isotonen Abbildung; Fixpunkte eines Paars antitoner Abbildungen; Anwendungen auf Relationen: Initialteil, (Satz von König)

5. Einige Phänomene heterogener Relationen
Konformität und Faktorisierungssätze; Sternförmigkeit und Satz von Gallai; Struktur- und Darstellungsfragen

Hörerkreis: alle Fachrichtungen; ab 5. Semester (ab 3. Semester möglich)

Voraussetzungen: keine

Einführende und begleitende Literatur:


Thomas Ströhlein, 1997-01-07, 1997-01-07