張從文 蘇州百年職業(yè)學(xué)院

1 引言

隨著計(jì)算機(jī)科學(xué)技術(shù)在現(xiàn)代生活中的應(yīng)用越來(lái)越廣泛，作為計(jì)算機(jī)科學(xué)基礎(chǔ)的離散數(shù)學(xué)也慢慢被大家所重視。圖論是離散數(shù)學(xué)的一個(gè)重要組成部分，起源于數(shù)學(xué)游戲的研究，如迷宮、哈密爾頓環(huán)球旅行等問(wèn)題，現(xiàn)在運(yùn)籌學(xué)、網(wǎng)絡(luò)技術(shù)、控制論等多個(gè)領(lǐng)域有著很重要的應(yīng)用。連通圖是圖論中的一個(gè)重要的基本概念，在圖的應(yīng)用中使用廣泛，從而使連通圖在圖論中占據(jù)著舉足輕重的位置。所以就如何判定圖特別是簡(jiǎn)單圖連通性的問(wèn)題就成為我們非常重視和關(guān)注的焦點(diǎn)，目前有許多關(guān)于這方面的研究。通常我們都是用圖連通性的定義來(lái)研究該問(wèn)題，但實(shí)際上這種用定義判別的方法適用范圍太窄，對(duì)結(jié)構(gòu)簡(jiǎn)單、結(jié)點(diǎn)數(shù)較少的圖來(lái)說(shuō)比較好，而對(duì)結(jié)點(diǎn)數(shù)目和邊數(shù)較多的復(fù)雜點(diǎn)的圖來(lái)說(shuō)，使用起來(lái)就不是很方便，而且不利于我們借助計(jì)算機(jī)程序來(lái)解決這一問(wèn)題。本文作者借助矩陣，用矩陣學(xué)的理論來(lái)研究圖的連通性問(wèn)題，便于形成算法，從而可以推廣到結(jié)點(diǎn)數(shù)目龐大的復(fù)雜的圖的研究中去。

2 基本概念

定義2.2 若有關(guān)系R={＜u,v＞│u,v∈V且u,v 之間存在通路}，且R 滿足自反性、對(duì)稱性和傳遞性，則R 是V上的等價(jià)關(guān)系。設(shè)R將V 分成的等價(jià)類為則稱無(wú)向圖G=＜V,E＞的子圖是G 的連通分支。

定理2.3 無(wú)向圖是連通的充分必要條件是此無(wú)向圖只有一個(gè)連通分支。

定義2.4 對(duì)有向圖G=＜V,E＞，如果略去G 中各邊的方向所得到的無(wú)向圖G 是連通圖，則稱有向圖G=＜V,E＞是弱連通圖。如果有向圖G 的任意兩個(gè)不同結(jié)點(diǎn)至少有一個(gè)可達(dá)另一個(gè)，則稱G 是單向連通圖。如果G 的任意兩個(gè)不同結(jié)點(diǎn)都是互相可達(dá)的，則稱G 是強(qiáng)連通圖。

定理2.5 對(duì)有向圖G=＜V,E＞，若存在經(jīng)過(guò)每個(gè)結(jié)點(diǎn)至少一次的有向通路，則G 是單向連通圖，若存在經(jīng)過(guò)每個(gè)結(jié)點(diǎn)至少一次的有向回路，則G 是強(qiáng)連通圖。

例1 判斷下面圖的連通性。

解：根據(jù)定理2.5，我們可以很容易的判定圖（1）是強(qiáng)連通圖，圖（2）是單向連通圖，圖（3）是單向連通圖，圖（4）是無(wú)向圖的非連通圖。對(duì)于像例1 這樣的四個(gè)結(jié)點(diǎn)的圖的連通性的判定，我們可以直接利用定理2.5看是否形成經(jīng)過(guò)每個(gè)結(jié)點(diǎn)至少一次的有向回路或者通路確定，但如果結(jié)點(diǎn)過(guò)多，利用定理2.5 就有點(diǎn)困難，所以對(duì)于結(jié)點(diǎn)多的圖，我們考慮利用鄰接矩陣、可達(dá)矩陣的代數(shù)學(xué)知識(shí)輔助解決。

3 圖連通性的矩陣判別法

定義3.1 設(shè)G=＜V,E＞是簡(jiǎn)單圖，其中V 是點(diǎn)集，且|V|=n, E是邊集，n 階方陣稱為此簡(jiǎn)單圖的鄰接矩陣，

定理3.3 對(duì)簡(jiǎn)單圖G=＜V,E＞，其可達(dá)性矩陣P=A+A2+...+An,此處“+”是指布爾和。

定理3.4 對(duì)于簡(jiǎn)單圖G=＜V,E＞，鄰接矩陣是A，可達(dá)性矩陣是P，有：

圖G=＜V,E＞是強(qiáng)連通圖的充要條件是可達(dá)矩陣P 除對(duì)角線元素外所有元素都為1。

圖G=＜V,E＞是單向連通圖的充要條件是矩陣P+PT除對(duì)角線元素外所有元素都為1。

圖G=＜V,E＞是弱連通圖的充要條件是以矩陣A+AT=作為鄰接矩陣所得到的可達(dá)矩陣除對(duì)角線元素外所有元素都為1。

對(duì)應(yīng)這個(gè)鄰接矩陣，計(jì)算A2，A3，A4如下：

4 圖連通性判別法的計(jì)算機(jī)實(shí)現(xiàn)程序

本 文將圖論中的鄰接矩陣看成是二元關(guān)系的關(guān)系矩陣，改進(jìn)了著名的傳遞閉包的Warshall 算法來(lái)計(jì)算可達(dá)矩陣，并據(jù)此來(lái)判斷有向圖的連通性。對(duì)于稍微復(fù)雜的有向圖的連通性的判定問(wèn)題，利用例2 的方法去求解判定，計(jì)算量會(huì)很大，因此，本文給出了例2 有向圖連通性的判別法的python 語(yǔ)言程序如下：

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("可達(dá)矩陣")

print(a)

print("此圖為強(qiáng)聯(lián)通圖")

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("可達(dá)矩陣與其轉(zhuǎn)置矩陣布爾和矩陣")

print(a)

print("此圖為單向聯(lián)通圖")

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("無(wú)向圖的可達(dá)矩陣")

print(c)

print("此圖是弱連通圖")

else：

print("此圖不是連通圖")

在python3.7.3 shell 里執(zhí)行后顯示結(jié)果顯示如下：

5 結(jié)語(yǔ)

本文主要基于鄰接矩陣，改進(jìn)了Warshall 算法，并利用改進(jìn)的warshall 算法，基于python 語(yǔ)言平臺(tái)，給出了判斷有向簡(jiǎn)單圖和無(wú)向簡(jiǎn)單圖的連通性的判別算法，從而大大簡(jiǎn)化了圖的判定過(guò)程，提高了準(zhǔn)確性和效率。