图进阶：连通性、二分图与网络流入门

一句话定义

在 BFS/DFS 骨架之上，图论进阶解决三类结构问题：用 DFS 时间戳与 low-link 求无向图割点/桥与有向图强连通分量（SCC）；用染色法判定二分图并引出匹配问题；用「增广路径 + 残量网络」求最大流，并以最大流最小割定理收束。

为什么重要

这三块是从「会遍历图」到「会用图建模」的跃迁：社交圈分析（SCC）、关键基础设施识别（割点/桥）、任务与人配对（二分图匹配）、带宽与运输优化（最大流）都是真实系统问题。掌握 low-link 思想还会反哺你对「DFS 一次性提取全部结构信息」的理解——同一棵 DFS 树能同时给出环、桥、SCC。

前置知识

kp-016（DFS 时间戳与括号定理）；kp-018（拓扑排序，用于 SCC 缩点后处理）。

核心概念

• 割点与桥：删除后使连通分量数增加的顶点/边；用子树 low 值判定：子节点 low ≥ in(u) 则 u 为割点，low > in(u) 则边 (u,v) 为桥。
• low-link：low(u) = min(in(u), 各父边之外的返祖边端点 in 值, 各孩子 low 值)。
• 强连通分量（SCC）：有向图中互相可达的极大点集；Tarjan 一次 DFS 用栈 + low 求出；Kosaraju 两次 DFS（原图 + 反图）。
• 缩点：SCC 压成一个点后得到 DAG，可再做拓扑排序/DP。
• 二分图：顶点可分两半、所有边跨半；判定 ⇔ 无奇环 ⇔ BFS/DFS 二染色成功。
• 匹配与匈牙利算法：二分图最大匹配用「交替路 + 增广」逐步扩大，O(V·E)。
• 最大流最小割：s-t 最大流值 = 最小割容量（Ford–Fulkerson 增广思想，Dinic 用层次图加速到 O(V²E)）。

原理与机制

low-link 的机制是「DFS 时给每个点记两样东西」：进入时间 in，以及「自己与子树能回溯到的最小 in」；子树若回不到祖先之上，当前边即桥、当前点即割点，有向图中 low == in 的点即 SCC 根并弹栈收分量。二分染色靠归纳：起点染红后每条边两端必异色，全部走完无冲突 ⇔ 无奇环。最大流靠「迭代改进」：在残量网络里反复找增广路推流，直到无路可增，此时流量恰被最小割封顶。

直观类比

low-link 像「登山时记住能回头望见的最矮路标」：如果 subtree 回不到你之前的高度，你脚下就是关口（割点/桥）。二分染色像「聚会分两队，认识的人必须不同队」，分不下去就是混进了奇数人环。最大流像水管网络：反复找一条还有余量的路送水，直到找不出为止——送出的总量恰好等于「最细瓶颈切面」的容量。

公式或模型

• 无向 DFS 桥判定：对树边 (u,v)（v 为孩子），若 low(v) > in(u)，则 (u,v) 是桥。
• Tarjan（有向）：low(u) = min(in(u), min low(子), min in(返祖可达点))；当 low(u) = in(u) 时 u 是一个 SCC 的根，弹栈收分量。
• König 定理：二分图最大匹配数 = 最小点覆盖数（用途：从匹配反推覆盖方案）。
• 最大流 = 最小割：任何流值 ≤ 任意割容量；残量网络无增广路时取等。

图示

二分染色（BFS）:
    A ─ B        A=红 → B=蓝, C=蓝
    |            D=红 ⇒ 合法二分图
    C ─ D
加一条 B─C 则 B,C 同为蓝却相邻 → 染色失败 ⇔ 存在奇环 A-B-C-A。

最大流（容量标边上）:  s ─3→ u ─2→ t
                      s ─2→ v ─2→ t   最大流 = 4 = 最小割容量

实例或案例

• 社交/网页分析：SCC 找「互相关注圈」，缩点后做传播分析。
• 关键节点排查：路由器、服务器集群找割点做冗余加固；桥边 = 单点故障链路。
• 任务分配：N 个任务 × M 个工人的二分图匹配（匈牙利算法）；广告与展位分配同型。
• 运输/物流：管道容量上限、服务器带宽调度用最大流；「项目选择闭合子图」是最大流的建模经典。

常见误区

• 混淆「连通分量」（无向）与「强连通分量」（有向互相可达）：名字近，语义差一级。
• 用「颜色不冲突」检查遗漏：二分图判定必须对每个连通分量都染色（森林图）。
• 把最大流的「找增广路」写成只找一遍：必须迭代到残量网络无路可增。
• low-link 数组忘了区分「父边」与「返祖边」（无向图处理父节点回边），导致桥/割点误判。

自测题

1. 描述用一次 BFS 判二分图的流程与失败条件。

答案要点：每连通分量任取起点染红，逐层染相反色；发现相邻同色即失败 ⇔ 存在奇环。

1. Tarjan 求 SCC 中，为什么用一个栈？什么时候弹栈？

答案要点：栈保存「尚未归属 SCC」的节点；low(u)=in(u) 时 u 是 SCC 根，把栈顶到 u 的全部节点弹出为一个 SCC。

1. 解释「最大流 = 最小割」的直观含义，并给出一个应用。

答案要点：流量被最细的瓶颈切面封顶；可用来求「最少删多少条边使 s、t 不连通」（边连通度）。

与其他知识点的关系

kp-016 的 DFS 时间戳是一切 low-link 的原材料；kp-030 并查集可判「删边连通性」的简化场景；kp-018 在 SCC 缩点后的 DAG 上继续工作；kp-027 的搜索思想与增广路径的「迭代改进」精神相通。

延伸阅读

Tarjan 1972 论文；《算法设计》第 3 章（图分解）与第 7 章（网络流）；CP-Algorithms 的 SCC 与二分图匹配条目作为实现参考。