---
title: "Short note: Network flows"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:network-flows-short-note"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/network-flows-short-note
site: BCT Engineering
---

# Short note: Network flows

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2070 Magh, 3 marks
- Video: [32. Network Flow](https://www.youtube.com/watch?v=eVhRZgwqzOM) — itechnica
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/network-flows-short-note
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on 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.

## Answer

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:
1. Capacity constraint: 0 ≤ f(e) ≤ c(e).
2. 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which two conditions must a flow satisfy?
   A. Capacity constraint and conservation at vertices other than s and t
   B. Every edge saturated and no sink
   C. Flow equals zero at s and t
   D. Flow in at s equals flow out at t on each edge
   Answer: A. 0 <= f(e) <= c(e), and at every other vertex inflow equals outflow. (Key point: Flow conditions)

2. How is the value of a flow defined?
   A. Sum of all edge capacities
   B. Number of edges used
   C. Total flow leaving s (equal to total entering t)
   D. Largest single edge flow
   Answer: C. It is the net amount sent from source to sink. (Key point: Flow value)

3. What does Ford-Fulkerson repeat until it stops?
   A. Delete the largest edge
   B. Find an augmenting path with spare capacity and push the bottleneck amount
   C. Sort edges by weight
   D. Color vertices
   Answer: B. It uses the residual graph and stops when no augmenting path exists. (Key point: Ford-Fulkerson)

4. In the example (s->a 3, s->b 2, a->b 1, a->t 2, b->t 3), why is the max flow 5?
   A. Cut S = {s} has capacity 3 + 2 = 5, which equals the maximum flow
   B. It is the sum of all capacities
   C. It is the capacity of a->t plus b->t minus 1
   D. It is the largest edge capacity plus 2
   Answer: A. Max flow equals the minimum cut capacity; the cut {s} gives 5. (Key point: Max-flow min-cut)

## Related in other subjects

- [Correct trial network flows and pressure at C](https://www.bctengineer.com/question.md?key=semester_4%2Fhydraulics%3Anetwork-distribution-trial-pressure-at-c) — Hydraulics, chapter 3
- [Pressure drop in a pipe network](https://www.bctengineer.com/question.md?key=semester_7%2Fapplied_computational_fluid_dynamics%3Apipe-network-pressure-drop-numerical) — Applied Computational Fluid Dynamics, chapter 6