Graphentheorie, HT07

Vorlesung Graphentheorie - HT07


Die Vorlesung Graphentheorie im Herbsttrimester 2007 wird von Prof. Dr. Peter Hertling gehalten und findet zu den folgenden Zeiten statt:

Di. 15.00 - 16.30 Uhr, Hörsaal 1431

Materialien zur Vorlesung wie z.B. Folien werden jeweils kurz vor oder nach der Vorlesung auf dem Dokumentenserver der Universität der Bundeswehr München bereitgestellt, und zwar hier:

Dokumente zur Vorlesung Graphentheorie
Auf dem Dokumentenserver werden auch die Übungsblätter bereitgestellt.

Es folgen Hinweise auf Korrekturen und Änderungen, die in den Folien nach dem ersten In-Netz-Stellen oder an den Übungsblättern nach dem Austeilen vorgenommen worden sind.
  • 02.10.2007:
    • Auf dem ersten Übungsblatt musste in Aufgabe 2 ein Fehler korrigiert werden: die Inzidenzmatrix wurde für gerichtete Graphen nur definiert, wenn diese schlingenfrei sind.
  • 09.10.2007:
    • Die Nummerierung wurde korrigiert: das bisherige Kapitel 2 ist tatsächlich Kapitel 1. Auf dem zweiten Übungsblatt muss in Aufgabe 6 auf Satz 2.16 verwiesen werden.
    • In Definition 1.1 muss es nicht Tripel, sondern Quadrupel heißen, und die Kantenmenge sollte nicht mit E, sondern mit K bezeichnet werden.
    • Im Beweis von Folgerung 1.7 ist U nicht Teilmenge von G, sondern von V.
    • Im zweiten Teil von Definition 1.10 muss es G[K'] heißen.
    • Auf der Folie nach Definition 1.11 musste das erste Vorkommen von "gerichtete" durch "ungerichtete" ersetzt werden.
    • Auf der Folie, in der der Grad einer Ecke in einem ungerichteten Graphen definiert wird, musste die Titelzeile korrigiert werden. Außerdem musste in der Formel eine Klammer ergänzt werden und in der Zeile nach der Formel ein k durch v ersetzt werden.
    • Auf den Folien 1, 5 und 7 in Abschnitt 1.3 "Darstellung von Graphen im Computer" sollten Mengenaufzählung mit einer schließenden Mengenklammer enden, nicht mit einer runden Mengenklammer.
    • In der Folie im Anschluss an die Definition der Adjazenzmatrix wurde ergänzt, dass die Adjazenzmatrix eines schlichten Graphen in der Diagonale nur Nullen enthält.
    • In Definition 1.15 wurde "Endecke" des Weges durch "Zielecke" des Weges ersetzt.
    • Am Ende des Kapitels 1 wurden zwei Folien zum Berechnungsmodell ergänzt.
  • 17.10.2007:
    • Die Definitionen eines einfachen Weges in einem gerichteten und in einem ungerichteten Graphen in Definition 2.2 mussten korrigiert werden.
    • Der erste Satz im Beweis von Folgerung 2.25 musste korrigiert werden.
    • Da der Graph in Satz 2.28 ungerichtet ist, musste in seiner Beschreibung "alpha,omega" durch "gamma" ersetzt werden.
  • 30.10.2007:
    • Auf der zweiten Folie mit dem Titel "Datenstruktur für eine Implementierung des Algorithmus von Kruskal" war die Beschreibung der Zeigerstruktur fehlerhaft. Entsprechend musste auch die Beschreibung der union-Operation auf der darauffolgenden Folie korrigiert werden.
    • In der Definition eines Teilmengensystems in Definition 3.13 musste zweimal M durch E ersetzt werden.
    • In Beispiel 3.14 musste ein S durch E ersetzt werden.
    • In Satz 3.15 muss A Teilmenge von K sein, nicht von V.
  • 08.11.2007:
    • In Satz 3.7 kann man statt n größer-gleich 2 auch n größer-gleich 1 annehmen.
    • In Definition 3.27 muss es ``alpha-Approximationsalgorithmus'' heißen
    • Ein Tippfehler in der dritten Titelzeile der ersten Folie von Abschnitt 3.5 wurde korrigiert. Auf der folgenden Folie wurde ein überflüssiges Wort entfernt.
    • Im Beweis von Satz 3.28 musste es einmal ``alpha-Approximationsalgorithmus'' statt c-Approximationsalgorithmus'' heißen.
    • Vor Lemma 3.33 musste einmal w(E) durch w(S) ersetzt werden.
    • In Bemerkung 3.34 und Bemerkung 3.35 musste jeweils einmal ``für i=2,...,n'' gestrichen werden.
    • Im Beweis von Satz 3.36 muss bei der Behandlung des zweiten Falls die Menge {1,...,k-1} nur eine Teilmenge von S_1 sein, nicht gleich S_1 sein.
  • 21.11.2007:
    • Die Formulierung von Lemma 4.11 musste korrigiert werden.
    • In den Definitionen 5.3, 5.4 und 5.5 sowie in Satz 5.7 und seinem Beweis ist die Vokabel ''Gewichtsfunktion'' durch ''Kantenbewertung'' ersetzt worden.
  • 26.11.2007:
    • In Satz 3.15 und seinem Beweis musste wiederholt anstelle von (V,K) etc. (V,K,\gamma) etc. geschrieben werden.
    • Auf der dritten Folie von Beispiel 4.10 wurden in Zeile 2 ein Komma und in der letzten Zeile das Wort "ist" ergänzt.
    • Auf der Folie nach Lemma 4.20 musste einmal strongzshgkomp[v] durch starkezsghkomp[v] ersetzt werden.
    • Im Beweis von Lemma 5.13 wurde eine Ergänzung vorgenommen.
    • In der formalen Formulierung des Algorithmus von Dijkstra musste die Nummerierung der Programmzeilen korrigiert werden.
    • Ebenso in der Formulierung des Algorithmus von Bellman und Ford. Außerdem musste in der for-Schleife ab Zeile 5 des Programms mehrmals v durch u und und w durch v ersetzt werden.
    • Lemma 5.16 bezieht sich auf die in Zeile 4 beginnende for-Schleife, nicht auf die in Zeile 2 beginnende for-Schleife. Am Ende des Beweises von Lemma 5.16 musste ein =-Zeichen durch <= ersetzt werden.
    • In Satz 5.17.2 wurde "Vorgaenger" durch "Vorgänger" ersetzt.
    • Zwei Zeilen vor Satz 5.19 musste dist_c(s,v) durch dist_c(u,v) ersetzt werden.
    • Auf der folgende Folie wurde zweimal das Wort "aus" entfernt.
    • Der Algorithmus von Floyd musste korrigiert werden.
    • In Satz 5.20 mussten einmal eckige Klammern durch runde Klammer ersezt werden.
    • In Bemerkung 5.21 wurde die Vokabel "bekannten" durch "sogenannten" ersetzt.
    • Im Beweis von 5.23 musste in der letzten Gleichung plus und minus vertauscht werden. Außerdem wurde in dem Beweis ein Argument ergänzt.
  • 28.11.2007:
    • Im Beweis von Satz 5.20 wurde die erste Formel in der Zeitabschätzung geändert.
    • Im Beweis von Satz 5.23 mussten die Zeitangabe für die n-malige Anwendung des Algorithmus von Dijkstra auf der ersten Seite und die Formel für den gesamten Zeitaufwand ganz am Ende korrigiert werden. Außerdem musste es auf der zweiten Folie nicht "c_neu(P) :=..", sondern "c_neu(P) = ..." heißen.
    • In Definition 6.16 sollte einmal V_k durch C_k ersetzt werden.
    • In Satz 6.25 musste vor "Färbungsalgorithmus" ergänzt werden: "in Polynomzeit arbeitenden". Außerdem musste die Formulierung des Textes vor Satz 6.25 korrigiert werden.
  • 28.11.2007:
    • In Definition 6.1 und in Definition 6.9 musste jeweils ein E durch ein K ersetzt werden.
    • In Definition 6.4 musste ein C entfernt werden.
    • In Beispiel 6.20.2 müssen Kreise mit mindestens fünf statt drei Ecken betrachtet werden.
    • In Definition 6.21 und Satz 6.22, sowie seinem Beweis musste überall anstelle des Minimalgrads deg_min der Maximalgrad deg_max stehen.
    • Im Beweis von Satz 6.27 wurden Fehler korrigiert.
  • 11.12.2007:
    • In Definition 6.16 musste max durch min ersetzt werden.
    • Der Graph in Beispiel 6.23 sollte ungerichtet sein.
    • In der Folie zu den Gebieten einer planaren Grapheinbettung (Folie 9 in Kapitel 7) fehlte eine Variable k in der Defintion von P(Gamma).
    • Die zweite Aussage von Lemma 8.9 und ihr Beweis mussten korrigiert werden.
    • Der Beweis von Satz 8.13 musste korrigiert werden.
  • 12.12.2007:
    • Die Definition des Randes einer Menge vor Satz 7.8 musste korrigiert werden.
    • In Satz 7.20 fehlte ein "nicht".

Übungen


Die Übungen werden von Herrn Dr. Christoph Spandl betreut. Termin und Raum:

Di. 12.15 - 13.00 Uhr, Raum 3101


Prüfung


Die Vorlesung Graphentheorie wird im Rahmen der Klausur am 07.01.2008 zum Anwendungsfach Mathematik und Angewandte Systemwissenschaften geprüft.


Letzte Änderung: 12. Dezember 2007