Content deleted Content added
simpler(more intuitive?) proof |
|||
Line 186:
Why can't the graph contain negative weights in the example? Isn't this a little confusing for people who just learned Dijkstra? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/78.21.33.78|78.21.33.78]] ([[User talk:78.21.33.78|talk]]) 05:48, 29 May 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
== Simpler end of proof ==
Proof can be made slightly simpler at the end. We are in case Y != Y_1, and Y_1 is minimal spanning tree. There two possibilities, Y is also minimal spanning tree (other one with the same sum of the weight), which is OK, or Y have different sum of weight. If it have different number, then if must of course have more than sum for Y_1. At the ending wee see that Y_2, constructed from Y by removing f and adding e, have sum of weights smaller (or equal) than Y itself, and is again spanning tree. If it is equal then it s OK for us. If it is greater, this leads to contradiction (Y_2 cannot have smaller sum of weight from Y_1, which already have smallest possible one). Therfore Y != Y_1, and sum of Y < sum of Y_1, is impossible. End of proof. --[[Special:Contributions/91.213.255.7|91.213.255.7]] ([[User talk:91.213.255.7|talk]]) 04:28, 7 January 2011 (UTC)
| |||