URL:         /axel/disc_ss05_blatt4.html
 

Aufgabe 7- Taillenweite
Unter der Taillenweite eines ungerichteten Graphen versteht man die kürzeste Kreislänge. Gibt es keinen Kreis (Graph = Baum) dann definieren wir Taillenweite als unendlich. 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, kein Baum und planar mit n Knoten und m Kanten, die Taillenweite sei >= g, mit g>=3. 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

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 C, Mathe für Wirtschaftler, Wirtschaftler)              
(Professor D, Informatik 1, Anfänger)                                         
(Professor D, Informatik 3, Hauptstudium)                                    
 

Wieviele Zeitblöcke werden benötigt?