Questions: Network Flow Models and Feasibility

Question 1

Which pair of constraints must every valid flow in a network satisfy?

• A. Flow on each edge equals its capacity AND total flow into source equals total flow out of sink
• B. Flow on each edge does not exceed its capacity AND inflow equals outflow at every internal vertex
• C. Flow on each edge is positive AND at least one path from source to sink is fully saturated
• D. Inflow equals outflow at every vertex including source and sink AND no cycles carry flow

Answer: (B)

A valid flow satisfies exactly two constraints: the capacity constraint (flow on each directed edge ≤ capacity of that edge) and the conservation constraint (inflow = outflow at every vertex except the source and sink). Option D is wrong because conservation does NOT apply at the source and sink — the source has net outflow and the sink has net inflow, which is the whole point. Option A incorrectly requires flow to equal capacity (that would be a saturating flow, not any valid flow).

Question 2

A flow network has a minimum cut with capacity 7. What is the maximum possible flow value from source to sink?

• A. It cannot be determined without knowing the individual edge capacities
• B. It must be exactly 7, by the max-flow min-cut theorem
• C. It must be at least 7, since the cut is a lower bound
• D. It is at most 7 but may be less depending on the network structure

Answer: (B)

The max-flow min-cut theorem is an exact equality: the maximum flow value equals the minimum cut capacity. If the min-cut is 7, then the max flow is exactly 7 — not 'at most' and not 'cannot be determined.' The minimum cut represents the tightest bottleneck separating source from sink; no flow can exceed it (any flow must cross every cut), and algorithms like Ford-Fulkerson show the maximum can always be achieved.

Question 3

The maximum flow through a network can exceed the minimum cut capacity if the network has enough parallel paths from source to sink.

• T. True
• F. False

Answer: False

No. Every flow must cross every cut — any path from source to sink crosses a cut at least once. The total flow across a cut cannot exceed the sum of capacities of edges crossing from the source side to the sink side. The minimum cut is the tightest such bottleneck, so it is an absolute upper bound on flow. The max-flow min-cut theorem says the maximum flow achieves this bound exactly, not that it merely approaches it.

Question 4

A flow that sends zero units along every edge is always a valid feasible flow in any network.

• T. True
• F. False

Answer: True

The zero flow trivially satisfies both constraints: every edge carries 0, which is ≤ any non-negative capacity, and inflow = outflow = 0 at every vertex. This makes it a valid feasible flow with value 0. It is not interesting or useful, but its existence guarantees that the feasibility problem always has a trivial solution. The non-trivial question is how to find a feasible flow with maximum value.

Question 5

What does flow conservation mean in a network flow model, and why is it a necessary constraint for the model to represent real-world routing problems?

Model answer: Flow conservation means that at every internal vertex (every node except source and sink), the total flow on incoming edges equals the total flow on outgoing edges. It is necessary because in any physical routing problem — traffic, data packets, water pipes, goods in supply chains — material doesn't spontaneously appear or disappear at intermediate nodes. What flows into a junction must flow out. Without conservation, the model could 'create' flow at intermediate nodes, making the computed flow meaningless for describing real systems.

Conservation is what gives network flows their power as models. It abstracts away the specifics of what is flowing and captures the universal constraint that resources are neither created nor destroyed in transit. The single exception — the source produces flow and the sink absorbs it — corresponds directly to the origin and destination in the real problem. This also means the value of a flow (total leaving source) must equal total entering sink, a consequence of conservation applied globally.