Talk:Edmonds–Karp algorithm: Difference between revisions

Revision as of 01:40, 20 February 2009

Revision as of 23:28, 2 May 2009

Line 52:

At the end of the example it says that the minimal cut partitions the nodes into ''"sets {let A =6,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)