Course contentsShow
← Mathematics
Lesson 2704 of 3,12153. Graph TheoryFree lesson

Networks and Flows: Definitions and Notation

Define flow networks, sources, sinks, capacities, flows, and the conservation of flow at intermediate vertices.

Networks and Flows: Definitions and Notation

What you'll learn: You'll understand how to model flow through a network using sources, sinks, capacities, and the conservation law that governs flow at intermediate points.

The Core Idea

Imagine water flowing through a system of pipes, or data packets traveling through a computer network. A flow network is a directed graph that models such scenarios mathematically.

A flow network consists of:

  • Vertices (nodes): Points where flow can enter, exit, or pass through
  • Directed edges: Pipes or channels connecting vertices
  • Source (s): A special vertex where flow originates (like a water pump)
  • Sink (t): A special vertex where flow terminates (like a drain)
  • Capacity c(u,v): The maximum amount of flow that can travel along edge (u,v)
  • Flow f(u,v): The actual amount currently flowing along edge (u,v)

Flow Rules

Two fundamental constraints govern valid flows:

  1. Capacity constraint: For every edge (u,v), we must have 0 ≤ f(u,v) ≤ c(u,v). You can't push more flow than the pipe allows.

  2. Flow conservation: At every intermediate vertex v (neither source nor sink), the total flow entering v equals the total flow leaving v. Think of it like traffic at an intersection—if 10 cars enter per minute, 10 must leave (nothing accumulates or disappears).

Mathematically: Σ f(u,v) = Σ f(v,w) for all incoming edges (u,v) and outgoing edges (v,w).

The value of the flow is the total amount leaving the source (or equivalently, reaching the sink).

Key Takeaway: A flow network models movement through a directed graph with a source, sink, edge capacities, and flows that respect capacity limits and conserve at intermediate vertices.