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