| Info2 |
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. |
