第 6 讲 · 连通与强连通分支

连通性问的是：边能否把一个顶点带到另一个顶点。课件区分通路、简单通路和基本通路：一般通路允许重复；简单通路不重复边；基本通路不重复顶点。最短通路一定可以去掉重复段，因此必是基本通路。

可达性具有传递性

若 $u$ 能到达 $v$，$v$ 能到达 $w$，拼接两段通路即可得到 $u$ 到 $w$ 的通路。顶点距离定义为最短通路长度，并满足三角不等式：

$$d(u,w)\leq d(u,v)+d(v,w).$$

有向图中 $d(u,v)$ 与 $d(v,u)$ 不一定相等，不可达时把距离视为无穷。

有向图有三种连通强度

• 强连通：任意 $u,v$ 都能互相到达；
• 单向连通：任意 $u,v$ 至少有一个方向可达；
• 弱连通：忽略方向得到的底图连通。

强连通蕴含单向连通，单向连通蕴含弱连通，反向一般不成立。课件还给出对应表述：强连通图存在经过所有顶点的完备回路；单向连通图存在完备通路；弱连通图存在完备半通路。

无向图按连通分支拆开

无向图的极大连通导出子图称为连通分支。删去顶点 $v$ 后若连通分支数增加，$v$ 是割点。团则是导出子图为完全图的顶点集合，表达一组两两相邻的顶点。

“极大”表示不能再加入相邻顶点而仍保持该性质，不等于顶点数在所有候选中最大。

强连通分支来自一个等价关系

在有向图中定义 $u\sim v$ 当且仅当二者互相可达。它满足自反、对称和传递，因此把顶点集划分成等价类；每个等价类的导出子图就是一个强连通分支（SCC）。每个顶点属于且只属于一个 SCC。

把每个 SCC 压缩成一个顶点，分支之间保留有向边，得到的压缩图一定是 DAG。若压缩图仍有有向圈，圈上各分支可以互相到达，本来就应属于同一个 SCC，产生矛盾。

顶点基要从所有源分支取点

顶点基是一组起点，使图中任意顶点都能由其中某点到达。DAG 的唯一最小顶点基由所有入度为 0 的顶点组成；一般有向图先压缩 SCC，再从压缩图每个入度为 0 的分支中任取一个顶点。

算法上可以用双 DFS、Tarjan 等方法求 SCC。真正需要记住的结构是“互相可达形成等价类，压缩后变成 DAG”，算法只是高效实现这件事。