有向图的单向连通与拟强连通性关系的探究

彭丽曼

摘 要：本文通过对有向图单向连通性与拟强连通性关系的探究，得出单向连通图D，如果单向连通图D中任意顶点ν，有向图D-ν不是单向连通的，则有向图D拟强连通的结论，进而证明了单向连通图D一定是拟强连通的。但是，存在拟强连通的有向图D不是单向连通的，从而探明有向图中单向连通性与拟强连通性之间的关系。本文最后讨论了几种可降阶单向连通图，以及可去点的性质。

关键词：有向图；单向连通；拟强连通

1 引言

本文所述定义及符号大部分出自[1]。

本文所论述的图都是有向图。所述道路、圈指的是有向道路、有向圈。用v的入度表示以顶点v为终点的弧的数目；用v的出度表示以顶点v为起点的弧的数目。并且，本文第三部分定义了可降阶单向连通图与可降阶单向连通图的可去点。

定义 如果在有向图D中，有一条有向道路，则v称为是从u可达的，或者说，从u可达v。

设D是一个有向图，r是D中一个顶点，如果由r可到达D的任一顶点，则称r为D的根。

如果有向图D的任何两顶点至少有一个顶点由另一顶点可达，则称D是单向连通的。

如果有向图D的每一对顶点u，v都存在一顶点w，使w可达u和v，则称D是拟强连通的。

定理* 有向图D有根当且仅当对D的每一对顶点u，v都存在一个顶点w，使w可达u和v。

2 有向图的单向连通和拟强连通性的关系

定理1 单向连通图D，如果D中任意顶点ν，D-ν不单向连通，则D拟强连通。

证明：任意有n个顶点的单向连通图D，取图D中一点ω1，由于D-ω1不单向连通，则存在图D-ω1中两个顶点μ1，ν1，对于μ1，ν1在图D-ω1中不存在从一个顶点到另一个顶点的有向道路。又由于图D单向连通，故对于上述μ1，ν1在图D中存在从一顶点到另一顶点的有向道路，不妨设μ1可达ν1，令P1=<μ1，ν1>，则P1一定过顶点ω1，从而μ1可达ω1，且ω1可达ν1。令ω2=μ1，则ω2可达ω1，且ω2可达ν1。又由于图D-ω2不单向连通，则存在图D-ω2中两个顶点μ2，ν2，对于μ2，ν2在图D-ω2中不存在从一个顶点到另一个顶点的有向道路。又由于图D单向连通，故对于上述μ2，ν2在图D中存在从一顶点到另一顶点的有向道路，不妨设μ2可达ν2，令P2=<μ2，ν2>，则P2一定过顶点ω2，从而μ2可ω2，且ω2可达ν2。令ω3=μ2，则ω3可达ω2，且ω2可达ν2。重复上述过程可穷尽图D的所有顶点，得：ωnl1可达ωnl2，，…ω1，ν1，从而ωnl1是D的根，由定理*与拟强连通的定义知，有向图D拟强连通。

定理2 单向连通图D拟强连通。

证明：对单向连通图D的顶点个数施加归纳。

（i）当n=2时，图D单向连通，显然图D拟强连通；

（ii）假设当n=k时，结论成立；

（iii）当n=k+1时，若不存在D中顶点r使得D-r单向连通，则由定理1得图D拟强连通；若存在D中顶点u，使得D-u单向连通，则由归纳假设，D-u拟强连通，由定理*与拟强连通的定义，D-u有根，设其根为v，若存在D-u中一个顶点w使得属于图D中的边，则w可达u，由ν可达w，从而v可达u，故v是图D的根；否则，任意D-u中的顶点w，不存在属于D-u的边，从而u的出度为0，则在D中，v不可达u，由于图D单向连通，从而u可达v，由此u可达D中任意顶点，故u是D中的根。综上所述，图D中有根，由定理*与拟强连通的定义知图D拟强连通。

定理3 拟强连通的有向图不一定是单向连通的。

定理是显然的，此处不给予证明。

3 可降阶单向连通图

定义 若单向连通图D可以通过去掉图中某一顶点ν使得图D-v保持单向连通性，则称图D为可降阶单向连通图，称顶点v为可去点。

在讨论可降阶单向连通图之前先给出有向圈与有向圈相连接的三种方式以及给出两个定理。

（a）有向圈与有向圈有公共边；

（b）有向圈与有向圈有一个公共点。

（c）有向圈与有向圈既无公共点又无公共边。

定理4 若有向连通图D的生成子图B是单向连通的，则图D是单向连通的。

证明：任意的有向连通图D中的顶点p，q，由于图D的生成子图B单向连通，从而在图B中有一条有向道路P连接p，q，由于道路P也是图D中的道路，从而道路P为图D中连接点p，q的有向道路，由于p，q的任意性，图D单向连通。

定理5 若有向连通图D每一个顶点的出度与入度都大于0，则图D存在由若干有向圈以（a）方式或（b）方式或（c）方式连接的生成子图。

证明：若有向连通图D的所有顶点的出度与入度都大于0，则从图D的任意顶点出发可得一有向链，从而存在有向圈C。若此时圈C为图D的生成子图，则定理得证，否则由于图D是连通的，必有圈C中一个顶点p与其他顶点之一相连，从p出发可得另一有向链，从而可得另一有向圈，重复上述过程，可得有向图D的生成子图B，图B为若干有向圈组成，其中任意两个有向圈由（a）方式或（b）方式或（c）方式连接。

以下讨论几种可降阶单向连通图以及可降阶单向连通图的可去点的性质。

（i）若单向连通图D中存在某个顶点ν，使得ν出度或者入度为0，则图D为可降阶单向连通图，且ν为可去点。

证明：在单向连通图D中存在顶点ν，使得v出度或者入度为0，则D- v任意两个顶点p，q，由于图D单向连通，所以有连接p，q的有向道路，且所有连接p，q的有向道路P均不经过顶点ν，否则v的出度与入度都大于0。从而道路P为图D- v的道路。所以图D-ν也單向连通，由可降阶的单向连通图定义知图D-v为可降阶的单向连通图，ν为图D的可去点。

（ii）若有向图D由两个有向圈以（a）或（b）方式连接，则D为可降阶单向连通图。

证明：若有向图D由两个有向圈以（a）方式连接，则去掉一个度为3的顶点得到一有向道路，有向道路为单向连通的，故图D为可降阶的单向连通图；若有向图由两个有向圈以（b）方式连接，则去掉任意度为2的顶点，得到的图均为单向连通图，从而图A为可降阶单向连通图。

参考文献

[1]王朝瑞，图论，北京理工大学出版社，2001。