圖的連通性和圖的矩陣表示

1、14.2 通路、回路 通路與回路是圖論中兩個重要而又基本的概念 本節(jié)所述定義一般說來既適合無向圖，也適合有向圖，否則將加以說明或分開定義。 1 定義14.11（通路、回路） 給定圖G，設(shè)G中頂點(diǎn)和邊的交替序列 =v0e1v1e2vi-1eivienvn 若滿足：對于i=1,2,n，vi-1和vi是ei的端點(diǎn)（在G是有向圖時，要求vi-1是ei的始點(diǎn)，vi是ei的終點(diǎn)），則稱為從v0到vn的一條通路或鏈（chain）。 v0和vn分別稱為此通路的起點(diǎn)和終點(diǎn)。 中邊的數(shù)目n稱為通路的長度(length) 當(dāng)v0=vn時，此通路稱為回路（circuit）說明（1）可以用邊的序列=e1e2en表示通路

2、或回路（2）在簡單圖中，可以只用頂點(diǎn)=v0v1vn表示通路或回路2 有邊重復(fù)出現(xiàn)的通路稱為復(fù)雜通路；有邊重復(fù)出現(xiàn)的回路稱為復(fù)雜回路。 若通路中無邊重復(fù)，則稱該通路為簡單通路；無邊重復(fù)的回路稱為簡單回路。 若通路中無邊重復(fù)且無頂點(diǎn)重復(fù)，則稱該通路為初級通路或路徑（path）；無邊重復(fù)且無頂點(diǎn)重復(fù)的回路稱為初級回路或圈（cycle）。 將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈。 易見 （1）初級通路(回路)是簡單通路(回路)，但反之不真。 （2）通路、回路是圖的子圖。3注意 （1）在無向圖中，環(huán)和平行邊構(gòu)成的回路分別是長度為1和2的初級回路（圈）。 （2）在有向圖中，環(huán)和兩條方向相反邊（對

3、稱邊）構(gòu)成的回路分別是長度為1和2的初級回路（圈）。 思考：在簡單無(有)向圖中，圈的長度至少為多長？ 在簡單無向圖中，圈的長度至少為3 在簡單有向圖中，圈的長度至少為24通路、回路的性質(zhì) 定理14.5 在一個n階圖中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長度小于等于n-1的通路。 推論 在一個n階圖中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長度小于等于n-1的初級通路。 定理14.6在一個n階圖中，若存在vi到自身的回路，則從vi到自身存在長度小于等于n的回路。 推論 在一個n階圖中，若存在vi到自身的簡單回路，則從vi到自身存在長度小于等于n的初級

4、回路。 514.3 圖的連通性6 首先討論無向圖的連通性。 定義14.12（連通） 在一個無向圖G=中，如果頂點(diǎn)u，v之間存在通路，則稱u，v是連通的（connected），記作uv。vV，規(guī)定vv。 由連通的定義可以定義如下的無向圖中頂點(diǎn)之間的連通關(guān)系: =|u,vVu與v之間有通路 顯然是自反的、對稱的、傳遞的，所以是V上的等價關(guān)系。 7 定義14.13（無向連通圖） 若無向圖G是平凡圖或G中的任何兩個頂點(diǎn)都是連通的，則稱G是連通圖（connected graph），否則稱G為非連通圖或分離圖（disconnected graph）。 例：完全圖Kn（n1）為連通圖， 零圖Nn（n2）都是

5、分離圖。8 定義14.14（連通分支） 設(shè)無向圖G=，V關(guān)于頂點(diǎn)之間的連通關(guān)系的商集V/=V1,V2,Vk，Vi為等價類，稱Vi的導(dǎo)出子圖GVi（i=1,2,k）為G的連通分支（connected component），連通分支數(shù)k常記為p(G)。 或 若無向圖G由若干彼此不連通的子圖組成，而每個子圖是連通的，稱這些子圖為G的連通分支。 顯然若G為連通圖，則p(G)=1； 若G為非連通圖，則p(G)2； Nn（n2）的連通分支為p(G)=n9 思考題 （1）n階非連通的簡單圖的邊數(shù)最多有多少條？最少呢？P289/P292-6(2) （2）證明：若無向圖G中恰有兩個奇度頂點(diǎn)，這兩個奇度頂點(diǎn)必然連

6、通。P291/P293-3910 下面討論有向圖的連通性 定義14.20在一個有向圖D=中，如果頂點(diǎn)u，v之間存在通路，則稱u可達(dá)v，記作uv。 規(guī)定任意的頂點(diǎn)總是可達(dá)自身的，即uV，uu。 若uv且vu，則稱u與v是相互可達(dá)的，記作uv，規(guī)定uu。11 有向圖有三種不同類型的連通圖 定義14.22（弱、單向、強(qiáng)連通圖） 在一個有向圖D中， 如果D的基圖是連通圖，則稱D是弱連通圖(weakly connected graph )。 如果對于任意的兩個頂點(diǎn)u，v，uv與vu至少成立其一，則稱D是單向連通圖（unilateral connected graph ）。 如果對于任意的兩個頂點(diǎn)u，v，

7、均有uv，則稱D是強(qiáng)連通圖（strongly connected graph ）。 說明：強(qiáng)連通圖一定是單向連通圖，單向連通圖一定是弱連通圖。12 強(qiáng)連通圖和單向連通圖的判別定理 定理14.8 有向圖D是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點(diǎn)至少一次的回路。 定理14.9 有向圖D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點(diǎn)至少一次的通路。13例 （1） （2） （3） （1）是強(qiáng)連通圖（2）是單向連通圖（3）是弱連通圖 1414.4 圖的矩陣表示15圖的表示 （1）集合定義 （2）圖形表示 （3）矩陣表示目的 （1）便于用代數(shù)知識來研究圖的性質(zhì) （2）便于用計算機(jī)來對圖進(jìn)行處理本節(jié)學(xué)習(xí) （1）圖的

8、關(guān)聯(lián)矩陣(無向圖和有向圖) （2）有向圖的鄰接矩陣 （3）有向圖的可達(dá)矩陣16 定義14.24（無向圖的關(guān)聯(lián)矩陣）設(shè)無向圖G=，V=v1,v2,vn，E=e1,e2,em，令mij為頂點(diǎn)vi與邊ej的關(guān)聯(lián)次數(shù)，則稱(mij)nm為G的關(guān)聯(lián)矩陣，記為M(G)。 易見，矩陣的第i行為頂點(diǎn)vi分別與邊e1,e2,em的關(guān)聯(lián)次數(shù)。 矩陣的第j列為邊ej分別與頂點(diǎn)v1,v2,vn的關(guān)聯(lián)次數(shù)。對于mij顯然有17例如：求下圖的關(guān)聯(lián)矩陣 關(guān)聯(lián)矩陣為： 18無向圖關(guān)聯(lián)矩陣的性質(zhì)： 即關(guān)聯(lián)矩陣中每條邊關(guān)聯(lián)兩個頂點(diǎn)（環(huán)關(guān)聯(lián)的頂點(diǎn)重合） 即關(guān)聯(lián)矩陣中第i行元素之和為頂點(diǎn)vi的度數(shù)。 即握手定理：各頂點(diǎn)的度數(shù)之和等于

9、邊數(shù)的2倍。(4) 第j列與第k列相同，當(dāng)且僅當(dāng)邊ej與ek是平行邊。當(dāng)且僅當(dāng)vi是孤立點(diǎn)。19 定義14.25（有向圖的關(guān)聯(lián)矩陣）設(shè)有向圖D=中無環(huán)，V=v1,v2,vn，E=e1,e2,em，令則稱(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D)。20例如：下圖的關(guān)聯(lián)矩陣為 關(guān)聯(lián)矩陣為： 21有向圖關(guān)聯(lián)矩陣的性質(zhì)： 22有向圖關(guān)聯(lián)矩陣的性質(zhì)： （1） ，從而 ，這說明有向圖關(guān)聯(lián)矩陣中所有元素之和為0。 23有向圖關(guān)聯(lián)矩陣的性質(zhì)： （1） ，從而 ，這說明有向圖關(guān)聯(lián)矩陣中所有元素之和為0。 （2）有向圖關(guān)聯(lián)矩陣中，-1的個數(shù)、1的個數(shù)、邊數(shù)m相等。這正是有向圖握手定理的內(nèi)容。24有向圖關(guān)聯(lián)矩陣的性

10、質(zhì)： （1） ，從而 ，這說明有向圖關(guān)聯(lián)矩陣中所有元素之和為0。 （2）有向圖關(guān)聯(lián)矩陣中，-1的個數(shù)、1的個數(shù)、邊數(shù)m相等。這正是有向圖握手定理的內(nèi)容。 （3）在有向圖關(guān)聯(lián)矩陣第i行中，1的個數(shù)等于d+(vi)，-1的個數(shù)等于 d-(vi)。25有向圖關(guān)聯(lián)矩陣的性質(zhì)： （1） ，從而 ，這說明有向圖關(guān)聯(lián)矩陣中所有元素之和為0。 （2）有向圖關(guān)聯(lián)矩陣中，-1的個數(shù)、1的個數(shù)、邊數(shù)m相等。這正是有向圖握手定理的內(nèi)容。 （3）在有向圖關(guān)聯(lián)矩陣第i行中，1的個數(shù)等于d+(vi)，-1的個數(shù)等于 d-(vi)。 （4）平行邊所對應(yīng)的列相同。 26 定義14.26（有向圖鄰接矩陣）設(shè)有向圖D=，V=v1,

11、v2,vn，令aij(1)為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱(aij(1)nn為D的鄰接矩陣，記作A(D)，簡記為A。例如：下圖的鄰接矩陣為27有向圖鄰接矩陣的性質(zhì)：(1) ，于是28有向圖鄰接矩陣的性質(zhì)：(1) ，于是(2) ，于是29有向圖鄰接矩陣的性質(zhì)：(1) ，于是(2) ，于是(3)所有元素之和 為D中邊的總數(shù)，也可看成D中 長度為1的通路的總數(shù)。30有向圖鄰接矩陣的性質(zhì)：(1) ，于是(2) ，于是(3)所有元素之和 為D中邊的總數(shù)，也可看成D中 長度為1的通路的總數(shù)。 而 為D中環(huán)的個數(shù)，即D中長度為1的回路總數(shù)。 31 問下圖中有多少條長度為2、3、4.的通路？32A2 =?

12、A2=A33 利用有向圖鄰接矩陣計算D中長度為d(d1)的通路數(shù)和回路數(shù)。 對于d=2,3,， 定義Ad=Ad(D)=(aij(d)nn，其中在Ad中aij(d)為頂點(diǎn)vi到頂點(diǎn)vj長度為d的通路數(shù)aii(d)為頂點(diǎn)vi到自身的長度為d的回路數(shù) 為D中長度為d的通路總數(shù) 為D中始于各頂點(diǎn)的長度為d的回路總數(shù) 34 定理14.11 設(shè)A為有向圖D的鄰接矩陣，則Ad（d1）中元素為aij(d)為頂點(diǎn)vi到頂點(diǎn)vj長度為d的通路數(shù)， 為D中長度為d的通路總數(shù)，為D中長度為d的回路總數(shù)。 推論 設(shè)Bd=A+A2+Ad（d1），則Bd中元素bij(d)為D中頂點(diǎn)vi到頂點(diǎn)vj長度小于等于d的通路數(shù)， 為D中長度小于等于d的通路總數(shù)， 為D中長度小于等于d的回路總數(shù)。35例：求右邊有向圖D中（1）端點(diǎn)v2到v4長度為1，2，3，4的通路分別為多少條？（2）端點(diǎn)v4到自身長度為1，2，3，4的回路分別為多少條？（3）長度小于等于4的通路和回路分別有多少條？解：有向圖D的鄰接矩陣為端點(diǎn)v2到v4長度為1，2，3，4的通路分別為0，1，1，2條端點(diǎn)v4到自身長度為1，2，3，4的回路分