網絡流簡介

本頁面主要介紹網絡流相關的基本知識。

概述

網絡（network）是指一個特殊的有向圖 \(G=(V,E)\)，其與一般有向圖的不同之處在於有容量和源匯點。

\(E\) 中的每條邊 \((u, v)\) 都有一個被稱為容量（capacity）的權值，記作 \(c(u, v)\)。當 \((u,v)\notin E\) 時，可以假定 \(c(u,v)=0\)。
\(V\) 中有兩個特殊的點：源點（source）\(s\) 和匯點（sink）\(t\)（\(s \neq t\)）。

對於網絡 \(G=(V, E)\)，流（flow）是一個從邊集 \(E\) 到整數集或實數集的函數，其滿足以下性質。

容量限制：對於每條邊，流經該邊的流量不得超過該邊的容量，即 \(0 \leq f(u,v) \leq c(u,v)\)；
流守恆性：除源匯點外，任意結點 \(u\) 的淨流量為 \(0\)。其中，我們定義 \(u\) 的淨流量為 \(f(u) = \sum_{x \in V} f(u, x) - \sum_{x \in V} f(x, u)\)。

對於網絡 \(G = (V, E)\) 和其上的流 \(f\)，我們定義 \(f\) 的流量 \(|f|\) 為 \(s\) 的淨流量 \(f(s)\)。作為流守恆性的推論，這也等於 \(t\) 的淨流量的相反數 \(-f(t)\)。

對於網絡 \(G = (V, E)\)，如果 \(\{S, T\}\) 是 \(V\) 的劃分（即 \(S \cup T = V\) 且 \(S \cap T = \varnothing\)），且滿足 \(s \in S, t \in T\)，則我們稱 \(\{S, T\}\) 是 \(G\) 的一個 \(s\)-\(t\) 割（cut）。我們定義 \(s\)-\(t\) 割 \(\{S, T\}\) 的容量為 \(||S, T|| = \sum_{u \in S} \sum_{v \in T} c(u, v)\)。

常見問題

常見的網絡流問題包括但不限於以下類型問題。

最大流問題：對於網絡 \(G = (V, E)\)，給每條邊指定流量，得到合適的流 \(f\)，使得 \(f\) 的流量儘可能大。此時我們稱 \(f\) 是 \(G\) 的最大流。
最小割問題：對於網絡 \(G = (V, E)\)，找到合適的 \(s\)-\(t\) 割 \(\{S, T\}\)，使得 \(\{S, T\}\) 的容量儘可能小。此時我們稱 \(\{S, T\}\) 是 \(G\) 的最小割。
最小費用最大流問題：在網絡 \(G = (V, E)\) 上，對每條邊給定一個權值 \(w(u, v)\)，稱為費用（cost），含義是單位流量通過 \((u, v)\) 所花費的代價。對於 \(G\) 所有可能的最大流，我們稱其中總費用最小的一者為最小費用最大流。

我們將在稍後的章節中對它們進行詳細介紹。

例題：網絡流 24 題

網絡流 24 題是中文互聯網上廣泛流傳的一個題單（LibreOJ/洛谷），至少在 2010 年前後就已經存在。該題單引入了一些經典的將其他問題建模為網絡流問題的技巧。由於時代的侷限性，這些問題未必是最具代表性的網絡流問題，但仍值得有志於算法競賽的讀者一閲。

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