跳到正文
格致开物MATHWIKI
数学百科/知识地图

网络流与最大流最小割

网络流研究有方向、有容量的网络中，多少量可以从源点送到汇点。水管、道路、通信链路都能画成网络，但“能送多少”只有在每条边的容量和中间节点的收支都定义清楚后，才是一个数学问题。本篇从四个节点的例子出发，得到最大流最小割定理，并说明如何计算及核验答案。

一张容量图

设源点 s 将物资送到汇点 t，中转点为 a,b。下表中的容量单位统一为“箱／小时”。箭头表示允许的运输方向，容量为一的 a→b 不能反过来当作现成道路。

边 s→a s→b a→b a→t b→t
容量 3 2 1 2 3
源点s向a和b的容量分别为三和二，a向b容量一，a和b向汇点t的容量分别为二和三；虚线将源点与其余节点分开
切开源点的两条出边，容量合计五。这给任何可行运输方案一个上界。

先送 2 箱沿 s→a→t，再送 2 箱沿 s→b→t，最后送 1 箱沿 s→a→b→t。逐边相加，流量依次为 3,2,1,2,3，都没有超过容量；在 a 处流入三、流出 2+1，在 b 处流入 2+1、流出三。可见至少能送五箱。

仅看 s 的两条出边，容量共 3+2=5，无论后面怎样绕行都不能从它送出更多。于是本例最大流恰为五。这个“一个可行方案给下界、一组瓶颈边给上界”的证据，比求解器单独报出数字五更可靠。

可行流、流值与割

把网络写成有向图 G=(V,E)。每条边 (u,v) 有非负容量 cuv 和流量 fuv，满足 0≤fuv≤cuv. 对每个既非 s 又非 t 的节点，流守恒要求所有入流之和等于所有出流之和。流值 |f| 定义为源点净流出量；它也等于汇点净流入量。若有多条原始边方向相反，净流出仍须把流入源点的量减掉。

s—t 割是把全部节点分成 S 与 T=V∖S，其中 s∈S,t∈T。割的容量只加从 S 指向 T 的原始边： c(S,T)=∑u∈S,v∈Tcuv. 反向边不是“负容量”。把 S 内所有节点的流守恒式相加，内部边一进一出相互抵消，只剩边界： |f|=∑u∈S,v∈Tfuv−∑u∈T,v∈Sfuv≤∑u∈S,v∈Tcuv=c(S,T). 所以任意流值都不超过任意割容量。本例取 S={s}，得到上界五。这个不等式已经是可独立使用的容量证书。

增广路与反向剩余边

若某条边容量为三、当前已用两，向前还可多送一；同时可以撤回其中至多两。分别把这两种调整记成容量为一的前向剩余边和容量为二的反向剩余边。反向边不代表现实世界新修了一条路，它记录“改派先前已分配的流”。在剩余网络中从 s 到 t 的路径称为增广路；沿路增加不超过最小剩余容量的量，仍能保持原网络可行。

反向边确实有用。另看五条容量全为一的边：s→a,s→b,a→b,a→t,b→t。如果先沿 s→a→b→t 送一，眼前两条终点边中 b→t 已满。剩余网络却还有 s→b→a→t；其中 b→a 是撤回原先 a→b 的一步。调整后两条实物流路变为 s→a→t 和 s→b→t，总量为二。只在原图上贪心找新路径会错过它。

最大流最小割定理

定理。在有限有向网络、非负有限容量下，最大可行流值等于最小 s—t 割容量。

前面的边界求和已证明“最大流不超过最小割”。现在考虑一个没有增广路的可行流。令 S 为从 s 沿正剩余容量的边仍能到达的全部节点。因为到不了 t，(S,V∖S) 确是一个割。

若有原始边从 S 指向外部且未满，它的前向剩余容量为正，终点也应该可达，矛盾；所以所有这些边都已满。若有原始边从外部指向 S 且上面仍有正流，它的反向剩余边会让外部节点可达，同样矛盾；所以跨割的反向原始边流量均为零。代回边界等式便得到 |f|=∑u∈S,v∉Scuv=c(S,V∖S). 这个流达到了某个割给出的上界，因此它最大，该割也最小。证明同时给出了一种验收办法：找到可行流，并找一个同值的割。

用广度优先搜索计算

每次在剩余网络中用广度优先搜索找边数最少的增广路，就是 Edmonds–Karp 算法。下面的 Python 3 程序接受以 (起点,终点) 为键、非负整数容量为值的字典；平行边应先汇总。它返回最大流值与源点侧的最小割节点集，不改写输入。整数容量使每一步都能精确核对；边数为 E、节点数为 V 时，时间复杂度为 O(VE2)，剩余图空间为 O(V+E)。

Python 3
from collections import defaultdict, deque

def max_flow_min_cut(capacity, source, sink):
    if source == sink:
        raise ValueError("source and sink must differ")
    residual = defaultdict(dict)
    for (u, v), amount in capacity.items():
        if amount < 0 or u == v:
            raise ValueError("capacities must be nonnegative; no self-loops")
        residual[u][v] = residual[u].get(v, 0) + amount
        residual[v].setdefault(u, 0)
    residual.setdefault(source, {})
    residual.setdefault(sink, {})
    value = 0
    while True:
        parent = {source: None}
        queue = deque([source])
        while queue and sink not in parent:
            u = queue.popleft()
            for v, available in residual[u].items():
                if available > 0 and v not in parent:
                    parent[v] = u
                    queue.append(v)
        if sink not in parent:
            break
        delta = float("inf")
        v = sink
        while v != source:
            u = parent[v]
            delta = min(delta, residual[u][v])
            v = u
        v = sink
        while v != source:
            u = parent[v]
            residual[u][v] -= delta
            residual[v][u] = residual[v].get(u, 0) + delta
            v = u
        value += delta
    reachable = {source}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v, available in residual[u].items():
            if available > 0 and v not in reachable:
                reachable.add(v)
                queue.append(v)
    return value, reachable

edges = {("s", "a"): 3, ("s", "b"): 2,
         ("a", "b"): 1, ("a", "t"): 2, ("b", "t"): 3}
print(max_flow_min_cut(edges, "s", "t"))  # (5, {'s'})

浏览器展示与复制的代码中，比较符号是普通的小于号、大于号和不等号。运行结果的集合打印顺序可能不同。本例可再独立求割容量 c({s},{a,b,t})=3+2=5，与返回的流值相同。

模型适用的边界

最大流回答的是单一物资、固定容量下的最大吞吐。若每条边还收费用，目标变成最小费用流；若人员或车辆不可拆分，或者同一辆车必须按顺序访问多个地点，就要在整数规划或路径模型中表达这些限制，不能把“每小时可送五箱”当作五辆车的合法路线。若道路容量随时间或拥堵状态变化，也不能把逐时最大流简单相加；须增加时间层或采用动态模型。若多个物资共享边容量，还会出现多商品流，单商品最大流最小割定理并不直接给出总最优值。

参考资料与相关词条

检索自“https://gezhi.wiki/index.php?title=网络流与最大流最小割&oldid=2724”