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

1 引言

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

2 基本概念

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

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

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

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

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

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

3 圖連通性的矩陣判別法

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

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

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

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

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

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

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

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

本 文將圖論中的鄰接矩陣看成是二元關(guān)系的關(guān)系矩陣，改進(jìn)了著名的傳遞閉包的Warshall 算法來計(jì)算可達(dá)矩陣，并據(jù)此來判斷有向圖的連通性。對于稍微復(fù)雜的有向圖的連通性的判定問題，利用例2 的方法去求解判定，計(jì)算量會很大，因此，本文給出了例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("可達(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("無向圖的可達(dá)矩陣")

print(c)

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

else：

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

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

5 結(jié)語

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