URL:         /axel/graph_ws0001_blatt3.html
 

Aufgabe 7- Taillenweite - (4 Punkte)
Unter der Taillenweite eines ungerichteten Graphen versteht man die kürzeste Kreislänge. Eine Kante (x,y) heisst Brücke, wenn nach ihrem Entfernen x und y in verschiedenen Zusammenhangskomponenten liegen. Beweisen Sie folgenden Satz

G sei zusammenhängend, planar mit n Knoten und m Kanten, die Taillenweite sei >= g. Dann gilt:

m <= g(n-2)/(g-2)

Tipp: Induktion nach n. Warum wurde Brücke definiert? Vielleicht ist die Eulerformel nützlich.
 

Aufgabe 8 - Graphfärben und Stundenplan -  (4 Punkte)

Um die Anzahl der benötigten Zeitblöcke zu optimieren betrachte folgendes Stundenplanproblem und löse es durch Knotenfärbung:

(Professor A, Analysis, Anfänger)                                                  (Professor E, Programmieren in C, 3. Semester)
(Professor A, Complexe Analysis, Hauptstudium)                         (Professor E, Computer Algebra, Hauptstudium)
(Professor B, Lin Algebra, Anfänger)                                               (Professor F, Differentialgleichungen, Hauptstudium)
(Professor B, Algebra, Hauptstudium)                                              (Professor F, Analysis 3, 3. Semester)
(Professor C, Numerik, 3. Semester)                                                 (Professor G, Stochastik,  3. Semester)
(Professor C, Mathe für Wirtschaftler, Wirtschaftler)                     (Professor G, Stochastik für Wirtschaftler, Wirtschaftler)
(Professor D, Informatik 1, Anfänger)                                               (Professor H, Funktionentheorie, Hauptstudium)
(Professor D, Informatik 3, Hauptstudium)                                        (Professor H, Algebraische Geometrie, 3. Semester)
 

Wieviele Zeitblöcke werden benötigt?