Discrete Math Quiz: Network Flow

20 questions · exam conditions

0:00

Network FlowQuestion 1 of 20

A bipartite graph $G = (X \cup Y, E)$ has $|X| = 6$ , $|Y| = 4$ , and every vertex in $X$ has degree exactly 2. When modeling maximum matching as a max flow problem, what is the sum of all edge capacities in the resulting flow network?

16 units, from source capacities plus matching edge capacities plus sink capacities

22 units, including all edges with their unit capacities in the flow network construction

18 units, accounting for source edges, bipartite edges, and sink edges with unit capacities

20 units, considering the total edges needed for the standard flow network transformation

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Network Flow

Practice Network Flow in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Network Flow, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

16 units, from source capacities plus matching edge capacities plus sink capacities
22 units, including all edges with their unit capacities in the flow network construction (correct answer)
18 units, accounting for source edges, bipartite edges, and sink edges with unit capacities
20 units, considering the total edges needed for the standard flow network transformation

Explanation: In the max flow model for maximum matching: add source

s

with edges to all vertices in

X

(6 edges of capacity 1), add sink

t

with edges from all vertices in

Y

(4 edges of capacity 1), and include all original bipartite edges with capacity 1. Since each vertex in

X

has degree 2, there are

6 \times 2 = 12

bipartite edges. Total edge capacities:

6 + 4 + 12 = 22

. Choice A miscounts the bipartite edges. Choices C and D have arithmetic errors in the total count.

Question 2

A bipartite graph represents a matching problem with 5 vertices on the left and 5 vertices on the right. When modeled as a flow network for maximum matching, what should be the capacity of the edge from source to each left vertex?

Capacity 5 to allow matching with any right vertex
Capacity 1 to ensure each left vertex matches at most once (correct answer)
Capacity equal to the degree of that left vertex
Capacity 0.2 since each vertex represents 20% of the left side

Explanation: In maximum bipartite matching via flow networks, each vertex should participate in at most one matching edge. Setting source-to-left capacities to 1 enforces this constraint. Choice A allows one left vertex to monopolize multiple matches. Choice C relates to graph structure but doesn't enforce matching constraints. Choice D uses fractional capacity inappropriately for a matching problem.

Question 3

In a flow network, every edge has capacity 1. The Ford-Fulkerson algorithm finds augmenting paths in this order: path $P_1$ (bottleneck 1), path $P_2$ (bottleneck 1), path $P_3$ (bottleneck 1). What is the current flow value?

Exactly 3 units total through the network (correct answer)
At most 3 units, possibly less if paths share edges
At least 3 units, possibly more from previous iterations
Cannot determine without knowing if paths are edge-disjoint

Explanation: Each augmenting path increases the total flow by its bottleneck capacity. Since we found three paths with bottleneck 1 each, the flow increased by 1 + 1 + 1 = 3 units total. Whether paths share edges is irrelevant - the algorithm ensures each augmentation adds the bottleneck amount to total flow. Choice B incorrectly suggests path overlap reduces total flow. Choice C assumes prior flow. Choice D overcomplicates the flow accounting.

Question 4

In a flow network, the capacity of edge $(u,v)$ is 8 and the current flow along this edge is 5. If we reverse the direction of 3 units of flow along this edge, what is the resulting net flow from $u$ to $v$ ?

2 units from $u$ to $v$ (correct answer)
8 units from $u$ to $v$
3 units from $v$ to $u$
5 units from $u$ to $v$

Explanation: Initially there are 5 units flowing from u to v. Reversing 3 units means we reduce the flow by 3 units, leaving 5 - 3 = 2 units flowing from u to v. Choice B ignores the reversal completely. Choice C incorrectly assumes the reversal creates flow in the opposite direction. Choice D ignores the reversal operation.

Question 5

A flow network has source $s$ , sink $t$ , and intermediate vertices $a$ and $b$ . The edges are: $s \to a$ (capacity 10), $s \to b$ (capacity 8), $a \to t$ (capacity 6), $b \to t$ (capacity 12). What constraint must any feasible flow satisfy?

Flow into $t$ cannot exceed min(6 + 12, 10 + 8) = 18 units
Flow out of $s$ cannot exceed min(10, 8) = 8 units total
Flow into $a$ must equal flow out of $a$ at all times (correct answer)
Total flow cannot exceed max(6, 8, 10, 12) = 12 units

Explanation: Flow conservation requires that for any intermediate vertex (not source or sink), flow in equals flow out. This must hold for vertices a and b. Choice A incorrectly adds capacities without considering bottlenecks. Choice B incorrectly applies min to source capacities. Choice D incorrectly uses the maximum single edge capacity as a flow bound.

Question 6

In the Ford-Fulkerson algorithm, an augmenting path is found from source to sink with bottleneck capacity 4. After augmenting along this path, which statement about the residual graph is necessarily true?

At least one forward edge on the path has its capacity reduced to zero
The maximum flow value increases by exactly 4 units from its previous value (correct answer)
All edges on the augmenting path now have residual capacity of exactly 4
The number of saturated edges in the network increases by exactly one

Explanation: By definition, augmenting along a path with bottleneck capacity 4 increases the total flow by exactly 4 units. Choice A is incorrect because edges might have had capacity > 4. Choice C is wrong because residual capacities depend on original capacities minus the bottleneck. Choice D is incorrect because multiple edges might become saturated, or the number might not change.

Question 7

In a unit capacity flow network (all edges have capacity 1), the maximum flow value is 4. A student claims that there must exist 4 vertex-disjoint paths from $s$ to $t$ . Which statement correctly evaluates this claim?

The claim is always true by Menger's theorem, since max flow equals vertex connectivity
The claim is true only if no vertex other than $s$ and $t$ has degree greater than 2
The claim is false; edge-disjoint paths are guaranteed, but vertex-disjoint paths require additional conditions (correct answer)
The claim is false unless the network is a planar graph with specific structural properties

Explanation: When you encounter flow network problems involving path decompositions, you need to distinguish carefully between edge-disjoint and vertex-disjoint paths—they're related but not equivalent concepts. The correct answer is C because the max-flow min-cut theorem guarantees that a flow of value 4 in a unit capacity network can always be decomposed into 4 edge-disjoint paths from

s

t

. However, vertex-disjoint paths are a stronger requirement: they cannot share any internal vertices (vertices other than

s

and

t

). This additional constraint means that even when 4 edge-disjoint paths exist, they might converge through common intermediate vertices, preventing a vertex-disjoint decomposition. Option A misapplies Menger's theorem. While Menger's theorem does relate maximum flow to connectivity, it specifically connects max flow to edge connectivity in this context, not vertex connectivity. The vertex version of Menger's theorem would require constructing a different network model. Option B suggests a degree-based condition, but vertex degrees don't directly determine whether edge-disjoint paths can be rearranged into vertex-disjoint ones. The relationship is more complex and depends on the overall network structure. Option D incorrectly introduces planarity as a relevant factor. Planar graph properties don't govern the relationship between edge-disjoint and vertex-disjoint path decompositions. Study tip: Remember that max flow problems naturally give you edge-disjoint paths. Getting vertex-disjoint paths requires additional structural analysis of the network—don't assume one automatically implies the other.

Question 8

A flow network has the property that in any maximum flow, edge $(u,v)$ carries exactly half of its capacity. If the capacity of $(u,v)$ is 6, and we decrease it to 4, what is the maximum possible decrease in the maximum flow value?

2 units, equal to the capacity reduction since the edge was partially utilized
3 units, representing the original flow amount that can no longer be maintained
1 unit, because the edge was only carrying 3 units and still has capacity for 4
0 units, since the reduced capacity still exceeds the original flow on this edge (correct answer)

Explanation: If edge

(u,v)

carries exactly half its capacity in any maximum flow, it carries

6/2 = 3

units of flow. When we reduce capacity to 4, this edge can still carry its required 3 units of flow. Since the edge was not a bottleneck (it wasn't at full capacity), reducing its capacity to a value still above its required flow doesn't affect the maximum flow. The bottlenecks are elsewhere in the network. Choices A, B, and C incorrectly assume this edge becomes a limiting factor.

Question 9

Consider a flow network where the maximum flow is 10. After applying the Ford-Fulkerson algorithm, we obtain a minimum cut $C$ with capacity 10. If we add a new edge with capacity 5 that crosses this cut from the source side to the sink side, what is the new maximum flow?

15, since we added 5 units of capacity directly across the bottleneck cut (correct answer)
12, because network topology constraints limit the effective use of added capacity
10, since other cuts in the network may become the new bottleneck
Between 10 and 15, depending on the specific placement and network structure

Explanation: When we add an edge of capacity 5 across the minimum cut, the capacity of cut

C

increases from 10 to 15. Since

C

was the minimum cut, and we've only increased its capacity (not decreased any other cut's capacity), the new minimum cut capacity is at least 15. The new maximum flow will be exactly 15 because we can achieve this by routing 5 additional units through the new edge while maintaining the original flow of 10. No other cut can have capacity less than 15 after this addition. Choices B and C underestimate the impact. Choice D is unnecessarily vague.

Question 10

A flow network has a cut $S = \{s, v_1, v_2\}$ and $T = \{v_3, v_4, t\}$ with cut capacity 15. If the maximum flow value is 12, which statement about this network is necessarily true?

There exists an augmenting path from $s$ to $t$ with bottleneck capacity 3
The cut $S, T$ is not a minimum cut, and there exists a cut with capacity 12 (correct answer)
All edges crossing from $S$ to $T$ have total unused capacity of exactly 3 units
The residual graph contains no path from $s$ to $t$ with positive capacity available

Explanation: By the max-flow min-cut theorem, the maximum flow value equals the minimum cut capacity. Since max flow = 12 but this cut has capacity 15, this cut cannot be a minimum cut. There must exist a cut with capacity exactly 12. Choice A is wrong because no augmenting path exists when max flow is achieved. Choice C is wrong because the cut capacity minus flow value doesn't directly relate to unused capacity on cut edges. Choice D is wrong because while true that no augmenting paths exist at maximum flow, this doesn't address the key relationship between cut capacity and flow value.

Question 11

In a flow network, edge $(u,v)$ has capacity 10 and currently carries flow 7. Edge $(v,u)$ has capacity 4 and currently carries flow 1. What is the residual capacity from $u$ to $v$ in the residual graph?

3 units, representing only the unused forward capacity on edge $(u,v)$
4 units, accounting for both unused forward capacity and potential flow cancellation (correct answer)
1 unit, determined by the minimum of forward unused and reverse flow capacities
6 units, combining forward residual capacity with the ability to reduce reverse flow

Explanation: Residual capacity from

u

v

includes: (1) unused forward capacity on

(u,v)

: 10-7=3 units, and (2) current flow on

(v,u)

that can be cancelled: 1 unit. Total residual capacity = 3+1=4 units. Choice A ignores flow cancellation. Choice C incorrectly applies a minimum operation. Choice D incorrectly adds the full reverse edge capacity rather than just the current reverse flow.

Question 12

A flow network has source $s$ , sink $t$ , and intermediate vertices $\{v_1, v_2, v_3, v_4\}$ . The minimum cut has capacity 8 and separates vertices $\{s, v_1\}$ from $\{v_2, v_3, v_4, t\}$ . If we increase the capacity of edge $(v_1, v_2)$ by 3 units, what can we conclude about the new maximum flow?

The maximum flow increases by exactly 3 units since we enhanced a cut edge directly
The maximum flow remains unchanged because other bottlenecks will limit the improvement
The maximum flow increases by at most 3 units, but may increase by less (correct answer)
The maximum flow increases by 3 units unless this creates a new minimum cut elsewhere

Explanation: When analyzing flow networks and cuts, remember that the max-flow min-cut theorem establishes a fundamental relationship: the maximum flow equals the minimum cut capacity. Understanding how modifications affect this relationship is crucial for network optimization problems. The minimum cut with capacity 8 separates

\{s, v_1\}

from

\{v_2, v_3, v_4, t\}

, meaning edge

(v_1, v_2)

is indeed part of this cut since it crosses the partition. Increasing its capacity by 3 units raises the cut's total capacity to 11, which means the maximum flow could potentially increase by up to 3 units. However, the actual increase depends on whether other cuts in the network become limiting factors. After the modification, there might be other cuts with capacity 8 or less that now become the new minimum cut. The maximum flow can only increase until it hits the next bottleneck in the network. Option A incorrectly assumes the increase is exactly 3 units, ignoring other potential bottlenecks. Option B wrongly claims no change will occur, but since we're modifying a minimum cut edge, some improvement is likely unless there's an identical minimum cut elsewhere. Option D suggests the flow increases by 3 units unless a new minimum cut appears, but even then, the increase could be less than 3 if that new cut has capacity between 8 and 11. Option C correctly states the maximum possible increase is 3 units while acknowledging it could be less due to other network constraints. Study tip: When modifying cut edges, always consider that multiple cuts may exist with similar capacities, creating cascading bottleneck effects.

Question 13

In a flow network, vertex $v$ has incoming edges with flows 7, 3, and 2, and outgoing edges with flows 5 and $x$ . If $v$ is neither source nor sink, what is the value of $x$ ?

$x = 7$ by flow conservation at intermediate vertices (correct answer)
$x = 12$ to equal total incoming flow
$x = 2$ to match the smallest incoming flow
$x = 17$ to equal sum of all other flows

Explanation: Flow conservation requires that flow in equals flow out at any intermediate vertex. Total incoming flow = 7 + 3 + 2 = 12. Total outgoing flow = 5 + x. Therefore 12 = 5 + x, which gives x = 7. Choice B incorrectly sets x equal to total incoming flow. Choices C and D use arbitrary relationships unrelated to flow conservation.

Question 14

A flow network has integer edge capacities. During Ford-Fulkerson execution, an augmenting path is found with bottleneck capacity 2.5. What can be concluded?

The algorithm implementation contains an error in capacity calculation
Previous augmentations must have used non-integer flow values
The residual graph construction is incorrect for this iteration
This scenario is impossible with integer capacities and proper execution (correct answer)

Explanation: If all original capacities are integers and the algorithm starts with zero flow, then all flows and residual capacities remain integers throughout execution. A fractional bottleneck capacity of 2.5 is impossible. Choice A suggests implementation error but not the fundamental impossibility. Choice B is incomplete. Choice C focuses on one iteration rather than the systematic constraint.

Question 15

In a flow network, the maximum flow value is 12. If we add a new edge from source to sink with capacity 8, what is the new maximum flow value?

Exactly 20 since we add 8 units of direct capacity
At most 20 since the new edge provides at most 8 additional units (correct answer)
Exactly 12 since the bottleneck constraints remain unchanged
At least 12 but could be less if the new edge creates conflicts

Explanation: Adding a direct source-to-sink edge with capacity 8 can increase the maximum flow by at most 8 units, giving an upper bound of 12 + 8 = 20. However, other bottlenecks in the network might prevent achieving this full increase. Choice A assumes the full 8 units are always achievable. Choice C ignores the new capacity entirely. Choice D incorrectly suggests flow could decrease.

Question 16

In the residual graph of a flow network, vertex $v$ can reach vertex $w$ along a path of residual edges. In the original network with current flow, what does this path represent?

There exists unused capacity along some direct route from $v$ to $w$
Flow can be rerouted to increase the total amount reaching $w$ from $v$
The current flow from $v$ to $w$ is suboptimal and can be improved
There are potential flow adjustments that can transfer flow from $v$ toward $w$ (correct answer)

Explanation: A path in the residual graph represents potential flow adjustments: pushing flow along forward edges with unused capacity, or reducing flow along backward edges. This creates a sequence of adjustments that effectively transfers flow from v toward w. Choice A is too narrow (only considers unused capacity). Choice B assumes the goal is increasing flow to w. Choice C incorrectly implies current flow is suboptimal.

Question 17

A cut $(S,T)$ in a flow network separates source from sink with capacity 20. The current flow value is 15. What is the minimum number of edges that must cross from $S$ to $T$ ?

At least 1 edge must cross from $S$ to $T$
At least 3 edges since $\lceil 20/7 \rceil = 3$
At least 4 edges since flow is 15 and capacity is 20
Cannot determine without knowing individual edge capacities (correct answer)

Explanation: The number of edges crossing a cut depends on the network structure, not just the cut capacity or flow value. A single edge could have capacity 20, or twenty edges could each have capacity 1. The cut capacity of 20 and flow of 15 don't determine the edge count. Choice A assumes at least one edge (true but not minimal constraint). Choices B and C use arbitrary arithmetic unrelated to the actual constraint.

Question 18

The Ford-Fulkerson algorithm terminates when no augmenting path exists from source to sink. At this point, which statement about the residual graph is correct?

All edges from source vertices have zero residual capacity remaining
There exists a cut where all forward edges are saturated and all backward edges carry zero flow
The source and sink belong to different strongly connected components
Every path from source to sink contains at least one edge with zero residual capacity (correct answer)

Explanation: When no augmenting path exists, every possible path from source to sink must contain at least one bottleneck edge with zero residual capacity, otherwise that path would be augmenting. Choice A is too strong - not all source edges need be saturated. Choice B describes a min-cut but not necessarily the residual graph state. Choice C uses incorrect terminology (strongly connected components apply to directed graphs differently).

Question 19

Consider a minimum cut $(S,T)$ with capacity $C$ . If we increase the capacity of every edge crossing from $S$ to $T$ by 1, what is the new maximum flow value?

Exactly $C + 1$ since only one unit of additional flow is possible
At least $C + k$ where $k$ is the number of edges crossing from $S$ to $T$
At most $C + k$ where $k$ is the number of edges crossing from $S$ to $T$ (correct answer)
Exactly $C + k$ where $k$ is the number of edges crossing from $S$ to $T$

Explanation: Increasing each edge capacity by 1 increases the cut capacity by k (number of edges). The max flow can increase by at most k, but might be limited by other cuts that become minimum after this change. Choice A assumes only 1 unit increase total. Choice B claims at least k increase, which isn't guaranteed due to other bottlenecks. Choice D assumes exactly k increase, ignoring other potential cuts.

Question 20

A flow network has maximum flow value 15. After removing a single edge, the maximum flow becomes 12. What can be concluded about the removed edge?

The edge had capacity exactly 3 in the original network
The edge carried flow of exactly 3 in some maximum flow
The edge was part of every minimum cut in the original network (correct answer)
The edge had residual capacity of 3 in the final iteration

Explanation: If removing a single edge reduces max flow by exactly 3, that edge must be critical - it appears in every minimum cut. The flow decrease equals the minimum amount that edge contributes across all cuts. Choice A is wrong because the edge capacity could be larger than 3. Choice B is incorrect because the edge might carry different flows in different maximum flows. Choice D confuses residual capacity with flow contribution.