Skip to content

Introduction to Network Flow

This page introduces fundamental concepts related to network flow.

Overview

A network is a special directed graph \( G = (V, E) \), which differs from a general directed graph in that it has capacities and source/sink nodes.

  • Each edge \((u, v) \in E\) has a weight called capacity, denoted as \( c(u, v) \). When \((u, v) \notin E\), we assume \( c(u, v) = 0 \).
  • There are two special nodes in \( V \): the source \( s \) and the sink \( t \) (with \( s \neq t \)).

For a network \( G = (V, E) \), a flow is a function from the edge set \( E \) to the set of integers or real numbers, satisfying the following properties:

  1. Capacity constraint: For each edge, the flow passing through it must not exceed its capacity, i.e., \( 0 \leq f(u, v) \leq c(u, v) \).
  2. Flow conservation: Except for the source and sink, the net flow of any node \( u \) is zero. Here, we define the net flow of \( u \) as \( f(u) = \sum_{x \in V} f(u, x) - \sum_{x \in V} f(x, u) \).

For a network \( G = (V, E) \) and a flow \( f \) on it, we define the value \( |f| \) of \( f \) as the net flow \( f(s) \) of the source \( s \). As a corollary of flow conservation, this is also equal to the opposite of the net flow of the sink \( t \), i.e., \( -f(t) \).

For a network \( G = (V, E) \), if \( \{S, T\} \) is a partition of \( V \) (i.e., \( S \cup T = V \) and \( S \cap T = \varnothing \)) and satisfies \( s \in S, t \in T \), then we call \( \{S, T\} \) an \( s \)-\( t \) cut of \( G \). We define the capacity of the \( s \)-\( t \) cut \( \{S, T\} \) as \( \|S, T\| = \sum_{u \in S} \sum_{v \in T} c(u, v) \).

Common Problems

Common network flow problems include, but are not limited to, the following types:

  • Maximum flow problem: For a network \( G = (V, E) \), assign flow to each edge to obtain a feasible flow \( f \) such that the value \( |f| \) is as large as possible. In this case, we call \( f \) a maximum flow of \( G \).
  • Minimum cut problem: For a network \( G = (V, E) \), find an \( s \)-\( t \) cut \( \{S, T\} \) such that the capacity \( \|S, T\| \) is as small as possible. In this case, we call \( \|S, T\| \) the minimum cut of \( G \).
  • Minimum cost maximum flow problem: In a network \( G = (V, E) \), assign a weight \( w(u, v) \) to each edge, called the cost, which represents the cost per unit of flow passing through \( (u, v) \). Among all possible maximum flows of \( G \), we call the one with the smallest total cost the minimum cost maximum flow.

We will introduce these problems in detail in later sections.

Example: Network Flow 24 Problems

The Network Flow 24 Problems is a widely circulated problem list in the Chinese internet (LibreOJ/Luogu), which has existed at least around 2010. This list introduces some classic techniques for modeling other problems as network flow problems. Due to the limitations of the era, these problems may not be the most representative network flow problems, but they are still worth reading for readers interested in algorithm competitions.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用