Frage:
Sei H= (V, E) ein zusammenhängender Graph und TH(w) der Tiefensuchebaum von H, der etsteht, wenn Tiefensuche mit Startknoten w ∈ V ausgeführt wird. Wir nennen einen Knoten v ∈ V Artikulation, wenn H ohne v unzusammenhängend ist. Zeige: Gilt δ(w) ≥ 2 in TH(w), dann ist w eine Artikulation.
Problem:
Man hat den tiefensuchenbaum und der startknoten soll der Knoten w sein. Wenn man w raus streichst dann hat der Graph mehrere Teilgraphen die Unzusammenhängend sind, weil die nicht mit eineinder verknüpft sind und die dürfen bei einem Suchbaum auch nur über den Startknoten w verknüpft sein sonst wäre es ein Kreis.
Ich weiß nur soweit aber ich weiß nicht, wie ich genau beweisen muss. :(
Ich bitte Sie um Ihre Hilfe.
