Self-Assessment Quiz: Network Flow and Matching

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Throughout, network $M$ is the chapter's primary network: $c(s,a)=10,\ c(s,b)=3,\ c(a,b)=4,\ c(a,t)=3,\ c(b,t)=10$.

Question 1

The value of a flow $f$, written $\lvert f\rvert$, is defined as:

A) the sum of all capacities in the network B) the net flow out of the source $s$ C) the largest flow on any single edge D) the number of edges carrying positive flow

Question 2

The flow-conservation constraint applies to:

A) every vertex in the network B) the source and sink only C) every vertex except the source and sink D) only saturated edges

Question 3

An edge with capacity 6 currently carries 6 units of flow is called:

A) a back edge B) a residual edge C) saturated D) a cut edge

Question 4 (True/False, justify)

True or false: In any flow, the net flow out of the source equals the net flow into the sink. Justify in one sentence.

Question 5

Naive greedy ("push as much as possible along any spare forward path, repeat") can fail to find the maximum flow because:

A) it may run forever B) it permanently commits flow to an edge with no way to undo a bad choice C) it violates the capacity constraint D) it ignores the sink

Question 6

The residual capacity $c_f(u,v)$ equals:

A) $c(u,v) - f(u,v)$ only B) $f(v,u)$ only C) $(c(u,v) - f(u,v)) + f(v,u)$ D) $c(u,v) + f(u,v)$

Question 7

Pushing one unit of flow along a residual back edge $v\to u$ has the effect of:

A) adding a new edge $v\to u$ to the original network B) increasing $f(u,v)$ by one C) decreasing $f(u,v)$ by one (canceling existing flow) D) saturating the edge $u\to v$

Question 8

An augmenting path is:

A) any path from $s$ to $t$ in the original graph B) a directed $s\to t$ path in the residual network, using forward and/or back edges with positive residual capacity C) the shortest path by total capacity D) a cycle through the source

Question 9

The bottleneck of an augmenting path is:

A) the largest residual capacity on the path B) the smallest residual capacity on the path C) the number of edges on the path D) the capacity of the source edge

Question 10

Choosing augmenting paths by BFS (shortest by number of edges) turns Ford–Fulkerson into:

A) Dijkstra's algorithm B) Kruskal's algorithm C) Edmonds–Karp D) the Bellman–Ford method

Question 11

The capacity of an s–t cut $(S,T)$ counts:

A) all edges with at least one endpoint in $S$ B) only edges going from $S$ to $T$ C) edges going from $T$ to $S$ as well as $S$ to $T$ D) every edge in the network

Question 12

The max-flow min-cut theorem states that:

A) the max flow is at most the min cut B) the max flow value equals the minimum s–t cut capacity C) every cut has the same capacity D) the min cut is half the max flow

Question 13 (True/False, justify)

True or false: If you find a flow of value 8 and some s–t cut of capacity 12, then the flow is not yet maximum (there is still room to improve). Justify.

Question 14

To construct a minimum cut from a maximum flow $f$, you take $S$ to be:

A) the vertices adjacent to $s$ B) the vertices reachable from $s$ in the original graph C) the vertices reachable from $s$ in the residual network $G_f$ D) all vertices except $t$

Question 15

In the proof that a max flow gives a min cut, every edge crossing from $S$ to $T$ must be:

A) carrying zero flow B) saturated C) a back edge D) inside the source

Question 16

In the bipartite-matching reduction, the edges $s\to x$ and $y\to t$ are given capacity exactly 1 in order to:

A) make the algorithm faster B) force each left vertex to be used at most once and each right vertex to be taken at most once C) guarantee the flow is fractional D) ensure the graph stays bipartite

Question 17 (True/False, justify)

True or false: The bipartite-matching reduction works only because Ford–Fulkerson, started from the zero flow with integer capacities, produces an integer flow. Justify.

Question 18

A maximum flow on a bipartite reduction has value 7. The maximum matching has size:

A) 3 B) 7 C) 14 D) cannot be determined

Question 19

Hall's condition for a bipartite graph to have a matching saturating $X$ is: for every $W\subseteq X$,

A) $\lvert N(W)\rvert \le \lvert W\rvert$ B) $\lvert N(W)\rvert \ge \lvert W\rvert$ C) $\lvert N(W)\rvert = \lvert X\rvert$ D) $N(W) = Y$

Question 20 (Short answer)

In two sentences, explain why image segmentation (separating foreground from background) is solved by computing a minimum cut, and which side of the cut is the foreground.

Answer Key

Topics to review by question