圖的連通性和14.4圖的矩陣表.pptVIP

1,14.2 通路、回路,通路與回路是圖論中兩個(gè)重要而又基本的概念 本節(jié)所述定義一般說來既適合無向圖，也適合有向圖，否則將加以說明或分開定義。,2,定義14.11（通路、回路） 給定圖G，設(shè)G中頂點(diǎn)和邊的交替序列 =v0e1v1e2vi-1eivienvn 若滿足：對于i=1,2,n，vi-1和vi是ei的端點(diǎn)（在G是有向圖時(shí)，要求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時(shí)，此通路稱為回路（circuit）,說明 （1）可以用邊的序列=e1e2en表示通路或回路 （2）在簡單圖中，可以只用頂點(diǎn)=v0v1vn表示通路或回路,3,有邊重復(fù)出現(xiàn)的通路稱為復(fù)雜通路；有邊重復(fù)出現(xiàn)的回路稱為復(fù)雜回路。 若通路中無邊重復(fù)，則稱該通路為簡單通路；無邊重復(fù)的回路稱為簡單回路。 若通路中無邊重復(fù)且無頂點(diǎn)重復(fù)，則稱該通路為初級通路或路徑（path）；無邊重復(fù)且無頂點(diǎn)重復(fù)的回路稱為初級回路或圈（cycle）。 將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈。 易見 （1）初級通路(回路)是簡單通路(回路)，但反之不真。 （2）通路、回路是圖的子圖。,4,注意 （1）在無向圖中，環(huán)和平行邊構(gòu)成的回路分別是長度為1和2的初級回路（圈）。 （2）在有向圖中，環(huán)和兩條方向相反邊（對稱邊）構(gòu)成的回路分別是長度為1和2的初級回路（圈）。,思考：在簡單無(有)向圖中，圈的長度至少為多長？ 在簡單無向圖中，圈的長度至少為3 在簡單有向圖中，圈的長度至少為2,5,通路、回路的性質(zhì) 定理14.5 在一個(gè)n階圖中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長度小于等于n-1的通路。 推論 在一個(gè)n階圖中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長度小于等于n-1的初級通路。 定理14.6在一個(gè)n階圖中，若存在vi到自身的回路，則從vi到自身存在長度小于等于n的回路。 推論 在一個(gè)n階圖中，若存在vi到自身的簡單回路，則從vi到自身存在長度小于等于n的初級回路。,6,14.3 圖的連通性,7,首先討論無向圖的連通性。 定義14.12（連通） 在一個(gè)無向圖G=中，如果頂點(diǎn)u，v之間存在通路，則稱u，v是連通的（connected），記作uv。vV，規(guī)定vv。 由連通的定義可以定義如下的無向圖中頂點(diǎn)之間的連通關(guān)系: =|u,vVu與v之間有通路 顯然是自反的、對稱的、傳遞的，所以是V上的等價(jià)關(guān)系。,8,定義14.13（無向連通圖） 若無向圖G是平凡圖或G中的任何兩個(gè)頂點(diǎn)都是連通的，則稱G是連通圖（connected graph），否則稱G為非連通圖或分離圖（disconnected graph）。 例：完全圖Kn（n1）為連通圖， 零圖Nn（n2）都是分離圖。,9,定義14.14（連通分支） 設(shè)無向圖G=，V關(guān)于頂點(diǎn)之間的連通關(guān)系的商集V/=V1,V2,Vk，Vi為等價(jià)類，稱Vi的導(dǎo)出子圖GVi（i=1,2,k）為G的連通分支（connected component），連通分支數(shù)k常記為p(G)。 或 若無向圖G由若干彼此不連通的子圖組成，而每個(gè)子圖是連通的，稱這些子圖為G的連通分支。 顯然若G為連通圖，則p(G)=1； 若G為非連通圖，則p(G)2； Nn（n2）的連通分支為p(G)=n,10,思考題 （1）n階非連通的簡單圖的邊數(shù)最多有多少條？最少呢？P289/P292-6(2) （2）證明：若無向圖G中恰有兩個(gè)奇度頂點(diǎn)，這兩個(gè)奇度頂點(diǎn)必然連通。P291/P293-39,11,下面討論有向圖的連通性 定義14.20在一個(gè)有向圖D=中，如果頂點(diǎn)u，v之間存在通路，則稱u可達(dá)v，記作uv。 規(guī)定任意的頂點(diǎn)總是可達(dá)自身的，即uV，uu。 若uv且vu，則稱u與v是相互可達(dá)的，記作uv，規(guī)定uu。,12,有向圖有三種不同類型的連通圖 定義14.22（弱、單向、強(qiáng)連通圖） 在一個(gè)有向圖D中， 如果D的基圖是連通圖，則稱D是弱連通圖(weakly connected graph )。 如果對于任意的兩個(gè)頂點(diǎn)u，v，uv與vu至少成立其一，則稱D是單向連通圖（unilateral connected graph ）。 如果對于任意的兩個(gè)頂點(diǎn)u，v，均有uv，則稱D是強(qiáng)連通圖（strongly connected graph ）。 說明：強(qiáng)連通圖一定是單向連通圖，單向連通圖一定是弱連通圖。,13,強(qiáng)連通圖和單向連通圖的判別定理 定理14.8 有向圖D是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路。 定理14.9 有向圖D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。,14,例,（1） （2） （3）,（1）是強(qiáng)連通圖 （2）是單向連通圖 （3）是弱連通圖,15,14.4 圖的矩陣表示,16,圖的表示 （1）集合定義 （2）圖形表示 （3）矩陣表示 目的 （1）便于用代數(shù)知識來研究圖的性質(zhì) （2）便于用計(jì)算機(jī)來對圖進(jìn)行處理 本節(jié)學(xué)習(xí) （1）圖的關(guān)聯(lián)矩陣(無向圖和有向圖) （2）有向圖的鄰接矩陣 （3）有向圖的可達(dá)矩陣,17,定義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顯然有,18,例如：求下圖的關(guān)聯(lián)矩陣,關(guān)聯(lián)矩陣為：,19,無向圖關(guān)聯(lián)矩陣的性質(zhì)：,即關(guān)聯(lián)矩陣中每條邊關(guān)聯(lián)兩個(gè)頂點(diǎn)（環(huán)關(guān)聯(lián)的頂點(diǎn)重合）,即關(guān)聯(lián)矩陣中第i行元素之和為頂點(diǎn)vi的度數(shù)。,即握手定理：各頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍。,(4) 第j列與第k列相同，當(dāng)且僅當(dāng)邊ej與ek是平行邊。,當(dāng)且僅當(dāng)vi是孤立點(diǎn)。,20,定義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)。,21,例如：下圖的關(guān)聯(lián)矩陣為,關(guān)聯(lián)矩陣為：,22,有向圖關(guān)聯(lián)矩陣的性質(zhì)：,23,有向圖關(guān)聯(lián)矩陣的性質(zhì)： （1） ，從而 ，這說明有向圖關(guān)聯(lián)矩陣中所有元素之和為0。,24,有向圖關(guān)聯(lián)矩陣的性質(zhì)： （1） ，從而 ，這說明有向圖關(guān)聯(lián)矩陣中所有元素之和為0。 （2）有向圖關(guān)聯(lián)矩陣中，-1的個(gè)數(shù)、1的個(gè)數(shù)、邊數(shù)m相等。這正是有向圖握手定理的內(nèi)容。,25,有向圖關(guān)聯(lián)矩陣的性質(zhì)： （1） ，從而 ，這說明有向圖關(guān)聯(lián)矩陣中所有元素之和為0。 （2）有向圖關(guān)聯(lián)矩陣中，-1的個(gè)數(shù)、1的個(gè)數(shù)、邊數(shù)m相等。這正是有向圖握手定理的內(nèi)容。 （3）在有向圖關(guān)聯(lián)矩陣第i行中，1的個(gè)數(shù)等于d+(vi)，-1的個(gè)數(shù)等于 d-(vi)。,26,有向圖關(guān)聯(lián)矩陣的性質(zhì)： （1） ，從而 ，這說明有向圖關(guān)聯(lián)矩陣中所有元素之和為0。 （2）有向圖關(guān)聯(lián)矩陣中，-1的個(gè)數(shù)、1的個(gè)數(shù)、邊數(shù)m相等。這正是有向圖握手定理的內(nèi)容。 （3）在有向圖關(guān)聯(lián)矩陣第i行中，1的個(gè)數(shù)等于d+(vi)，-1的個(gè)數(shù)等于 d-(vi)。 （4）平行邊所對應(yīng)的列相同。,27,定義14.26（有向圖鄰接矩陣）設(shè)有向圖D=，V=v1,v2,vn，令aij(1)為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱(aij(1)nn為D的鄰接矩陣，記作A(D)，簡記為A。,例如：下圖的鄰接矩陣為,28,有向圖鄰接矩陣的性質(zhì)： (1) ，于是,29,有向圖鄰接矩陣的性質(zhì)： (1) ，于是 (2) ，于是,30,有向圖鄰接矩陣的性質(zhì)： (1) ，于是 (2) ，于是 (3)所有元素之和 為D中邊的總數(shù)，也可看成D中 長度為1的通路的總數(shù)。,31,有向圖鄰接矩陣的性質(zhì)： (1) ，于是 (2) ，于是 (3)所有元素之和 為D中邊的總數(shù)，也可看成D中 長度為1的通路的總數(shù)。 而 為D中環(huán)的個(gè)數(shù)，即D中長度為1的回路總數(shù)。,32,問下圖中有多少條長度為2、3、4.的通路？,33,A2 =?,A2=A,34,利用有向圖鄰接矩陣計(jì)算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ù),35,定理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ù)。,36,例：求右邊有向圖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的回