网络流问题

网络流问题（Network Flow Problems）是图论中一类重要的优化问题，研究如何在网络中高效分配流量。它在运输、通信、资源分配等领域有广泛应用。本章将介绍基本概念、经典算法（如Ford-Fulkerson方法、Edmonds-Karp算法）以及实际案例。

基本概念

定义

网络流问题通常建模为有向图 $G=(V,E)$，其中：

• $V$ 是节点集合（如仓库、路由器）。
• $E$ 是边集合，每条边 $(u,v)\in E$ 有容量 $c(u,v)\ge 0$。
• 存在唯一的源点（source）$s$ 和汇点（sink）$t$。

目标是找到从 $s$ 到 $t$ 的最大流（maximum flow），即在不违反边容量限制的情况下，最大化从源点到汇点的总流量。

流量性质

合法流 $f:E\to {\mathbb{ℝ}}^{+}$ 需满足： 1. 容量限制：$0\le f(u,v)\le c(u,v)$。 2. 流量守恒：对任意非源汇节点 $u$，流入等于流出，即 $\sum _{v\in V}f(v,u)=\sum _{v\in V}f(u,v)$。

经典算法

Ford-Fulkerson 方法

通过不断寻找增广路径（augmenting path）来增加流量，直到无法继续。

伪代码

  
def ford_fulkerson(G, s, t):  
    max_flow = 0  
    residual_graph = initialize_residual_graph(G)  
    while exists_augmenting_path(residual_graph, s, t):  
        path = find_augmenting_path(residual_graph, s, t)  
        min_capacity = min_capacity_on_path(path)  
        max_flow += min_capacity  
        update_residual_graph(residual_graph, path, min_capacity)  
    return max_flow

Edmonds-Karp 算法

Ford-Fulkerson 的改进版，使用 BFS 寻找最短增广路径，时间复杂度为 $O(V{E}^2)$。

示例

以下是一个网络流图及其最大流计算过程：

graph LR s -->|4/4| v1 s -->|2/2| v2 v1 -->|3/3| v3 v1 -->|1/1| v4 v2 -->|2/2| v4 v3 -->|3/3| t v4 -->|3/3| t

• 边上的标记表示流量/容量。
• 最大流值为 5（4从s→v1→v3→t，1从s→v1→v4→t）。

实际应用

交通网络

城市道路系统中，每条道路的容量代表最大车流量，网络流算法可优化交通分配。

计算机网络

路由器之间的带宽分配问题可建模为网络流，最大化数据传输效率。

代码实现

以下是 Edmonds-Karp 算法的 Python 实现：

  
from collections import deque  

def edmonds_karp(graph, source, sink):  
    n = len(graph)  
    residual = [[0] * n for _ in range(n)]  
    for u in range(n):  
        for v, cap in graph[u]:  
            residual[u][v] = cap  

    parent = [-1] * n  
    max_flow = 0  

    while True:  
        queue = deque([source])  
        parent = [-1] * n  
        parent[source] = source  
        found_path = False  

        while queue and not found_path:  
            u = queue.popleft()  
            for v in range(n):  
                if residual[u][v] > 0 and parent[v] == -1:  
                    parent[v] = u  
                    if v == sink:  
                        found_path = True  
                        break  
                    queue.append(v)  

        if not found_path:  
            break  

        path_flow = float('inf')  
        v = sink  
        while v != source:  
            u = parent[v]  
            path_flow = min(path_flow, residual[u][v])  
            v = u  

        v = sink  
        while v != source:  
            u = parent[v]  
            residual[u][v] -= path_flow  
            residual[v][u] += path_flow  
            v = u  

        max_flow += path_flow  

    return max_flow  

# 示例输入：邻接表表示图，边格式为 (目标节点, 容量)  
graph = [  
    [(1, 4), (2, 2)],  # s (0)  
    [(3, 3), (4, 1)],   # v1 (1)  
    [(4, 2)],           # v2 (2)  
    [(5, 3)],           # v3 (3)  
    [(5, 3)],           # v4 (4)  
    []                  # t (5)  
]  
print("最大流:", edmonds_karp(graph, 0, 5))  # 输出: 5

扩展阅读

• 最小割问题：最大流的值等于最小割的容量（Max-Flow Min-Cut Theorem）。
• 多源多汇问题：通过超级源点和超级汇点转换为单源单汇问题。

网络流问题是算法竞赛和实际工程中的核心课题，掌握其原理和实现能显著提升解决复杂问题的能力。