编辑“︁网络流问题”︁

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

== 基本概念 ==  
=== 定义 ===  
网络流问题通常建模为'''有向图''' <math>G = (V, E)</math>，其中：  
* <math>V</math> 是节点集合（如仓库、路由器）。  
* <math>E</math> 是边集合，每条边 <math>(u, v) \in E</math> 有容量 <math>c(u, v) \geq 0</math>。  
* 存在唯一的'''源点'''（source）<math>s</math> 和'''汇点'''（sink）<math>t</math>。  

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

=== 流量性质 ===  
合法流 <math>f: E \to \mathbb{R}^+</math> 需满足：  
1. '''容量限制'''：<math>0 \leq f(u, v) \leq c(u, v)</math>。  
2. '''流量守恒'''：对任意非源汇节点 <math>u</math>，流入等于流出，即 <math>\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)</math>。  

== 经典算法 ==  
=== Ford-Fulkerson 方法 ===  
通过不断寻找'''增广路径'''（augmenting path）来增加流量，直到无法继续。  

==== 伪代码 ====  
<syntaxhighlight lang="python">  
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  
</syntaxhighlight>  

=== Edmonds-Karp 算法 ===  
Ford-Fulkerson 的改进版，使用 BFS 寻找最短增广路径，时间复杂度为 <math>O(VE^2)</math>。  

==== 示例 ====  
以下是一个网络流图及其最大流计算过程：  
<mermaid>  
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  
</mermaid>  
* 边上的标记表示流量/容量。  
* 最大流值为 5（4从s→v1→v3→t，1从s→v1→v4→t）。  

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

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

== 代码实现 ==  
以下是 Edmonds-Karp 算法的 Python 实现：  
<syntaxhighlight lang="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  
</syntaxhighlight>  

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

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]