[科普中国]-单向连通图

定义

在有向图中，即使存在从结点 到 的通路，却未必存在从 到 的通路，即顶点之间的可达关系没有对称性。因此，有向图的连通性分为强连通、单向连通和弱连通3种。

定义1设D是一个有向图，如果D中任意两个结点都彼此可达，则称D为强连通图。如果D中任意两点 之间，有 到 可达或 到 可达（称为单向可达），则称D为单向连通图。如果有向图的底图是无向连通图，则称D为弱连通图。

**注意：**强连通图必是单向连通图，单向连通图必是弱连通图。但反之未必。

例1 图1(a)是强连通图，图1(b)是单向连通图，图1(c)是弱连通图，图1(d)不是弱连通图。2

定义2设是有向图，G的极大的单向连通子图称为G的单向连通分****支(unilateral connected component)。

由定义知，如图2所示有两个单向连通分支，分别是G[1，2，3，4，5]，G[5，6]。

**注意：**有向图G的节点可以位于G的不同的单向连通分支中。

单向连通图的判定关于单向连通图的判定，有如下定理。

设 是有向图，则 单向连通当且仅当 中存在一条路，它通过所有节点。1

证法一： ( )若能证明命题“对于任意 均存在一个W中节点在G中到W中其余节点都有路”，则定理结论成立，因为先取W=V，存在 到其余V中节点有路，再取 ，存在 到其余 节点有路．这样一直下去，就可以得到一条从 到 ， 到 ， 到 的一条路，其中 (但这条路不一定是轨迹)。

假定上述命题不成立，令 是使其不成立的元素个数最少的，这时k≥3，根据假设 使命题成立，于是必存在 中一个节点，不妨设为 到其余节点 有路，而假设 到 是没有路的，否则与W的假设矛盾。另一方面，由于 到其余节点 有路，所以 到 没有路，否则 到 都有路，由于 到 没有路，而 到 也没有路，与已知G是单向连通图矛盾。

( )显然。

**证法二：**充分性：若G中有一回路，它至少经过每个顶点一次。则图中任何两个顶点都是相互可达的，可见图G是强连通图。

必要性：若有向图G是强连通的，则图中任何两个顶点都是相互可达的，故可作出一回路它经过图中的所有顶点。否则，必有一回路不通过某个顶点v，因此v与回路上的个结点均互不可达，这与G是强连通图矛盾。3

例2 判断图3中两有向图的连通性。

**解：**图3(a)中存在着经过所有点的回路，故图3(a)是强连通图，图3(b)没有a到其他顶点的通路，故图3(b)是单向连通图。