---

Geschrieben von Info2 am 18.04.2010 um 16:27:

  Bäume

Sei T= (V,E(T)) ein spannender Baum von G = (V,E). Dann gilt:

(V,E(T)\{e}) zerfällt in zwei Unterbäume (X,E(X)) und (X',E(X')). Dabei ist Q:=(X,X'):={e=[i,j] aus E: i aus X, j aus X'} ein Schnitt in G.

Also ich habe schon ein Problem, den ersten Teil der Aussage zu beweisen. Kann man damit anfangen, dass wenn ich eine Kante zwischen zwei Knoten entferne, mindestens einer der Knoten die Wurzel einer der beiden Unterbäume ist.