最小割：切断补给的最低代价
最小割：切断补给的最低代价
要瘫痪一支军队的补给，是该漫无目的地多炸几处，还是找准一处下刀、以最低代价让全网断流？这正是本节的问题：在容量网络里找一个割——把顶点切成"含源的一侧"与"含汇的一侧"，割掉所有横跨两侧的边——使被割边的容量总和最小。上一节末尾埋下的伏笔在此揭晓：最小割的容量恰好等于最大流的流值。这条最大流最小割定理是组合优化的定海神针，本节完成它的证明拼图，再演示这枚定理如何变身为连通度诊断、图像分割与瓶颈分析的多面手。
割的形式化与弱对偶
先把对象定义干净。一个割是顶点集的一个划分（S, T），源在 S、汇在 T；割的容量是所有从 S 指向 T 的边的容量之和（注意方向：只算顺流的，T 指回 S 的边不计）。形象的比喻：割是一圈"工事线"，工事只拦顺着我方意图流动的物资；敌军沿反方向溜走的流量不在拦截目标内。
任何割与任何流之间都隔着一道天然屏障，值得先证这条弱对偶：任意流的流值，不超过任意割的容量。论证只需会计常识：流值等于"从 S 净流出到 T 的总量"，它由两部分构成——横跨割的正向流（被容量上界压着，最多等于割容量）与逆跨的回流（非负，只会减损净输出）。于是流值 ≤ 正向流量 ≤ 割容量。一句话消化：任何一道工事都给运力上了顶；最大流再大，也大不过最浅的工事。
弱对偶立刻给出一个实用的上界工具：估出任何一个割，就拿到了最大流的 pessimistic 上限。工程设计里快速判断"瓶颈大致在哪"，往往先手算两三个显然的割。
强对偶：定理的证明拼图
弱对偶说的是"任意流 ≤ 任意割"；定理的完整版更进一步："最大流 = 最小割"。拼图只缺一块：存在某个流与某个割，恰好把不等号同时取到等号。
补上这块拼图的正是上一节算法的终点。当残余网络里源到汇不再连通时，令 S 为"源在残余网络中可达的顶点集"、T 为其余。三个观察连环：其一，横跨 S 到 T 的每条原边都已被榨干（否则残余网络里 S 还能扩张，与 S 的极大性矛盾）；其二，从 T 指回 S 的每条边流量必为零（否则它的反向边提供残余容量，同样会扩张 S）；其三，于是当前流值 = 正向饱和流之和 − 零回流 = 割 (S, T) 的容量。把这个割摆到弱对偶里：流值顶到了这道割的天花板，两侧同时取等——它既是最小割，当前流也必是最大流。证毕，顺带白送一条判定准则：最大流的流值唯一，而达到它的流与割都可能不唯一。
import networkx as nx def min_cut_edges(G, s, t): """跑最大流后，从残余网络可达集读出最小割""" R = nx.algorithms.flow.build_residual_network(G, "capacity") # 复用上一节的增广循环（此处调用官方实现灌满残网） nx.algorithms.flow.edmonds_karp(G, s, t, residual=R) # 残余网络中从 s 可达的顶点集 = 割的源侧 reachable, q = {s}, [s] while q: u = q.pop() for v, attr in R[u].items(): if v not in reachable and attr["capacity"] - attr["flow"] > 1e-9: reachable.add(v) q.append(v) cut = [(u, v) for u, v in G.edges if u in reachable and v not in reachable] value = sum(G[u][v]["capacity"] for u, v in cut) return reachable, cut, value supply = nx.DiGraph() supply.add_edge("基地", "中转A", capacity=3) supply.add_edge("基地", "中转B", capacity=2) supply.add_edge("中转A", "前哨", capacity=2) supply.add_edge("中转B", "前哨", capacity=3) supply.add_edge("中转A", "中转B", capacity=2) side, cut, cap = min_cut_edges(supply, "基地", "前哨") print("源侧据点:", side) print("被切断的桥:", cut) print("割容量:", cap) print("最大流对照:", nx.maximum_flow_value(supply, "基地", "前哨"))
输出的割容量与最大流值分毫不差——定理在机器上的显形。值得玩味的是：最小割自动"避开了"贵的那一刀，它专挑"容量细脖子"下手；工程上把这组边称为瓶颈边集，它们是扩容改造时性价比最高的目标。
这枚定理还能干什么
连通度诊断。问"网络至少要坏几个节点才断开"（点连通度）：把每个顶点拆成一进一出的内部边（容量为一），跑最大流，流值即答案；边连通度则直接给原边单位容量。通信网、电网的抗毁性评估走的就是这条路。
图像分割。像素为顶点、相邻像素的相似度为边容量，再添"源=前景、汇=背景"各连到端点。最小割切开的边恰是"相似度最低的接缝"——接缝两侧天然分成前景与背景。这个思路是计算机视觉里能量优化分割（如抓取切割交互）的数学心脏。
项目瓶颈分析。把流水线画成容量网（工序容量=产能），最大流给出整线产出上限，最小割点出拖住全线的工序群——扩产预算该砸给谁，答案在割上而不在直觉上。
联盟稳定性判定。合作博弈论里要判断一组联盟能否被外部报价瓦解，可转写为流可行性问题，最小割给出"最便宜瓦解方案"。棒球淘汰判定（上一节的例子）的证明灵魂同样是这条定理。
def edge_connectivity_probe(G, u, v): """两顶点间的边连通度：单位容量最大流""" H = nx.DiGraph() for a, b in G.edges(): H.add_edge(a, b, capacity=1) # 无向边拆成两条单位容量有向边 H.add_edge(b, a, capacity=1) return nx.maximum_flow_value(H, u, v) field_net = nx.Graph([("指挥所","电台"),("电台","哨站一"),("电台","哨站二"), ("哨站一","粮站"),("哨站二","粮站"),("粮站","前线")]) print("指挥所-前线 需炸断的边数:", edge_connectivity_probe(field_net, "指挥所", "前线"))
读数即答案：要让前线与指挥所彻底失联，敌军至少要切断那么多的链路。防御方的对策反过来做——给割上的边加冗余。
复杂度与实务细节
最小割本身不需要独立算法：任何最大流算法跑完，从源出发在残余网络里做一次可达性遍历，割就浮出水面——代价被最大流完全吸收。实务里有两条经验值得记牢。其一，最小割不唯一：并列的最小割可能有好几刀，若业务要"最难切断的那个瓶颈"（比如防守方想找最稳的切法），需在并列解里按次级准则挑选；图论里还专门研究了"所有最小割的结构"（其数量被顶点数的平方量级封顶，且构成一种漂亮的格结构）。其二，只关心 s-t 割，别与无向图的全局最小割混淆——全局版有专门的更快算法（如随机收缩法，靠掷硬币反复收缩边直到剩两点，简洁得像魔术），那是另一条技术路线。
⚠️ 常见坑：把"割容量"算成两侧之间全部边（含从 T 指回 S 的）。方向反了的边不计入容量——它拦不住从源到汇的顺流；多算会让割虚胖，最小割判断随之失真。
💡 关键直觉：最大流是"送多少"，最小割是"卡在哪"——对偶定理说这两个问题的答案天然相等。学会在两个对偶视角间自由切换，是组合优化的内功；遇到"上限"问题先想流，遇到"瓶颈"问题先想割。
补给线的攻防两面都已讲透。战役的最后一块阵地是一一配对：任务与兵力怎么对位，才能既不冲突又最满员？下一节的二分图匹配给出答案。