Zeige: Gilt δ(w) ≥ 2 in TH(w), dann ist w eine Artikulation.

Question

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.

Answer 1

Antwort mit KI erzeugt

Erklärung und Beweisführung

Um zu zeigen, dass ein Knoten \(w\) in einem Graphen \(H\) eine Artikulation ist, wenn im Tiefensuchebaum \(TH(w)\) von \(H\), der Knoten \(w\) einen Grad \(δ(w) \geq 2\) aufweist, betrachten wir zunächst die Definitionen und die gegebenen Bedingungen.

Gegeben:

- Ein zusammenhängender Graph \(H = (V, E)\).
- Ein Tiefensuchebaum \(TH(w)\) von \(H\), der entsteht, wenn eine Tiefensuche mit Startknoten \(w \in V\) ausgeführt wird.
- Ein Knoten \(v \in V\) wird als Artikulation bezeichnet, wenn der Graph \(H\) ohne \(v\) unzusammenhängend ist.
- Es gilt \(δ(w) \geq 2\) im Tiefensuchebaum \(TH(w)\), d.h., der Startknoten \(w\) hat mindestens zwei Kinder.

Zu Zeigen:

- Wenn \(δ(w) \geq 2\) in \(TH(w)\), dann ist \(w\) eine Artikulation.

Beweis:

1. Startpunkt ist, dass \(w\) im Tiefensuchebaum \(TH(w)\) mindestens zwei verschiedene Teilgraphen \(T_1\) und \(T_2\) hat, was bedeutet, dass \(δ(w) \geq 2\). Diese Teilgraphen \(T_1\) und \(T_2\) sind die Teilbäume von \(TH(w)\), die durch die Kinder von \(w\) generiert werden.

2. Angenommen, \(w\) ist keine Artikulation, dann müsste nach dem Entfernen von \(w\) aus \(H\) der Graph immer noch zusammenhängend sein. Das würde bedeuten, dass es mindestens einen Pfad zwischen einem Knoten in \(T_1\) und einem Knoten in \(T_2\) gibt, der \(w\) nicht beinhaltet.

3. Allerdings, wenn solch ein Pfad existiert, der \(w\) nicht beinhaltet, dann hätte die Tiefensuche diesen Pfad genommen, und die Knoten von \(T_1\) und \(T_2\) würden nicht in getrennten Teilbäumen des Tiefensuchebaums auftauchen. Dies steht im Widerspruch zur Annahme, dass \(δ(w) \geq 2\). Das heißt, wenn \(w\) nicht die Wurzel dieser Teilbäume wäre, dann müssten alle Knoten entweder in \(T_1\) oder \(T_2\) zusammengefasst sein, abhängig davon, welchen Pfad die Tiefensuche zuerst entdeckt hätte, was jedoch nicht der Fall ist.

4. Daher muss bei Entfernen von \(w\) aus \(H\) der Graph in mindestens zwei unzusammenhängende Teile zerfallen, da es keinen Pfad zwischen den Knoten in \(T_1\) und den Knoten in \(T_2\) gibt, der \(w\) nicht beinhaltet. Folglich ist \(w\) eine Artikulation, wenn \(δ(w) \geq 2\) in \(TH(w)\).

Fazit:

Der Knoten \(w\) ist eine Artikulation im Graphen \(H\), wenn im Tiefensuchebaum \(TH(w)\) der Grad von \(w\) mindestens 2 ist. Dies basiert auf der Logik, dass ohne \(w\), die aus \(w\) entspringenden Teilbäume des Tiefensuchebaums keine Verbindungen mehr untereinander haben, was den Graphen \(H\) unzusammenhängend macht.