0 Daumen
44 Aufrufe

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.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community