Graphentheorie
Dr. Theresia Eisenkölbl
Lehrveranstaltungsnummer: 250310+250311
Lehrveranstaltungstyp: VO+PS
Stundenzahl: 3+1
Zeit und Ort: Mo-Do, 11.05-11.50h, Seminarraum D1.01 (Nordbergstraße 15)
Beginn: Mi, 1. März 2006
Informationen zur Lehrveranstaltung:
Ein Graph besteht aus einer Menge V von Ecken und einer Teilmenge von
V×V von Kanten. Aus dieser
einfachen Definition ergeben sich viele Fragen und Anwendungen.
- Wie finde ich den kürzesten Weg zwischen zwei Ecken in einem Graphen?
- Wieviele Graphen mit bestimmten Eigenschaften gibt es?
- Mit wievielen Farben kann eine Landkarte gefärbt werden?
- Wie findet eine Briefträgerin die optimale Route durch ihren
Bezirk?
- Ist es möglich, den Graphen oben links so zu zeichnen, dass sich
keine Kanten überschneiden?
- Wieviele Fünfecke hat ein Fußball und warum?
- Ist es möglich, auf einem Rundweg
jede Ecke im Graphen oben rechts genau einmal zu durchlaufen?
In der Vorlesung werden grundlegende Begriffe und Sätze der
Graphentheorie vorgestellt, die auch Antworten auf die obigen
Fragen liefern.
Behandelt werden unter anderem Pfade, Kreise, Bäume, Adjazenzmatrizen,
Färbungen, Flüsse und Matchings.
Diese Vorlesung benötigt keine speziellen Vorkenntnisse.
Literatur
- Diestel: Graphentheorie, Springer, 2000
- Bondy, Murty: Graph Theory with Applications, Elsevier, 1976
- Bollobas: Modern graph theory, Springer 1998
- Behzad, Chartrand, Lesniak-Foster: Graphs & Digraphs, Wadsworth, 1979
Zurück zur Lehre
Zurück zur Startseite
e-mail: