Bäume |
18.04.2010, 16:27 | Auf diesen Beitrag antworten » |
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. |
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |