✏️ Übungen zu Kap. 7 · Grad, Wege und Kreise in gerichteten Graphen
Freiwillig – such dir aus, was du üben willst.
Formal
Ein Weg in G = (V, E) ist eine Folge (k₁, k₂, …, kₙ) von Knoten mit (kᵢ, kᵢ₊₁) ∈ E für alle 1 ≤ i < n. Seine Länge ist n − 1.
Ein einfacher Weg ist ein Weg mit kᵢ ≠ kⱼ für alle i ≠ j.
Ein Zyklus ist ein Weg mit k₁ = kₙ, in dem keine Kante doppelt vorkommt: (kᵢ, kᵢ₊₁) ≠ (kⱼ, kⱼ₊₁) für i ≠ j.
Ein Kreis ist ein Zyklus, in dem außer k₁ = kₙ kein Knoten doppelt vorkommt.
In einem Graphen mit V = {A, B, C, D} haben die Knoten diese Grade: A: Eingangsgrad 0, Ausgangsgrad 2; B: Eingangsgrad 2, Ausgangsgrad 1; C: Eingangsgrad 1, Ausgangsgrad 2; D: Eingangsgrad 2, Ausgangsgrad 0. Es gibt keine Mehrfachkanten, keine Schlingen und zu keiner Kante (x,y) die Gegenkante (y,x). Zeichne einen solchen Graphen. (Wie viele solche Graphen gibt es?)
In einem Graphen mit V = {A, B, C, D} haben die Knoten diese Grade: A: Eingangsgrad 0, Ausgangsgrad 2; B: Eingangsgrad 2, Ausgangsgrad 1; C: Eingangsgrad 1, Ausgangsgrad 2; D: Eingangsgrad 2, Ausgangsgrad 0. Es gibt keine Mehrfachkanten, keine Schlingen und zu keiner Kante (x,y) die Gegenkante (y,x). Zeichne einen solchen Graphen. (Wie viele solche Graphen gibt es?)
Warum gibt es in diesem Graphen unendlich viele Wege von A nach F, aber nur endlich viele einfache Wege?