Network flow Flashcards
Network flow as a first block
Marriage theorem
G bipartite graph with |V1| = |V2| then G has perfect matching iff |N(S)| >= |S| for all subsets S of V1
s-t flow satisfies these conditions
conservation, capacity
Augmenting path theorem
Flow f is a max flow <=> there are no augmenting paths in residual graph
Running time of Ford-Fulkerson
O(mnC) where C is the maximum capacity
Define residual graph
It is the same graph as the original one but in addition it has return edges. These return edges r and the original edges o satisfy the following: old_cap(o) = old_cap(o) - f(o); and the return edges satisfy the following: cap(r) = old_cap(o) - new_cap(o)
Max-flow min-cut theorem
The value of a max flow is equal to the value of a min cut
We choose augmenting paths by the following criterias
- Max bottleneck capacity.
- Sufficiently large bottleneck capacity.
- Fewest number of edges
What is capacity scaling?
Basically, we do not use all the edges from the beginning of the Ford-Fulkerson algorithm but in each iteration of the algorithm we work only with those edges which satisfy cap(edge) >= scaling_parameter
How does capacity scaling work?
Scaling-Max-Flow(G, s, t, c)
foreach e ∈ E f (e) ← 0
∆ ← C
Gf ← residual graph
while (∆ ≥ 1)
Gf (∆) ← ∆-residual graph
while (there exists augmenting path P in Gf (∆))
f ← augment (f, c, P )
update Gf (∆)
∆ ← ∆/2
return f
So, in the beginning we set ∆ to some high value and while there exists an augmenting path in residual graph, augment this path. If there does not exist any other augmenting path, lower ∆ (for example ∆ = ∆/2). Do this while ∆ >= 1.
Define a min-cut, draw simple graph with network flow and indicate all min-cuts
s-t cut is a partition (A,B) of V with s in A and t in B. Minimum cut is a s-t cut with min CAPACITY
Define flow-value lemma
Let f be a flow in network (V,E,s,t,c) and let (A,B) be an s-t cut. Then the following holds: Σ_e out of A (f(e)) - Σ_e in to A (f(e)) = v(f)
What is weak duality?
Value of the flow is at most the capacity of the cut
Define a circulation
A circulation is a function that satisfies conservation and capacity
What is matching?
M⊆E is a matching if each vertex appears in at most one edge in M
Define Konig-Egervary theorem and describe it’s consequences (in words of runtime complexity of vertex cover for bipartite graphs)
The size of a smallest vertex cover of a bipartite graph equals the size of a maximum matching.
