圖的連通性的判定算法研究

張從文 蘇州百年職業學院

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 語言平臺，給出了判斷有向簡單圖和無向簡單圖的連通性的判別算法，從而大大簡化了圖的判定過程，提高了準確性和效率。