Networks And Flows

Question 1

For a directed graph, a capacity on G is?

Answer 1

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

Question 2

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

Answer 2

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

Question 3

e₊

Answer 3

the end/sink/target of the edge e

Question 4

e_-

Answer 4

The start/source/origin of an edge e

Question 5

Directed path?

Answer 5

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

Question 6

Forward edge

Answer 6

e_i=v_i->v_i+1

Question 7

A network ?

Answer 7

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

Question 8

Criteria for A flow?

Answer 8

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

Question 9

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

Answer 9

e is saturated

Question 10

In a flow, f(e) = 0 ?

Answer 10

e is void

Question 11

Prove

Answer 11

Question 12

Value of flow f?

Answer 12

w(f) =

Question 13

f is maximal if,

Answer 13

Question 14

A cut?

Answer 14

For a network N;
Denoted (S,T)

Question 15

Capacity of a cut?

Answer 15

Quantity given

Question 16

Minimal cut?

Answer 16

Question 17

Cut must

Answer 17

Result in 2 disjoint connected components

Question 18

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

Answer 18

(S,T) is cut of N

Question 19

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

Answer 19

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

Question 20

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

Answer 20

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

Question 21

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

Answer 21

Question 22

Augmenting path theorem

Answer 22

Question 23

Integral flow theorem

Answer 23

Question 24

S _f ?

Answer 24

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

Question 25

T _f

Answer 25

V\S _f

Question 26

Given T_f and S_f, f is a maximal flow if? Which means?

Answer 26

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

Question 27

Max flow min cut

Answer 27

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

Question 28

Naive labelling algorithm

Answer 28

1) f(e) <- 0 for all e
2) while exists and augmenting path from s to t:
3) let W = (e₁, … , e_k) be augmenting path from s to t set:

Question 29

Ford and Fulkerson labelling algorithm

Answer 29

Question 30

Kirchoff’s law

Answer 30

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