Spanning trees: Cut/Cycle optimality condition |
| 20.06.2007, 19:21 | Andy82 | Auf diesen Beitrag antworten » |
| Spanning trees: Cut/Cycle optimality condition Kennt sich hier jemand im Bereich spanning trees aus? Ich geb euch mal nen Link: http://www.cs.princeton.edu/~wayne/cs423/lectures/mst.ppt Im drittletzten Punkt des Beweises auf Folie 11 steht "Deleting e from T* creates a fund. cut D which shares (at least) two arcs with cycle C. One is e, let f be another." Mir ist klar, dass e sowohl in C als auch in D liegt und dass es ein f in T geben muss, dass auch in D liegt. Aber wieso muss dieses f in C liegen? Das versteh ich noch nicht. Wieso kann das f nicht in T\C liegen? Wär super, wenn mir das jemand sagen könnte. Danke. |
||
| 21.06.2007, 01:02 | Abakus | Auf diesen Beitrag antworten » |
| RE: Spanning trees: Cut/Cycle optimality condition Kannst du den bisherigen Beweis mit allen Voraussetzungen einmal hinschreiben und dann dazu deine Frage formulieren ? Dort könnten wir einsteigen. Grüße Abakus 
|
||
| 21.06.2007, 12:25 | Andy82 | Auf diesen Beitrag antworten » |
| RE: Spanning trees: Cut/Cycle optimality condition Die Voraussetzungen und den kompletten Beweis findet man unter dem Link, aber ich schreib ihn auch gerne nochmal hier hin: ---------------------------------------------------------------------------------------------------- Given an undirected weighted graph G with weight function c and some spanning tree T of G. T satisfies the "cycle optimality condition" if for every non-tree arc e and for every tree arc f in its fundamental cycle, it holds that c(f) <= c(e). Theorem: If T satisfies the cycle optimality condition, then T is a minimum spanning tree (MST), i.e. a spanning tree of minimum weight. Proof: Let T be a spanning tree that satisfies the cycle optimality condition and let T* be a MST that has as many arcs in common with T as possible. If T=T* we are done. Otherwise, let e be an element of T*\T. Let C be the fundamental cycle formed by adding e to T. (Jetzt kommt der Satz, den ich bisher nicht verstand) Deleting e from T* creates a fundamental cut D that shares (at least) two arcs with cycle C. One is e, let f be another. Note: f is not in T*. The cycle optimality condition implies that c(f) <= c(e). Thus, we can replace e with f in T* without increasing its cost. ---------------------------------------------------------------------------------------------------- Was mir bisher unklar war ist die Tatsache, dass dieser Cut D mindestens zwei Kanten mit C gemeinsam hat. Mittlerweile hab ich herausgefunden, dass die Schnittmenge eines Cycles und eines Cuts stets eine gerade Anzahl an Kanten enthält. Womit sich das eigentlich geklärt hätte. Ich möchte allerdings zeigen, dass das obige Theorem generell für Basen von Matroiden gilt, nicht nur für spanning trees (spanning trees sind ja Basen eines graphischen Matroids). Und da tu ich mir noch schwer, da es dort so etwas wie cuts in der Form nicht gibt. 
Kann mir da vielleicht jemand weiterhelfen? |
||
| 21.06.2007, 14:49 | Abakus | Auf diesen Beitrag antworten » |
| RE: Spanning trees: Cut/Cycle optimality condition OK, dass es eine gerade Anzahl von Kanten ist, steht weiter vorne auf einer Folie. Das Problem hier ist, dass du mitten in etwas reinspringst und es ohne Kenntnis des davor Geschehenen schwer ist, es dann zu verstehen. Grüße Abakus
|
||
| 21.06.2007, 21:56 | Andy82 | Auf diesen Beitrag antworten » |
| RE: Spanning trees: Cut/Cycle optimality condition Habs mittlerweile rausgekriegt. Es funktioniert auch für Matroide, mit Hilfe eines Basisaustauschaxioms von Brualdi. Trotzdem danke für die Hilfsversuche. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
