Übungen

Übung 1 (Endliche Graphen, I)

Sei G = (E, K) ein Graph. Sei U = { a  ∈  E | d(a) ist ungerade }.

Zeigen Sie, dass |U| eine gerade Zahl ist.

Übung 2 (Endliche Graphen, II)

Ein Graph G = (E, K) heißt planar, wenn er in der Ebene so gezeichnet werden kann, dass sich keine Kanten überschneiden. Für einen planaren Graphen sei e die Anzahl der Ecken, k die Anzahl der Kanten und f die Anzahl der Flächen, wobei die äußere Fläche mitzählt. (Z. B. hat ein Graph in der Form einer Acht drei Flächen.)

Zeigen Sie, dass für jeden planaren Graphen gilt:

e − k + f = 2. (Eulersche Polyederformel)

[ Wir beweisen die Aussage zuerst für Graphen mit f = 1. Die allgemeine Aussage beweisen wir dann durch Induktion nach f. ]

Folgern Sie, dass es nur 5 regelmäßige konvexe Polyeder im ℝ³ gibt (die Platonischen Körper): ein Tetraeder mit 4, einen Kubus mit 6, ein Oktaeder mit 8, ein Dodekaeder mit 12, und ein Ikosaeder mit 20 Flächen. (Dabei heißt ein P ⊆ ℝ³ konvex, falls für alle a, b  ∈  P die Strecke von a nach b eine Teilmenge von P ist.)

[ Seien e, k, f die Anzahl der Ecken, Kanten, Flächen eines Polyeders. Für ein regelmäßiges Polyeder sei n die Zahl der Kanten einer Fläche und d der Grad der Ecken. Begründen Sie, dass die Eulersche Polyederformel gilt, und folgern Sie für regelmäßige Polyeder die Beziehung

(+) 1/n + 1/d = 1/2 + 1/k,

die sich aus der Eulerschen Polyederformel und nf = 2k, de = 2k ergibt. Bestimmen Sie die möglichen Lösungen von (+) mit n ≥ 3 und d ≥ 3, nämlich

(n, d, k) = (3, 3, 6), (3, 4, 12), (3, 5, 30), (4, 3, 12), (5, 3, 30).

Beobachten Sie hierzu, dass n ≤ 3 oder d ≤ 3 gelten muss, falls (+) mit positiven Zahlen (n, d, k) erfüllt wird. ]

Übung 3 (Endliche Graphen, III)

Zeigen Sie:

(a)	Ist f : G₁ → G₂ ein Isomorphismus zwischen zwei Graphen, so gilt d_G₁(a) = d_G₂(f (a)) für alle a  ∈  E₁.

(b)	Skizzieren Sie alle Graphen für die Eckenmenge E = { 1, 2, 3 }. Welche dieser Graphen sind isomorph? Welche Graphen sind aus welchen Gründen nicht isomorph?

(c)	Geben Sie zwei nichtisomorphe Graphen mit den Ecken { 1, …, 5 } an, sodass die Grade beider Graphen die Zahlen 2, 2, 2, 3, 3 sind.

Übung 4 (Endliche Graphen, IV)

Ein Graph G = (E, K) heißt selbstkomplementär, falls G isomorph zu seinem komplementären Graphen G^c = (E, { ab | a, b  ∈  E, a ≠ b, ab  ∉  K }) ist.

(a)	Geben Sie je einen selbstkomplementären Graphen an mit den Ecken E₁ = { 1, 2, 3, 4 } und E₂ = { 1, 2, 3, 4, 5 }.

(b)	Zeigen Sie: Ist G selbstkomplementär, so ist die Anzahl seiner Ecken durch 4 ohne Rest oder durch 4 mit Rest 1 teilbar.

Übung 5 (Kantenzüge, Wege und Kreise, I)

Sei a₀, …, a_n ein einfacher geschlossener Kantenzug in einem Graphen G.

Zeigen Sie, dass i < j ≤ n existieren, sodass a_i, a_i + 1, …, a_j ein Kreis ist.

Zeigen Sie weiter, dass für jedes a_i, i ≤ n, ein Kreis in G durch a_i existiert.

Kann hier auf die Voraussetzung „einfach“ verzichtet werden?

Übung 6 (Kantenzüge, Wege und Kreise, II)

Sei G = (E, K) ein Graph, und seien k₁, k₂, k₃  ∈  K paarweise verschieden.

Es gebe einen Kreis, der k₁ und k₂ besucht, und einen Kreis, der k₂ und k₃ besucht. Zeigen Sie, dass es einen Kreis gibt, der k₁ und k₃ besucht.

Übung 7 (Kantenzüge, Wege und Kreise, III)

Sei G = (E, K) ein Graph. Zeigen Sie, dass die folgenden Aussagen äquivalent sind:

(a) G ist bipartit. (b) Jeder Kreis in G hat eine gerade Länge.

Inbesondere ist also jeder kreisfreie Graph bipartit.

Übung 8 (Erreichbarkeit und Zusammenhang, I)

Sei G = (E, K) ein Graph, und seien a, b  ∈  E. Zeigen Sie:

Ist b erreichbar von a, so existiert ein Weg von a nach b.

Übung 9 (Erreichbarkeit und Zusammenhang, II)

Sei G = (E, K) ein Graph. Für a, b  ∈  E sei a ≡ b, falls b erreichbar von a ist.

Zeigen Sie, dass ≡ eine Äquivalenzrelation auf E ist. Genauer ist ≡ die ⊆-kleinste Äquivalenzrelation R auf E mit aRb für alle ab  ∈  K.

Übung 10 (Erreichbarkeit und Zusammenhang, III)

Sei G = (E, K) ein zusammenhängender Graph. Zeigen Sie, dass die Abstandsfunktion d : G² → ℕ eine Metrik ist, d. h. es gilt für alle a, b, c  ∈  E:

(a)	d(a, a) = 0,

(b)	d(a, b) = d(b, a),

(c)	d(a, c) ≤ d(a, b) + d(b, c).

Übung 11 (Erreichbarkeit und Zusammenhang, IV)

Sei G = (E, K) ein Graph. Zeigen Sie, dass für alle ab  ∈  K die folgenden Aussagen äquivalent sind:

(a)	ab ist eine Brücke von G.

(b)	a, b ist der einzige Weg von a nach b.

Übung 12 (Erreichbarkeit und Zusammenhang, V)

Sei G ein Graph, und jede Ecke von G habe einen geraden Grad.

Zeigen Sie, dass G keine Brücken besitzt.

Übung 13 (Erreichbarkeit und Zusammenhang, VI)

Für einen Graphen G = (E, K) sei

G^c = (E, { ab | a, b  ∈  E, a ≠ b, ab  ∉  K }),

der zu G komplementäre Graph.

Zeigen Sie, dass der Graph G^c eines unzusammenhängenden Graphen G zusammenhängend ist.

Übung 14 (Erreichbarkeit und Zusammenhang, VII)

Sei G ein zusammenhängender Graph der Ordnung n derart, dass jede Ecke von G den Grad 2 besitzt. Zeigen Sie:

G ist isomorph zum Kreis C_n.

Übung 15 (Eulerzüge, I)

Sei G ein Graph, und seien a, b verschiedene Ecken von G. Ein offener Eulerzug von a nach b in G ist ein einfacher in a beginnender und in b endender Kantenzug in G, der alle Kanten durchläuft.

Zeigen Sie, dass die folgenden Aussagen für jeden zusammenhängenden Graphen G = (E, K) und alle a, b  ∈  E, a ≠ b, äquivalent sind:

(a)	Es gibt einen offenen Eulerzug von a nach b.

(b)	Die Grade d(a), d(b) sind ungerade, und für alle c  ∈  E − { a, b } ist der Grad d(c) gerade.

Übung 16 (Eulerzüge, II)

Zeigen Sie, dass die folgenden Aussagen für jeden zusammenhängenden Graphen G = (E, K) äquivalent sind:

(a)	G ist Eulersch.

(b)	G ist die Vereinigung von Kreisen K₁, …, K_n in G mit paarweise disjunkten Kanten.

Übung 17 (Eulerzüge, III)

Sei G = (E, K) ein zusammenhängender Graph. Zeigen Sie, dass es einen geschlossenen Kantenzug gibt, der jede Kante genau zweimal durchläuft.

Übung 18 (Eulerzüge, IV)

Betrachten Sie ein Dominospiel mit Zahlenpaaren von 0, …, 6 auf den Steinen, ohne die Steine mit gleichen Zahlen. (Das Spiel hat dann also 21 Steine.) Das Dominoproblem lautet: Kann man die Steine so in einer geschlossenen Kette anordnen, dass, wie beim Domino üblich, aneinanderliegende Steine dort, wo sie sich berühren, stets die gleiche Zahl aufweisen? Klären Sie dieses Problem in der Sprache der Graphentheorie. Geben Sie im Falle der Existenz eine konkrete Lösung an. Für welche n gibt es eine Lösung, wenn auf den Dominosteinen die Zahlen 0, 1, …, n erscheinen?

Übung 19 (Eulerzüge, V)

Bestimmen Sie mit dem Algorithmus von Hierholzer einen Eulerzug für den folgenden Graphen:

Übung 20 (Eulerzüge, VI)

Was findet der Algorithmus von Hierholzer, wenn er auf einen nicht notwendig zusammenhängenden Graphen angewendet wird, dessen Ecken alle einen geraden Grad haben? Was kann passieren, wenn der Algorithmus auf einen beliebigen Graphen angewendet wird?

Übung 21 (Erkundung eines Labyrinths, I)

Wie verläuft der Erkundungsalgorithmus, wenn die Startkante 0 1 in einen Kreis C_n hineinführt?

Übung 22 (Erkundung eines Labyrinths, II)

Führen Sie den Erkundungsalgorithmus für den folgenden Graphen durch. Wählen Sie dabei im Falle mehrerer möglicher nächster Ecken immer die kleinste mögliche Ecke.

Übung 23 (Hamiltonkreise, I)

Zeigen Sie, dass die Graphen der fünf regelmäßigen Platonischen Körper aus Übung 2 Hamiltonsch sind.

Übung 24 (Hamiltonkreise, II)

Sei G = (E, K) ein Graph der Ordnung n* mit d(a) ≥ n*/2 für alle a  ∈  E. Zeigen Sie ohne Verwendung des Satzes von Dirac, dass G zusammenhängend ist. Kann die Schranke n*/2 noch verbessert werden?