Course contentsShow
← Computer Science
Lesson 1022 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Flow Networks and Definitions

Understand directed graphs with capacities, sources, sinks, and the concept of flow as a function on edges.

Flow Networks and Definitions

What you'll learn: You'll understand how flow networks model real-world transport systems using directed graphs with capacity constraints.

What Is a Flow Network?

A flow network is a directed graph designed to model the movement of "stuff" (water, data, traffic, goods) from a starting point to an ending point. Think of it like a city's water pipe system: water flows from a reservoir through pipes of different sizes to homes.

Formally, a flow network consists of:

  • A directed graph G = (V, E)
  • A source vertex s (where flow originates)
  • A sink vertex t (where flow terminates)
  • A capacity function c(u, v) ≥ 0 for each edge (u, v), representing the maximum flow that edge can carry

The Flow Function

The flow is a function f(u, v) on edges that represents how much is actually flowing through each edge, subject to two key rules:

  1. Capacity constraint: For every edge (u, v), the flow cannot exceed capacity: 0 ≤ f(u, v) ≤ c(u, v)

  2. Flow conservation: For every vertex except s and t, flow in equals flow out: ∑(flow in) = ∑(flow out)

Intuitive Example

Imagine a highway network:

  • Source (s): City center where all traffic starts
  • Sink (t): Suburbs where everyone goes
  • Capacities: Lane counts on roads (2-lane road = capacity 2000 cars/hour)
  • Flow: Actual cars traveling each road segment

The flow can't exceed road capacity, and at every intersection (except start/end), cars entering must equal cars leaving.

Key Takeaway: Flow networks model transport through directed graphs with capacities, where flow must respect capacity limits and conserve at intermediate vertices.