# Networks And Flows Flashcards

1
Q

For a directed graph, a capacity on G is?

A

A map- c:E -> R>=0

2
Q

On a directed graph, the capacity of an edge is?

A

c(e) , where c:E -> R>=0

3
Q

e+

A

the end/sink/target of the edge e

4
Q

e-

A

The start/source/origin of an edge e

5
Q

Directed path?

A

<=> aligned path: a path W where each edge is a forward edge

6
Q

Forward edge

A

ei=vi->vi+1

7
Q

A network ?

A

N=(G,c,s,t)
Source = s
Sink = t
s,t € V

8
Q

Criteria for A flow?

A

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} ,

9
Q

In a flow, f(e) = c(e) ?

A

e is saturated

10
Q

In a flow, f(e) = 0 ?

A

e is void

11
Q

Prove

A
12
Q

Value of flow f?

A

w(f) =

13
Q

f is maximal if,

A
14
Q

A cut?

A

For a network N;
Denoted (S,T)

15
Q

Capacity of a cut?

A

Quantity given

16
Q

Minimal cut?

A
17
Q

Cut must

A

Result in 2 disjoint connected components

18
Q

For N, w f: E -> R >=0 and (S,T), w(f) =?

A

(S,T) is cut of N

19
Q

Given (S,T) of N, w(f) =? Inequality?

A

<= c(S,T)
= capacity of cut;
Equality holds iff

20
Q

Proof that w(f) <= c(S,T)

A

Where equation (13) is sum of f(e) (sources) minus sum of f(e) (sinks)

21
Q

For N, with flow f, W is an augmenting path wrt f if

A
22
Q

Augmenting path theorem

A
23
Q

Integral flow theorem

A
24
Q

S f ?

A

The set of all vertices accesible from s on an augmenting path wrt f

25
Q

T f

A

V\S f

26
Q

Given Tf and Sf, f is a maximal flow if? Which means?

A

And only if t€ Tf which means (Sf,Tf) is a minimal cut: w(f) = c(Sf, Tf)

27
Q

Max flow min cut

A

For N and f, max value of f is equal to minimal capacity of a cut for N

28
Q

Naive labelling algorithm

A

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:

29
Q

Ford and Fulkerson labelling algorithm

A
30
Q

Kirchoff’s law

A

Sum of sinks = sum of sources (for all v € V{s,t}