Beweis einer Äquivalenz zwischen 2 Aussagen.

Question

Es sei G ein zusammenhängender Graph, w : E → R eine Gewichtsfunktion und B ein aufspannender Baum
von G. Zu zeigen ist, dass die folgenden Aussagen äquivalent sind:Aussage 1: B ist ein minimal spannender Baum von G.
Aussage 2) Für jedes e = xy ∈ E(G)\E(B) existiert keine Kante auf dem eindeutigen x-y-Pfad in T, die höheres Gewicht als e hat.

Würde mich freuen wenn jemand den Lösungsweg kennt und ihn mir erklären kann.

(:

Comments

Meinst du etwa :
"...auf dem eindeutigen x-y-Pfad in B, die höheres Gewicht als e hat."

Answer 1

Spontan kann ich die Hinrichtung zeigen:
"=>"
Also: B ist ein minmaler Spannbaum.

Wir gehen davon aus, dass Ausage 2 nicht stimmt.
Nehme an: es existiert ein e = xy ∈ E(G)\E(B) mit  w(e) < w(e') , wobei e' eine Kante auf dem Weg von x zu y ist.

Jetzt kann ich durch löschen von e' und hinzufügen von e einen Spannbaum mit kleinerem Gesamtgewicht bestimmen.

=> B ist also doch kein minimaler Spannbaum => Widerspruch, also stimmt die Hinrichtung.

(Vielleicht mal um klar zu machen, warum das einfach so geht: Durch das löschen der Kante e'  "verlieren" wir die Verbindung von Knoten a mit Knoten b. Gehen wir mal davon aus, dass diese Knoten nicht x und y sind, weil das supertrivial wäre eine direkte Verbindung mit einer anderen direkten Verbindung zu ersetzen.
Das Löschen der Kante würde in meinem Spannbaum zwei Zusammenhangskomponenten erzeugen.Das heißt zu dem einem Knoten a komme ich nur noch von x hin/ zu Knoten b komme ich nur noch von y hin. Durch nutzen der direkten Kante e = xy überbrucke ich dieses Problem, weil die beide Zshmkomponenten wieder mittels der dieser Kante zusammensetze)

Für die Rückrichtung wirds zeitlich gerade knapp bei mir. Eventuell schaffe ich dies später.
Hier solltest du aber zeigen können, wenn keine solche Kante existiert, dass du keine Kante aus deinem Spannbaum mit einer,die nicht im Spannbaum ist, ersetzen kannst, sodass das Gewicht kleiner wird. Sollte nach dem selben Prinzip gehen.