圖的連通性與矩陣表示

1、12時，稱為回路。時，稱為回路。的長度。當?shù)拈L度。當稱為稱為中邊的數(shù)目中邊的數(shù)目的通路。的通路。到頂點到頂點為頂點為頂點，則稱，則稱的端點，的端點，是是和和滿足：滿足：，若，若為為中頂點和邊的交替序列中頂點和邊的交替序列，設(shè)，設(shè)給定無向圖給定無向圖1111112211, 2 , 1, kkiiikkvvkvvkievvveevevGEVG 1v3v2v4v1e2e3e4e如右圖所示：如右圖所示：的一條通路的一條通路到到就是就是2124321vvvevev的一條通路的一條通路到到也是也是212433411vvvevevev是一條回路是一條回路1233411vevevev3路。路。相同，則稱其為簡

2、單通相同，則稱其為簡單通若通路中的所有邊互不若通路中的所有邊互不路。路。相同，則稱其為簡單回相同，則稱其為簡單回若回路中的所有邊互不若回路中的所有邊互不初初級級（基基本本）通通路路。不不相相同同，則則稱稱其其為為若若通通路路中中的的所所有有頂頂點點互互回回路路。則則稱稱其其為為初初級級（基基本本）相相同同，相相同同外外，其其余余頂頂點點互互不不若若回回路路中中除除起起點點和和終終點點稱為復(fù)雜通路。稱為復(fù)雜通路。有邊重復(fù)出現(xiàn)的通路，有邊重復(fù)出現(xiàn)的通路，稱為復(fù)雜回路。稱為復(fù)雜回路。有邊重復(fù)出現(xiàn)的回路，有邊重復(fù)出現(xiàn)的回路，簡簡單單通通（回回）路路。初初級級通通（回回）路路一一定定是是43v5v2v1

3、v4v1e2e7e6e4e5e3e如右圖所示：如右圖所示：的一條初級通路的一條初級通路到到就是就是2123321vvvevev不不是是初初級級通通路路的的一一條條簡簡單單通通路路，但但卻卻到到也也是是2123364755321vvvevevevevev簡單回路。簡單回路。是一條初級回路，也是是一條初級回路，也是11475423321vevevevevev當當然然也也是是一一條條簡簡單單通通路路但不是初級回路但不是初級回路是一條簡單回路是一條簡單回路,1146355423321vevevevevevev5存在初級通路。存在初級通路。到到則從則從存在通路，存在通路，到頂點到頂點點點：在一個圖中，若

4、從頂：在一個圖中，若從頂定理定理jijijivvvvvv)(.12 . 7 。不大于不大于任何初級回路的長度均任何初級回路的長度均。不大于不大于任何初級通路的長度均任何初級通路的長度均階圖中，階圖中，：在一個：在一個定理定理nnn)2(1)1(2 . 2 . 7 6。回回路路的的長長度度都都不不大大于于、五五階階圖圖中中，任任意意初初級級41。通通路路的的長長度度都都不不大大于于、六六階階圖圖中中，任任意意初初級級52的的通通路路。為為、六六階階圖圖中中，存存在在長長度度73的的回回路路。為為、六六階階圖圖中中，存存在在長長度度64的通路。的通路。長度為長度為、六階完全圖中，存在、六階完全圖中

5、，存在55的回路。的回路。長度為長度為、六階完全圖中，存在、六階完全圖中，存在66判 斷 題7點。點。能夠到達其余的任意頂能夠到達其余的任意頂個中間頂點，個中間頂點，如有必要經(jīng)過一個或多如有必要經(jīng)過一個或多出發(fā)，出發(fā)，當且僅當從任一個頂點當且僅當從任一個頂點一個圖稱為是連通的，一個圖稱為是連通的，1v3v2v4v1e2e3e4e例例如如下下圖圖就就是是連連通通的的而而下下圖圖就就不不是是連連通通的的1v3v2v4v1e2e間都存在通路。間都存在通路。即：任意兩個不同頂點即：任意兩個不同頂點8對非連通圖，可以把它分成幾部分，使每一部分對非連通圖，可以把它分成幾部分，使每一部分都是連通的，且各部分

6、之間無公共結(jié)點。這樣分都是連通的，且各部分之間無公共結(jié)點。這樣分成的每一部分成為該非連通圖的成的每一部分成為該非連通圖的連通分枝連通分枝。9定義定義 在無向連通圖在無向連通圖G G中：中：（1 1）如果去掉某一條邊，圖）如果去掉某一條邊，圖G G將不連通，則稱將不連通，則稱這條邊為圖這條邊為圖G G的割邊或橋。的割邊或橋。（2 2）與圖）與圖G G的任意一個割邊相關(guān)聯(lián)的結(jié)點稱為的任意一個割邊相關(guān)聯(lián)的結(jié)點稱為圖圖G G的割點。的割點。（3 3）若）若S S為圖為圖G G的至少含有一條邊的子集，圖的至少含有一條邊的子集，圖G G去掉去掉S S則不連通，而去掉則不連通，而去掉S S的任一真子集仍然的

7、任一真子集仍然連通，則稱連通，則稱S S為圖為圖G G的割集。的割集。 10 例如下圖中例如下圖中: (b,c)、(d,i)是割邊是割邊，b、c、d、i是割點是割點，(b,c) 、(d,i) 、(a,b), (a,f) 、(a,f) , (b,f) , (f,g)是割集是割集，而，而(a,b)、(a,b), (b,g)不是割集。這里沒有把割集不是割集。這里沒有把割集和非割集全部列出。和非割集全部列出。 112、有向圖的連通性、有向圖的連通性定義定義2 2 在一個有向圖在一個有向圖D中，中，若從頂點若從頂點vi 到到vj 存在通路存在通路, ,則稱則稱vi 可達可達vj 。規(guī)定：規(guī)定：vi 到自

8、身總是可達的到自身總是可達的。v1可達可達v2,v4不可達不可達v112若有向圖若有向圖D略去所有有向邊的方向后所得略去所有有向邊的方向后所得的的無向圖是連無向圖是連通圖，則稱通圖，則稱D是是(弱弱)連通圖連通圖。特別地，特別地，若若D中任意兩頂點至少一個可達另一個，中任意兩頂點至少一個可達另一個， 則稱則稱D是是單向連通圖單向連通圖。 若若D中任意兩頂點都是相互可達的，中任意兩頂點都是相互可達的， 則稱則稱D是是強連通圖。強連通圖。結(jié)論：結(jié)論： 由定義可知，若圖由定義可知，若圖G G是單向連通的，則必是弱連通的；是單向連通的，則必是弱連通的；若圖若圖G G是強連通的，則必是單向連通的，且也是

9、弱連通的。是強連通的，則必是單向連通的，且也是弱連通的。但反之不真。但反之不真。13)a)b)c弱連通弱連通單向連通單向連通強連通強連通14定義定義設(shè)無向圖設(shè)無向圖G =V,E的結(jié)點集為的結(jié)點集為，,21nvvvV 邊集為邊集為，,21meeeE 則矩陣則矩陣稱為稱為G的鄰接矩陣，的鄰接矩陣，其中其中圖的矩陣表示1.無向圖的鄰接矩陣無向圖的鄰接矩陣nnijaGA )()( 01ija),(),(EvvEvvjiji 15例例2 2 寫出下圖所示無向圖寫出下圖所示無向圖G的鄰接矩陣的鄰接矩陣A(G)： 0111110001100101010111010)(GA16 如圖如圖7.3.1所示的圖所示

10、的圖G， 求其鄰接矩陣求其鄰接矩陣A0111110100110101010110010A 圖圖7.3.1 G 172.有向圖的鄰接矩陣有向圖的鄰接矩陣 與無向圖一樣，與無向圖一樣， 有向圖也能用相有向圖也能用相應(yīng)的鄰接矩陣表示應(yīng)的鄰接矩陣表示.但注意這里但注意這里A A 不一定是對稱的。不一定是對稱的。定義定義 設(shè)有向圖設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 為頂點為頂點vi鄰接到頂點鄰接到頂點vj邊的條數(shù)，邊的條數(shù)，稱稱( )m n為為D的鄰接矩陣的鄰接矩陣, 記作記作A(D), 簡記為簡記為A. )1(ija)1(ija183.無向圖的關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣定義定義設(shè)無向圖設(shè)無向圖G =V,E的結(jié)點集為的結(jié)點集為，,21nvvvV 邊集為邊集為，,21meeeE 則矩陣則矩陣mnijmGM )()(稱為稱為G的關(guān)聯(lián)矩陣，的關(guān)聯(lián)矩陣，其中其中的的關(guān)關(guān)聯(lián)聯(lián)次次數(shù)數(shù)。與與邊邊表表示示頂頂點點jiijevm19例例11 寫出下圖所示無向圖寫出下圖