最小割问题：
最小割问题可以转化为最大流量问题。
假设有一个无向图G=(V,E),其中假设每条边e的权重都是非负整数（可以是有向的），权重表示为w_e。现在要求从S到T的最小割，其中S和T表示图中两个顶点，S称为源节点，T称为汇节点。最小割所表示的是将图G进行分割，让S存在于一个分割A中，T存在于一个分割B中的最小的权重和。另外，这种分割意味着我们将原图中的边分成两个集合E_A和E_B，其中E_A表示连接A中的节点的边，E_B表示连接B中的节点的边。例如，假设我们想要把“pidancode.com”分割成两个部分，得到最小的分割，即从源节点S连接“pidan”，T连接“code.com”，将E_A和E_B分别表示为连接A和B中的节点的边。下面是一个例子：

在这个图中，S是4，T是5。可以看到，当我们删除边(1,3)时，我们就会把图分成两部分[1,2,3]和[4,5]。另一方面，如果我们删除边(2,5)，那么我们就会得到边[1,2,3,5]和[4]。上面两个分割的权重分别为3和6。我们要找到能够让最小割最小的那条边，拥有最小割的边称为割。
那么，如何在网络流图中解决最小割问题呢？这里我们使用Ford-Fulkerson算法求解最大流量。
Ford-Fulkerson算法：
Ford-Fulkerson算法提供一种通用的方法，可以找到网络流图G（V，E）的最大流量。在这个算法中，我们从初始流出发，不断增加边的流量，直到达到最终流的最大值，也就是没有更多流能够通过图的情况为止。具体来说，这个算法会重复执行以下步骤：
1. 选定一条从源节点S到汇节点T的路径。
2. 然后增加路径上的边的流量。
3. 重复步骤1，直到不存在从源节点到汇节点的路径。
为了清楚起见，以下是一些示例代码（使用networkx模块）来实现Ford-Fulkerson算法：
import networkx as nx
def max_flow_ford_fulkerson(G, source, sink):

首先，我们建立一个副本图并将其初始化为原始图。这个副本图可以被修改，并且我们将用它来存储当前的流情况。

Gf = G.copy()

其次，我们初始化一个字典来存储每个边的流量。

flow = {}
for u, v in G.edges():
flow[u, v] = 0

我们使用一个while循环，不断寻找从源节点到汇节点的路径。由于目前没有流量，我们可以使用深度优先搜索来探索整个图。

while True:

让我们找到一条从源节点到汇节点的路径，并记录路径中的最小权重。

path, min_capacity = dfs(Gf, source, sink, [])
if not path:
break

这里，我们增加路径上每个边的流量，并减去相反的反向边上的流量。

for u, v in path:
flow[u, v] += min_capacity
flow[v, u] -= min_capacity

找到一条路径后，我们需要继续在剩余网络图上寻找新的路径。因此，我们需要更新剩余的网络图。

Gf = residual_graph(G, flow)

在剩余的网络图上搜索路径并返回它

def dfs(G, current, sink, visited):
visited.append(current)
if current == sink:
return visited, get_min_capacity(G, visited)
for neighbor in G[current]:
if neighbor not in visited and G[current][neighbor]['capacity'] > 0:
path, min_capacity = dfs(G, neighbor, sink, visited)
if path:
return path, min_capacity
return None, 0

更新剩余网络图

def residual_graph(G, flow):
Gf = G.copy()
for u, v in Gf.edges():
capacity = G[u][v]['capacity']
flow_uv = flow.get((u,v), 0)
flow_vu = flow.get((v,u), 0)
new_capacity = capacity - flow_uv + flow_vu

更新边的权重

边的容量减去流量

将相反的反向边的流量添加到熟悉的边缘上

Gf[u][v]['capacity'] = new_capacity
Gf[v][u]['capacity'] = flow_uv
return Gf

计算路径中的最小容量

def get_min_capacity(G, path):
min_capacity = float('inf')
for i in range(len(path)-1):
u, v = path[i], path[i+1]
capacity = G[u][v]['capacity']
if capacity < min_capacity:
min_capacity = capacity
return min_capacity
现在我们可以使用Ford-Fulkerson算法解决最小割问题。下面给出示例代码（仍然使用networkx模块）：
import networkx as nx
def main():
G = nx.DiGraph()
G.add_edges_from([(1,2,{'capacity':3}),(1,3,{'capacity':2}),(2,3,{'capacity':1}),(2,4,{'capacity':3}),(3,4,{'capacity':1}),(4,5,{'capacity':2})])
source, sink = 1, 5
max_flow = max_flow_ford_fulkerson(G, source, sink)
print('Maximum flow:', max_flow)
if name == 'main':
main()
在上面的示例中，我们建立了一个有向图（使用DiGraph()）并将边缘的容量设置为每个边缘的权重。我们然后调用中提供的主函数，并将它们传递到max_flow_ford_fulkerson()函数中作为参数。最后，Ford-Fulkerson算法将返回从源节点到汇节点的最大流量。
在这里，我们计算的是最大流量。要找到最小割，我们需要将残余网络图中的所有容量为零的边的权重相加。这是因为最小割与最大流量同步，因此选择一种方法来计算最小割并不奇怪。
效果如下：