图的连通性的判定算法研究

张从文 苏州百年职业学院

1 引言

随着计算机科学技术在现代生活中的应用越来越广泛，作为计算机科学基础的离散数学也慢慢被大家所重视。图论是离散数学的一个重要组成部分，起源于数学游戏的研究，如迷宫、哈密尔顿环球旅行等问题，现在运筹学、网络技术、控制论等多个领域有着很重要的应用。连通图是图论中的一个重要的基本概念，在图的应用中使用广泛，从而使连通图在图论中占据着举足轻重的位置。所以就如何判定图特别是简单图连通性的问题就成为我们非常重视和关注的焦点，目前有许多关于这方面的研究。通常我们都是用图连通性的定义来研究该问题，但实际上这种用定义判别的方法适用范围太窄，对结构简单、结点数较少的图来说比较好，而对结点数目和边数较多的复杂点的图来说，使用起来就不是很方便，而且不利于我们借助计算机程序来解决这一问题。本文作者借助矩阵，用矩阵学的理论来研究图的连通性问题，便于形成算法，从而可以推广到结点数目庞大的复杂的图的研究中去。

2 基本概念

定义2.2 若有关系R={＜u,v＞│u,v∈V且u,v 之间存在通路}，且R 满足自反性、对称性和传递性，则R 是V上的等价关系。设R将V 分成的等价类为则称无向图G=＜V,E＞的子图是G 的连通分支。

定理2.3 无向图是连通的充分必要条件是此无向图只有一个连通分支。

定义2.4 对有向图G=＜V,E＞，如果略去G 中各边的方向所得到的无向图G 是连通图，则称有向图G=＜V,E＞是弱连通图。如果有向图G 的任意两个不同结点至少有一个可达另一个，则称G 是单向连通图。如果G 的任意两个不同结点都是互相可达的，则称G 是强连通图。

定理2.5 对有向图G=＜V,E＞，若存在经过每个结点至少一次的有向通路，则G 是单向连通图，若存在经过每个结点至少一次的有向回路，则G 是强连通图。

例1 判断下面图的连通性。

解：根据定理2.5，我们可以很容易的判定图（1）是强连通图，图（2）是单向连通图，图（3）是单向连通图，图（4）是无向图的非连通图。对于像例1 这样的四个结点的图的连通性的判定，我们可以直接利用定理2.5看是否形成经过每个结点至少一次的有向回路或者通路确定，但如果结点过多，利用定理2.5 就有点困难，所以对于结点多的图，我们考虑利用邻接矩阵、可达矩阵的代数学知识辅助解决。

3 图连通性的矩阵判别法

定义3.1 设G=＜V,E＞是简单图，其中V 是点集，且|V|=n, E是边集，n 阶方阵称为此简单图的邻接矩阵，

定理3.3 对简单图G=＜V,E＞，其可达性矩阵P=A+A2+...+An,此处“+”是指布尔和。

定理3.4 对于简单图G=＜V,E＞，邻接矩阵是A，可达性矩阵是P，有：

图G=＜V,E＞是强连通图的充要条件是可达矩阵P 除对角线元素外所有元素都为1。

图G=＜V,E＞是单向连通图的充要条件是矩阵P+PT除对角线元素外所有元素都为1。

图G=＜V,E＞是弱连通图的充要条件是以矩阵A+AT=作为邻接矩阵所得到的可达矩阵除对角线元素外所有元素都为1。

对应这个邻接矩阵，计算A2，A3，A4如下：

4 图连通性判别法的计算机实现程序

本 文将图论中的邻接矩阵看成是二元关系的关系矩阵，改进了著名的传递闭包的Warshall 算法来计算可达矩阵，并据此来判断有向图的连通性。对于稍微复杂的有向图的连通性的判定问题，利用例2 的方法去求解判定，计算量会很大，因此，本文给出了例2 有向图连通性的判别法的python 语言程序如下：

from numpy import *

a=mat([[0,1,0,0],[0,0,0,0],[0,1,0,0],[1,0,1,0]])

c=mat([[0,1,0,0],[0,0,0,0],[0,1,0,0],[1,0,1,0]])

for i in range(4)：

for j in range(4)：

if j==i：

continue

elif a[j,i]==1：

for k in range(4)：

a[j,k]=a[j,k]or a[i,k]

f=0

for i in range(4)：

for j in range(4)：

if j==i：

continue

elif a[j,i]==1：

f=f+1

if f＞=(4*4-4)：

print("可达矩阵")

print(a)

print("此图为强联通图")

else：

b=a.T

for i in range(4)：

for j in range(4)：

a[j,i]=a[j,i]or b[j,i]

f=0

for i in range(4)：

for j in range(4)：

if j==i：

continue

elif a[j,i]==1：

f=f+1

if f＞=(4*4-4)：

print("可达矩阵与其转置矩阵布尔和矩阵")

print(a)

print("此图为单向联通图")

else：

c=c+c.T

for i in range(4)：

for j in range(4)：

if j==i：

continue

elif c[j,i]==1：

for k in range(4)：

c[j,k]=c[j,k]or c[i,k]

f=0

for i in range(4)：

for j in range(4)：

if j==i：

continue

elif c[j,i]==1：

f=f+1

if f＞=(4*4-4)：

print("无向图的可达矩阵")

print(c)

print("此图是弱连通图")

else：

print("此图不是连通图")

在python3.7.3 shell 里执行后显示结果显示如下：

5 结语

本文主要基于邻接矩阵，改进了Warshall 算法，并利用改进的warshall 算法，基于python 语言平台，给出了判断有向简单图和无向简单图的连通性的判别算法，从而大大简化了图的判定过程，提高了准确性和效率。