Week 5: Graph Algorithms (70)

Flow in a network G=(V,E) … nonnegative f(v,w) for all vertices v,w∈V such that

f(v,w)≤capacity for each edge e=(v,w,capacity) ∈ E
f(v,w)=0 if no edge between v and w
total flow into a vertex = total flow out of a vertex:

`sum_(x in V) f(x,v) = sum_(y in V) f(v,y)` for all v ∈ V \ {s,t}

Maximum flow … no other flow from s to t has larger value