Thursday, January 5, 2012

Max flow min cut?

Bij for vertex i, edge j is 0 if j does not connect to i, 1 if j flows out of i and -1 if j flows in. Obviously every edge j contributes a 1 to some vertex and a -1 to another, elsewhere 0s so the sum over the whole digraph is 0.

No comments:

Post a Comment