Which two conditions must a flow satisfy?

Capacity constraint and conservation at vertices other than s and t

Every edge saturated and no sink

Flow in at s equals flow out at t on each edge

How is the value of a flow defined?

Total flow leaving s (equal to total entering t)

What does Ford-Fulkerson repeat until it stops?

Find an augmenting path with spare capacity and push the bottleneck amount

In the example (s->a 3, s->b 2, a->b 1, a->t 2, b->t 3), why is the max flow 5?

Cut S = {s} has capacity 3 + 2 = 5, which equals the maximum flow

It is the sum of all capacities

It is the capacity of a->t plus b->t minus 1

It is the largest edge capacity plus 2

2070 Magh · 3 marks

Short note: Network flows

Short answer

A flow network is a directed graph with source s, sink t, and edge capacities. A flow satisfies capacity and conservation constraints. The Ford-Fulkerson algorithm finds maximum flow using augmenting paths. The max-flow min-cut theorem states that max flow equals the minimum cut capacity.

Write a short note on network flows.

A transport network (flow network) is a connected directed graph with a source s (no incoming edges), a sink t (no outgoing edges), and a non-negative capacity c(e) on every edge.

A flow assigns a value f(e) to each edge such that:

Capacity constraint: 0 ≤ f(e) ≤ c(e).
Conservation: at every vertex other than s and t, the total flow in equals the total flow out.

The value of the flow is the total flow leaving s (equal to the total entering t).

The maximum flow problem asks for the largest possible value. Ford–Fulkerson algorithm: begin with zero flow, find an augmenting path from s to t in which every edge has spare capacity (using the residual graph, which also allows undoing flow), push the bottleneck amount, and repeat until no such path exists.

Max-flow min-cut theorem: the maximum flow value equals the minimum capacity among all cuts (S, T), where s ∈ S, t ∈ T and the capacity is the total capacity of edges from S to T.

Example: edges s→a 3, s→b 2, a→b 1, a→t 2, b→t 3 give max flow 5, equal to the capacity of the cut S = {s} (3 + 2 = 5).

Applications: traffic and pipeline networks, data routing, bipartite matching, project selection.

✓ Answer checked by Claude Opus 5.5 (high effort)

Correct trial network flows and pressure at C · Hydraulics, chapter 3
Pressure drop in a pipe network · Applied Computational Fluid Dynamics, chapter 6

All Discrete Structure chapter 4 questions →

Short note: Network flows

Related questions