1MaxFlow MinCut Theorem¶
 Definition of a
Cut
: a partition of the vertices of a graph into two disjoint subsets. (Wikipedia) Capacity/Size of a cut is Sum of capacity of edges in the cutset (edges whose endpoints are in different set)
 Minimum cut is thus the set of edges that sum up to the smallest capacity.
 Capacity/Size of a cut is Sum of capacity of edges in the cutset (edges whose endpoints are in different set)
 Claim: Suppose f* is the output of FordFulkerson MaxFlow Algorithm
 There exists a Cut (A , B ) = V(f*).

Proof: Let A* be the set of all vertices that can be reached from s (source) in the residual graph.
 Consider that edges from s to t in a residual graph represent leftover capacity at that edges. Edges from t to s in residual graph may represent flow from s to t.
 Graph Gf* :
")  Since the algorithm terminated, we know t cannot be in A* . Otherwise, there will be a path from s to t to augment, thus continue the algorithm.
 Note: No edge should be going from A to B in Gf*.
 For every edge e from A to B , we have f(e)=Ce: otherwise, an edge would exist connecting endpoints in Gf *. i.e: path from A to B must be use in its full capacity, or there will be left over to produce reverse in residual graph.

For every edge e from B to A, we have f(e)=0 : otherwise, an edge would exist connecting endpoints in Gf *. i.e: edge from B to A become residual edge from A to B if flow > 0, thus must have zero flow.
V(f*) = Sum of flow of edges from A* to B*  Sum of flow of edges from B* to A* = Sum of capacity of edges from A* to B*  0 = Cap. ( A*, B*) V(f*) <= max flow <= min cut <= Cap(A*, B*) and V(f*) = Cap(A*, B*) then V(f*) = max flow = min cut = Cap(A*, B*)

Random Question: Is it true that every max flow assigns integer values to all edges?
 No, by counter example:
 No, by counter example:
1.1Choosing a good path to augment?¶
 want the largest augment path to be picked ==> slow, poly time
 instead, start with a large value delta, and keep augmenting path with bottleneck >= delta until no such a path remain. Then set delta = delta/2 and continue.
1.1.1Scaling MaxFlow Algorithm¶
initially, f(e)=0 for all e in E, set _delta_ = smallest power of 2 >= max capacity of any edge while _delta_ >= 1: while exists st path "p" in Gf(delta): augment p. update Gf(delta). end while _delta_= _delta_/2 end while let Gf(**delta**) be the subgraph of Gf with only edges with residual capacity >= _delta_
 Proof of Correctness : when algorithm terminates, there won't be any st path in Gf.(same as FordFulkerson)

Runtime:
Let C = Max (e in E) Ce. initial _delta_ <= 2C The outer while loop iterations = log(initial _delta_) <= O(log C) The runtime of inner loop is bit tough (case dependent)
 Claim: let f be a flow at the end of the delta phase (i.e no st path left in Gf(delta) )
 exits a Cut(A,B) in G such that Cap(A,B) <= V(f) + M * delta where M = # of edges in G
 Proof: Let A be the set of vertices that can be reach from s in Gf(delta)

Observation:
there is no residual edges from A > B in Gf(delta).
so for every edge e in G from A>B, Cef(e) < delta, Ce delta < f(e)
i.e cannot be augmented anymore.V(f) = f out (A)  f in (A)
= Sum of f(e) for e from A>B  Sum of f(e) for e from B>A
> Sum (Ce  delta) for e from A>B  Sum of delta for e from B > A
>at most Mdelta
V(f) > Cap(A,B)  M * delta
=> Cap(A,B) < V(f) + Mdelta

Claim: the number of augmentation on the delta  phase is at most 2M

Proof: Let f^prev denotes the flow at the end of the previous phase. (2delta phase)
 V(f) <= Cap(A,B) <= V(fprev) + 2M

Observation: every augmentation in the deltaphase adds at least delta to V(f). so we can do at most 2M augmentation: V(f)  V (f prev) <= 2deltaM.

total running time is:
O(Log C * M * M ) = O(M^2 log C) > Polytime
augment do augmentation
1.2Bipartite Matching Problem¶
 Definition: A matching in a graph G is a set of edges with no intersection.
 A prefect matching is a matching including all vertices.

The Problem:
 input: bipartite graph G, find a largest possible matching in G.
 convert G to a flow network G', s.t the maxflow in G' corresponds to a max match in G.
 construct G' like this ( G partions to (X,Y)):
 direct every edge in G from X to Y and add capacity of 1
 add a node "s" and direct edges from s to every edge iin X with Cap=1.
 add a node "t" and direct edges from every edges in Y to "t" with Cap=1.

Prop: MaxFlow of G' = Max Matching in G.
 Claim: MaxFlow in G' >= Max matching in G

Proof: Let M be a max matching in G,
 assign flow of 1 to every edge in M
 assign flow of 1 to every edge from s to a vertex in M, and from every vertex in "?" involved in M to t.
 all other edges get a flow of zero.
 note that V(f) = M, so max flow >= f = M

Claim: MaxFlow <= Max Matching.
 Proof: let f be a max flow with integer values.
 the edges that get a flow of 1 from X > Y will form a matching
 since:
 there can only be 1 such X>Y edge incident to any one vertex in X (or in Y).
 so there is a matching M of size >= maxflow
 MaxMatching >= M >= MaxFlow
 thus: MaxMatching >= Max Flow. MaxFlow >= MaxMatching==> Max Flow = Max Matching
Note incomplete:under development