gen-define-maximum-flow-and-give-one-short-worked-example-ad8e

Define maximum flow and give one short worked example.

# Maximum Flow ## Definition **Maximum flow** is the greatest amount of flow that can be sent from a source node **s** to a sink node **t** in a flow network, subject to capacity constraints on edges. A flow network is a directed graph where: - Each edge has a non-negative capacity - Flow on each edge ≤ capacity of that edge - Flow conservation: flow into a node = flow out (except at s and t) --- ## Worked Example Consider this network (capacities shown on edges): ``` 10 10 s ----→ a ----→ t | ↗ ↑ 5 | / 5 5 | ↓ / | b ------------→ c 10 ``` **Capacities:** - s→a: 10, s→b: 5 - a→t: 10, b→a: 5, b→c: 10 - c→t: 5 **Finding maximum flow:** 1. **Path s→a→t:** Send 10 units (limited by min capacity = 10) 2. **Path s→b→c→t:** Send 5 units (limited by c→t capacity = 5) **Maximum flow = 15 units** **Flow assignment:** - s→a: 10, a→t: 10 - s→b: 5, b→c: 5, c→t: 5 We cannot send more because the total capacity leaving s is 15, which forms a bottleneck (this is a minimum cut).