Content deleted Content added
No edit summary |
No edit summary |
||
Line 53:
At the end of the example it says that the minimal cut partitions the nodes into ''"sets {A,B,C,E} and {D,F,G}, with the capacity c(A,D) + c(C,D) + c(E,G) = 3 + 1 + 1 = 5."'' But isn't the capacity here missing edge (D,E) with c(D,E) = 2 ? The capacity of the cut would then be 7 instead of 5. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/134.60.236.119|134.60.236.119]] ([[User talk:134.60.236.119|talk]]) 15:15, 23 October 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
: No, the capacity is five. You should only count edges from the source set S to the sink set T. edge D,E is from T to S, and therefore does not increase the capacity. [[User:ArrowmanCoder|ArrowmanCoder]] ([[User talk:ArrowmanCoder|talk]]) 01:40, 20 February 2009 (UTC)
You state that "...and independently by Jack Edmonds and Richard Karp in 1972 (discovered earlier).". Well, that is usual in any science. Did anybody ask Dinic at what point in time he discovered the algorithm that is attributed to Edmonds and Karp? If not, then the remark "(discovered earlier)" should be removed. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/130.237.222.140|130.237.222.140]] ([[User talk:130.237.222.140|talk]]) 14:52, 1 October 2008 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
| |||