Übungen

Übung 1

Sei G = (E, K) ein Graph, und seien a, b  ∈  E. Es gebe einen Kantenzug von a nach b in G. Zeigen Sie, dass es einen Weg von a nach b in G gibt.

Übung 2

Zeigen Sie, dass jeder Weg in einem Graphen ein einfacher Kantenzug ist.

Übung 3

Sei G = (E, K) ein Graph. Zeigen Sie, dass die Erreichbarkeitsrelation von G reflexiv, symmetrisch und transitiv ist.

Übung 4

Sei G = (E, K) ein Graph mit genau n Zusammenhangskomponenten und sei ab eine Brücke in G. Zeigen Sie, dass der Graph G′, der aus G durch Streichen der Kante ab hervorgeht, genau n + 1 Zusammenhangskomponenten besitzt.

Übung 5

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

(1)

Die Kante ab ist eine Kreiskante, d. h. es gibt einen Kreis in G, der ab als Kante enthält.

(2)

Die Kante ab ist keine Brücke von G.

Übung 6

Sei G = (E, K ) ein zusammenhängender Graph mit mindestens zwei Ecken. Zeigen Sie: Es gibt zwei verschiedene Ecken a, b derart, dass die Graphen G − a und G − b zusammenhängend sind. Dabei sei G − e für eine Ecke e der Untergraph von G, der durch Streichen der Ecke e entsteht (Entfernen von e und aller Kanten mit e als Ecke).

[ Hinweis: Starke Induktion nach |E|. ]

Übung 7

Sei G = (E, K) ein Graph. Zeigen Sie die drei grundlegenden Eigenschaften (Nullbedingung, Symmetrie, Dreiecksungleichung) für die Abstandsfunktion d des Graphen.

Übung 8

Sei G = (E, K) ein Graph. Zeigen Sie, dass G genau dann zusammenhängend ist, wenn es eine Ecke a gibt mit d(a, b) < ∞ für alle Ecken b.

Übung 9

Sei G = (E, K) bipartit und zusammenhängend. Weiter sei a  ∈  E beliebig. Wir setzen

E1  =  { b  ∈  E | d(a, b) ist gerade },  E2  =  { b  ∈  E | d(a, b) ist ungerade }.

Zeigen Sie, dass G bipartit durch E1, E2 ist.

Übung 10

Sei G = (E, K1, K2) ein gerichteter Graph mit E = { 0, …, 6 } und zwei Kantenmengen

K1  =  { 01, 12, 23, 34, 45, 56, 60 },

K2  =  { 00, 13, 26, 32, 45, 51, 64 }.

Der Graph hat eine Schlinge bei 0 und eine Doppelkante zwischen 4 und 5. Wir zeichnen die Kanten in K1 als grüne Pfeile und die Kanten in K2 als blaue Pfeile.

ema21-AbbID2-2-ex-1

Sei nun eine Zahl d1…dn in Dezimaldarstellung gegeben. Wir starten im Graphen bei der Ecke 0 und gehen d1 Schritte entlang der grünen Pfeile. Danach gehen wir einen Schritt entlang eines blauen Pfeils. Nun gehen wir d2 grüne Schritte, danach wieder einen blauen usw. Das Verfahren endet mit dn grünen Schritten. (Blaue Schritte markieren einen Ziffernwechsel, sodass es insgesamt n − 1 blaue Schritte gibt.) Für 148 ergibt sich zum Beispiel der Kantenzug 0, 1, 3, 0, 0, 1; für 226 ergibt sich 0, 2, 6, 1, 3, 2.

(a)

Welche zahlentheoretische Bedeutung hat die zuletzt besuchte Ecke? Formulieren sie eine Hypothese und beweisen Sie sie.

[ Hinweis: Experimentieren Sie systematisch, um die Bedeutung zu ermitteln, und verwenden Sie Induktion, um Ihre Hypothese zu beweisen. ]

(b)

Ergibt sich das korrekte Resultat, wenn die Zahl d1…dn von rechts nach links durchlaufen wird?

(c)

Können Sie analoge Graphen für die Eckenmenge { 0, …, m − 1 }, m ≥ 2 beliebig, erstellen? Welche Graphen ergeben sich speziell für m = 3, 5, 9? Welchen bekannten zahlentheoretischen Regeln entsprechen die Ergebnisse für diese m?

Übung 11

Das Problem der Flussüberquerung lautet in einer von zahlreichen Varianten:

Ein Bauer will mit einem Wolf, einer Ziege und einem Kohlkopf einen Fluss mit Hilfe eines Floßes überqueren. Nur der Bauer kann das Floß steuern, und er kann immer nur entweder den Wolf oder die Ziege oder den Kohlkopf mitnehmen. Zudem dürfen auf einer Flussseite niemals Ziege und Kohlkopf ohne Bauer und auch niemals Wolf und Ziege ohne Bauer sein. Wie überquert der Bauer den Fluss?

Modellieren Sie das Problem mit Hilfe eines Graphen. Zeichnen Sie Ihren Graphen möglichst übersichtlich, sodass Sie alle möglichen Lösungen ablesen können.