Network Flow Flashcards
What is a directed graph?
Where the edges have direction and therefore an arc set A(G) or ordered pairs of vertices
What are semi-walks, semi-paths and semi-trails?
They are walks, paths and trails in the digraph that ignore arc direction.
What is a Network graph, N?
It is a digraph with two vertices, x the source and y the sink. Together with a capacity function on the edges which is the maximum amount a commodity can move along that edge and a flow function which is the current amount of that commodity that is moving along that edge.
What are the 3 conditions that define a flow in N?
The capacity constraint: f(uv) \leq c(uv) for each uv in A(N). The conservation condition: for each u in V(N){x,y}, the sum of the flows out of u, f(uv) or f^+(u) is equal to the sum of the flows into u, f(wu) of f^-(u). Maximum flow condition: define val(f) = f^+(u) - f^-(u) then f is a maximum flow if val(f) \geq val(g) for every flow g in N.
What does it mean for an arc to f-saturated and f-zero?
f-saturated: f(uv)=c(uv) and f-zero if f(uv)=0
When is f-unsaturated? Answer by first defining I(P).
I(P) = min uv in A(P) where P is a semi-path in N from x to y of: c(uv)-f(uv) if uv if forward in P or f(uv) if us is backward in P. P is unsaturated if I(P)>0.
What is the process of augmentation along a semi-path P in N used in the Maximum Flow algorithm?
I(P) = min uv in A(P) where P is a semi-path in N from x to y of: c(uv)-f(uv) if uv if forward in P or f(uv) if us is backward in P. Increase the flow of each forward arc by I(P) and decrease the flow of each backward arc by I(P).
What is the Max Flow Algorithm?
1.Label x, l(x) = infinity
repeat
(i) choose an unsaturated arc uv in A(N). Label the head, v with l(v) u min{l(u), c(uv)-f(uv)}
OR
(ii) choose an arc vu in A(N) which is not f-zero with head u labelled and tail v unlabelled. Label v with l(v) = min{l(u), f(a)}
until no arcs can be found or y gets labelled.
2. If y is unlabelled goto step 3. Otherwise update the flow by augmenting extra flow l(y) along semi-path P from x to y, where P can be found by defining a tree T containing all arcs uv or vu such that v was labelled from u, then P is the (x,y)-semi path in T. Define the new flow to be f’(uv) = f(uv)+l(y) if uv is forward in P OR f(uv)-l(y) if uv is backward in P OR f(uv) if uv is not in P.
3. Output the maximum flow f. The set of all labelled vertices determines the minimum cut S(S,V-S)
Define the net flow in and out of a set of vertices, S subset of V, f^+(S) and f^-(S).
f^+(S) is the sum of all f(uv) out of S where uv is in A(N) such that u is in S and v is in V(N)-S.
f^-(S) is the sum of all f(wu) into S where wu is in A(N) such that w is in V(N)-S and u is in S.
What is a cut associated with the subset S of V(N)
All the arcs uv in A(N) where u is in S and v is in V(N)-S denoted (S,V-S). This separates x and y limiting its flow.
What is the capacity of a cut, cap(S,V(N)-S)?
cap(S,V(N)-S) = Sum of all the c(uv) where uv is in A(N) such that u is in S and v is V(N)-S.
For every flow f and cut (S,V(N)-S) of N: val(f) ___ cap(S,V(N)-S)
val(f) \leq cap(S,V(N)-S). Also val(f) = cap(S,V(N)-S) iff each arc in (S,V(N)-S) is f-saturated and each arc from V(N)-S to S is f-zero.