Network flow concepts (max flow intro) - Discrete Math

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?
Answer: 22 units, including all edges with their unit capacities in the flow network construction 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.
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?
Answer: Exactly 3 units total through the network 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.
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$ ?
Answer: 2 units from $u$ to $v$ 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.
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?
Answer: 15, since we added 5 units of capacity directly across the bottleneck cut 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.
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?
Answer: 4 units, accounting for both unused forward capacity and potential flow cancellation Residual capacity from $u$ to $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.
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?
Answer: The cut $S, T$ is not a minimum cut, and there exists a cut with capacity 12 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.
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?
Answer: Flow into $a$ must equal flow out of $a$ at all times 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.
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$ ?
Answer: Cannot determine without knowing individual edge capacities 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.
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?
Answer: The maximum flow value increases by exactly 4 units from its previous value 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.
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?
Answer: The maximum flow increases by at most 3 units, but may increase by less 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.
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?
Answer: The claim is false; edge-disjoint paths are guaranteed, but vertex-disjoint paths require additional conditions 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$ to $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.
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?
Answer: Capacity 1 to ensure each left vertex matches at most once 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.
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?
Answer: Every path from source to sink contains at least one edge with zero residual capacity 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).
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?
Answer: At most 20 since the new edge provides at most 8 additional units 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.
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?
Answer: The edge was part of every minimum cut in the original network 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.
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?
Answer: This scenario is impossible with integer capacities and proper execution 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.
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?
Answer: There are potential flow adjustments that can transfer flow from $v$ toward $w$ 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.
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?
Answer: 0 units, since the reduced capacity still exceeds the original flow on this edge 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.
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$ ?
Answer: $x = 7$ by flow conservation at intermediate vertices 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.
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?
Answer: At most $C + k$ where $k$ is the number of edges crossing from $S$ to $T$ 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.

Start this quiz