构建无向图最小割：掌握图论最优划分的奥秘

# 1. 无向图最小割概述

无向图最小割问题在图论中是一个重要的概念，它旨在找到将图划分为两个子集的最小边权和割集。最小割在许多实际应用中有着广泛的应用，例如图像分割、社区检测和网络流优化。

在无向图中，最小割可以定义为将图的顶点划分为两个不相交的子集 S 和 T，使得 S 和 T 之间的边权和最小。最小割问题可以通过各种算法来求解，包括福特-富尔克森算法和 Edmonds-Karp 算法。

# 2. 最小割算法理论基础

### 2.1 图论基础知识

#### 2.1.1 图的定义和基本概念

**图**是由顶点和边组成的结构。顶点表示实体，边表示实体之间的关系。一个图用 G = (V, E) 表示，其中 V 是顶点集，E 是边集。

**有向图**：边具有方向，称为弧。
**无向图**：边没有方向。
**权重图**：边具有权重，表示边上关联的数值。
**连通图**：任意两个顶点之间都存在路径。
**连通分量**：图中最大连通子图。

#### 2.1.2 图的表示方法

**邻接矩阵**：一个 n×n 的矩阵，其中 n 是顶点数。矩阵元素表示顶点之间的边权重。

adj_matrix = [
    [0, 1, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [0, 0, 1, 0],
]

**邻接表**：一个列表，其中每个元素是一个字典，键是相邻顶点，值是边权重。

adj_list = [
    {1: 1},
    {0: 1, 2: 1},
    {1: 1, 3: 1},
    {2: 1},
]

### 2.2 最小割问题的定义和性质

#### 2.2.1 最小割的定义

**最小割**：将图 G 分成两个不相交的子图 S 和 T，使得 S 和 T 之间的边权重和最小。

#### 2.2.2 最小割的性质

* **最小割定理**：最小割等于图中最大流。
* **最小割性质**：
* 最小割中，S 和 T 之间的边权重都为 0。
* 最小割中，S 和 T 之外的边权重都为正。

# 3.1 福特-富尔克森算法

#### 3.1.1 算法原理

福特-富尔克森算法是一种经典的最小割算法，它基于贪心策略，通过不断寻找增广路径，逐步增大网络流，最终达到最大流。

算法的具体原理如下：

1. **初始化：**设置源点和汇点的初始流量为 0，其他边的流量为无穷大。
2. **寻找增广路径：**从源点出发，使用深度优先搜索或广度优先搜索算法寻找一条从源点到汇点的增广路径。增广路径是指一条流量小于其容量的路径。
3. **增大流量：**如果找到增广路径，则沿该路径增大所有边的流量。增大流量的量等于增广路径上流量最小的边。
4. **重复步骤 2 和 3：**继续寻找增广路径并增大流量，直到无法再找到增广路径为止。

#### 3.1.2 算法实现

def ford_fulkerson(graph, source, sink):
    """