Network Flow Flashcards

1
Q

What is a directed graph?

A

Where the edges have direction and therefore an arc set A(G) or ordered pairs of vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are semi-walks, semi-paths and semi-trails?

A

They are walks, paths and trails in the digraph that ignore arc direction.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a Network graph, N?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the 3 conditions that define a flow in N?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What does it mean for an arc to f-saturated and f-zero?

A

f-saturated: f(uv)=c(uv) and f-zero if f(uv)=0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

When is f-unsaturated? Answer by first defining I(P).

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the process of augmentation along a semi-path P in N used in the Maximum Flow algorithm?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the Max Flow Algorithm?

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Define the net flow in and out of a set of vertices, S subset of V, f^+(S) and f^-(S).

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a cut associated with the subset S of V(N)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the capacity of a cut, cap(S,V(N)-S)?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

For every flow f and cut (S,V(N)-S) of N: val(f) ___ cap(S,V(N)-S)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly