Übungen

Übung 1

Wir betrachten den folgenden Graphen:

Konstruieren Sie mit Hilfe des Algorithmus von Hierholzer einen Euler-Zug für diesen Graphen.

Übung 2

Wir betrachten die 21 Steine eines Dominospiels, die jeweils zwei verschiedene Werte 0, …, 6 besitzen. Das Dominoproblem lautet : Lassen sich die Steine in einer geschlossenen Kette anordnen, sodass Berührungen nur bei gleicher Zahl erlaubt sind? Modellieren und untersuchen Sie dieses Problem graphentheoretisch. Geben Sie im Falle der Existenz eine konkrete Lösung an. Für welche n gibt es eine Lösung, wenn allgemeiner die Werte 0, 1, …, n statt 0, …, 6 zugelassen sind?

Übung 3

Konstruieren Sie einen Graphen G = (E, K) und einen geschlossenen einfachen Kantenzug Z = a₀, …, a_n, a₀ in G derart, dass für alle i, j der Kantenzug a_j, …, a_n, a₀, …, a_i kein Kreis ist. (Dieser Graph zeigt, dass aus einem geschlossenen einfachen Kantenzug im Allgemeinen kein Kreis in einem Schritt herausgeschnitten werden kann, der eine gegebene Ecke besucht.)

Übung 4

Wie ändern sich die Ergebnisse und Algorithmen über Euler-Züge, wenn wir Mehrfach-Verbindungen zwischen den Ecken zulassen?

Übung 5

Wir betrachten nun gerichtete Graphen, bei denen eine Kante ab von ba zu unterscheiden ist (in Diagrammen durch einen Pfeil dargestellt). Alle graphentheoretischen Grundbegriffe sind in natürlicher Weise definiert. Beim Grad einer Ecke unterschieden wir nun den Ausgangsgrad d⁺(a) und den Eingangsgrad d⁻(a) einer Ecke a:

d⁺(a)  =  | { b  ∈  E | ab  ∈  K } |,  d⁻(a)  =  | { b  ∈  E | ba  ∈  K } |.

Sei nun G = (E, K) ein zusammenhängender gerichteter Graph, d. h. für alle Ecken a, b gibt es einen gerichten Kantenzug von a nach b und einen gerichteten Kantenzug von b nach a. Zudem gelte d⁺(a) = d⁻(a) für alle Ecken a (Eingangsgrad gleich Ausgangsgrad). Zeigen Sie, dass der für gerichtete Graphen angepasste Algorithmus von Hierholzer einen Euler-Zug produziert.

Übung 6

Beweisen Sie den Satz über den zweifachen Kantenbesuch mit Hilfe der vorangehenden Übung durch Übergang zu einem gerichteten Graphen.

Übung 7

Beweisen Sie den Satz über den zweifachen Kantenbesuch, indem Sie zeigen, dass der folgende Labyrinth-Algorithmus einen geschlossenen Kantenzug produziert, der jede Kante genau zweimal in unterschiedlichen Richtungen durchläuft.

Vorbemerkung: Bei der Durchführung des Verfahrens sind Kanten ab entweder gar nicht oder mit einem gelben oder mit einem roten Pfeil von a nach b markiert (sodass für die Markierung ab von ba zu unterscheiden ist). Rot bedeutet: Die Kante darf in Pfeilrichtung nicht durchlaufen werden. Gelb bedeutet: Durchlaufe die Kante in Pfeilrichtung erst dann, wenn es keine unmarkierten Optionen mehr gibt.

Wir starten mit einer beliebigen Kante a₀a₁ und dem Kantenzug a₀, a₁. Weiter markieren wir die Kante a₀a₁ rot. Ist ein Kantenzug a₀, …, a_n konstruiert und wird dabei a_n zum ersten Mal besucht, so markieren wir die Kante a_na_n − 1 gelb. Gibt es eine unmarkierte Kante mit a_n als Ausgangsecke, so gehen wir eine solche Kante. Andernfalls gehen wir von a_n entlang der gelb markierten Kante. Dieser Schritt liefert die nächste Ecke a_n + 1. Schließlich markieren wir wir a_na_n + 1 nun rot. Wir wiederholen nun das Verfahren solange, bis alle Kanten rot markiert sind.

Übung 8

Überprüfen Sie die Vermutung von Szekeres und Seymour an einigen selbstgewählten Beispielen. Informieren Sie sich in der Fachliteratur oder im Internet über den Stand der Vermutung (engl. cycle double cover conjecture).

Übung 9

Beweisen Sie den Satz von Dirac wie folgt:

Betrachten Sie einen nach links und rechts nicht mehr verlängerbaren Weg W = a₀, …, a_n in G. Zeigen Sie, dass es ein i < n gibt derart, dass

C  =  a₀, …, a_i, a_n, a_n − 1, …, a_i + 1, a₀

ein Kreis in G ist. Zeigen Sie nun mit Hilfe der Reichhaltigkeitsbedingung: Ist a  ∈  E eine auf C nicht besuchte Ecke, so gibt es ein j derart, dass aa_j eine Kante von G ist. Gewinnen Sie hieraus einen Weg, der länger ist als W und vollständigen Sie den Beweis durch Wiederholung des Verfahrens.