Graphentheorie Klausur vom 06.07.2009 (Uni Köln)

Aufgabe 1 (9 Punkte, Graphenzeichnung)

Zeichnen Sie den aus der Vorlesung bekannten

• Dedekahedron Graphen und den
• gerichteten De Bruijn Graphen

Aufgabe 2 (15 Punkte, Graphenkrimi)

Sei ein Graph (ohne Schlingen und Mehrfachkanten) mit 18 Knoten und höchstens 24 Kanten, welcher aus drei Zusammenhangskomponenten , und mit folgenden Eigenschaften besteht:

• ist eulersch, hamiltonsch, bipartit und enthält einen Weg mit vier Knoten als induzierten Teilgraph,
• ist ein Baum und {000000,000001,000010,000110,001010,011010,101010} ist eine zugehörige Menge Binäradressen der Knoten, so daß die Distanz je zweier Knoten aus gleich der Hammingdistanz der zugehörigen Adressen ist und
• die Cliquenzahl .

Geben Sie bis auf Isomorphie alle Graphen an, die diese Eigenschaften erfüllen.

Aufgabe 3 (15 Punkte, Knotenfärbung)

Der in der Vorlesung präsentierte Beweis des Theorems von Brooks liefert ein algorithmisches Verfahren um in einem 2-zusammenhängenden Graphen , der weder Kreis noch ein vollständiger Graph ist, eine -Knotenfärbung zu bestimmen. Wenden Sie dieses algorithmische Verfahren auf das folgende Beispiel an und beschreiben Sie ihre Herangehensweise.

Aufgabe 4 (15 Punkte, Maximaler Fluss)

Geben Sie zu dem gegebenen Netzwerk einen maximalen Fluss an und begründen Sie die Maximalität des Flusses.

Netzwerk mit Quelle , Senke und Kapazitätsfunktion

Aufgabe 5 (15 Punkte, Digraphenkrimi)

Sei ein gerichteter Graph ohne Schlingen, ohne Mehrfachkanten und ohne orientierte Kreise der Länge zwei mit 14 Knoten und 19 gerichteten Kanten. Der zugrundeliegende ungerichtete Graph, der nach Entfernen aller Orientierungen entsteht, enthält drei Zusammenhangskomponenten. Wir bezeichnen die korrespondierenden disjunkten gerichteten Graphen aus denen sich zusammensetzt mit , und . Diese erfüllen folgende Eigenschaften:

• ist hamiltonsch und besitzt mindestens einen Knoten mit ,
• ist eulersch und enthält genau zwei starke Zusammenhangskomponenten und
• besitzt mindestens einen Knoten mit und enthält keine Knoten und mit .

Geben Sie bis auf Isomorphie alle gerichteten Graphen an, die diese Eigenschaften erfüllen.

Aufgabe 6 (15 Punkte, Planare Graphen)

• Geben Sie ein Beispiel für einen planaren Graphen an, der nicht kreisplanar ist (Mit kurzer Begründung!).
• Beschreiben Sie die Aussage der Eulerschen Polyederformel.
• Beweisen Sie die Eulersche Polyederformel!

Aufgabe 7 (16 Punkte, Spielplan-Entwurf)

Sie werden von Herrn Dr. Fußbroichs, dem Geschäftsführer der DFL (Deutsche Fußpflege Liga), beauftragt einen Spielplan für die kommende Saison zu entwerfen. Jede Mannschaft spielt innerhalb der Saison gegen jede andere Mannschaft genau einmal. An einem Spiel sind genau zwei Mannschaften beteiligt. Die folgenden Mannschaften nehmen an der Meisterschaft teil: FC Zeh (FCZ), Dynamo Feile (DF), TUS Schere (TUS), Hansa Pflaster (HP), Pflegefreunde Siegen (PFS), Turbine Podologieski (TP) und Thick Uncles United (TUU). Entwerfen Sie einen Spielplan für die DFL-Saison basierend auf algorithmischen Ideen der Vorlesung. (Hinweis: Es ist erlaubt die einzelnen kompletten Spieltage durch eine Zeichnung zu repräsentieren!)

Aufgabe 8 (20 Punkte, Strukturaussage)

Sei ein zusammenhängender Graph (ohne Schlingen und Mehrfachkanten) mit Knoten, welcher keinen Weg mit fünf Knoten als induzierten Teilgraphen enthält. Zeigen Sie, dass in mindestens ein Knoten mit Knotengrad existiert.

(Hinweis: Die Strukturaussage der Vorlesung über -freie Graphen sollte ausgenutzt werden. Sie besagte, dass jeder zusammenhängende Graph , der keinen Weg mit fünf Knoten als induzierten Teilgraphen enthält, eine Knotenteilmenge besitzt, die eine Clique oder einen Weg mit drei Knoten induziert, sodass jeder Knoten aus – mindestens einen Nachbarknoten in besitzt.)