Networks And Flows Flashcards
For a directed graph, a capacity on G is?
A map- c:E -> R>=0
On a directed graph, the capacity of an edge is?
c(e) , where c:E -> R>=0
e+
the end/sink/target of the edge e
e-
The start/source/origin of an edge e
Directed path?
<=> aligned path: a path W where each edge is a forward edge
Forward edge
ei=vi->vi+1
A network ?
N=(G,c,s,t)
Source = s
Sink = t
s,t € V
Criteria for A flow?
Flow on N is a map: f:E -> R >=0 which satisfies
1) for all e€E, 0<= f(e) <= c(e)
2) for al v€V{s,t} ,
In a flow, f(e) = c(e) ?
e is saturated
In a flow, f(e) = 0 ?
e is void
Prove
Value of flow f?
w(f) =
f is maximal if,
A cut?
For a network N;
Denoted (S,T)
Capacity of a cut?
Quantity given
Minimal cut?
Cut must
Result in 2 disjoint connected components
For N, w f: E -> R >=0 and (S,T), w(f) =?
(S,T) is cut of N
Given (S,T) of N, w(f) =? Inequality?
<= c(S,T)
= capacity of cut;
Equality holds iff
Proof that w(f) <= c(S,T)
Where equation (13) is sum of f(e) (sources) minus sum of f(e) (sinks)
For N, with flow f, W is an augmenting path wrt f if
Augmenting path theorem
Integral flow theorem
S f ?
The set of all vertices accesible from s on an augmenting path wrt f
T f
V\S f
Given Tf and Sf, f is a maximal flow if? Which means?
And only if t€ Tf which means (Sf,Tf) is a minimal cut: w(f) = c(Sf, Tf)
Max flow min cut
For N and f, max value of f is equal to minimal capacity of a cut for N
Naive labelling algorithm
1) f(e) <- 0 for all e
2) while exists and augmenting path from s to t:
3) let W = (e1, … , ek) be augmenting path from s to t set:
Ford and Fulkerson labelling algorithm
Kirchoff’s law
Sum of sinks = sum of sources (for all v € V{s,t}
