Section 7: Network Flows

Question 1

Directed graph

Answer 1

a pair (V, E), where V is any set, and E is a set whose elements are ordered pairs of elements from V

Question 2

in-edge of v

Answer 2

an edge from u to v

Question 3

out-edge of v

Answer 3

and edge from v to w

Question 4

in-degree of a vertex v

Answer 4

number of in-edges of v

Question 5

out-degree of v

Answer 5

number of out-edges of v

Question 6

Source

Answer 6

A vertex in a digraph whose in-degree is zero

Question 7

Sink

Answer 7

a vertex whose out-degree is zero

Question 8

Directed path from u to v

Answer 8

a sequence of vertices
u = w_1, . . . , w_p = v such that ->w_iw_i+1
is a directed edge for each
1 ≤ i ≤ p − 1.

Question 9

basic flow network

Answer 9

a directed graph with exactly one source and one sink, equipped with a function c: E → N which
assigns a capacity to each edge

Question 10

Flow

Answer 10

a function f : E →N ∪ {0} which satisfies the following conditions:

a) for every edge e, f(e) is at most c(e), the capacity of e, and

b) for every vertex v other than the source and the sink, the sum of the flows on the in-edges of v is equal to the sum of the flows on the out-edges of v.

Question 11

value of a flow, val(f),

Answer 11

Equal to the sum of the
flows assigned to the out-edges of the source

Question 12

Lemma 7.1. Let f be a flow in the basic flow network D = (V, E). Then the sum of the flows assigned to the out-edges of the source is equal to __________

Answer 12

the sum of the flows assigned to the in-edges of the sink.

Question 13

augmenting path

Answer 13

an undirected path from the source to the sink such that we can increase the flow along every edge of the path by some value x ∈ N without violating any capacity constraints

Question 14

forward edges

Answer 14

path includes the edge uv
and −→uv is a directed edge of our graph

Question 15

backward edges

Answer 15

path includes the edge uv but only the directed edge −→vu is in the network.

Question 16

saturated edge

Answer 16

An edge in the network is said to be saturated by a given flow if the flow on the edge is equal to the capacity of the edge

Question 17

Cut

Answer 17

a partition of the vertices into two disjoint sets, such that the source belongs to the first set and the sink to the second.

Question 18

Capacity of a cut (X,Y)

Answer 18

sum of the capacities of the edges from X to Y (we ignore any edges from Y to X)

Question 19

Minimum cut

Answer 19

a cut whose capacity is equal to the minimum
capacity of any cut in the digraph

Question 20

Max-Flow Min-Cut Theorem

Answer 20

In any basic flow network, the value of the maximum flow is equal to the
capacity of the minimum cut.