《《離散數(shù)學(xué)》PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《《離散數(shù)學(xué)》PPT課件（71頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、離散數(shù)學(xué),1,一、圖 定義一個(gè)圖是一個(gè)三元組,簡記為G。,7-1 圖的基本概念,其中： Vv1,v2,v3,,vn是一個(gè)非空集合,vi(i1,2,3,,n)稱為結(jié)點(diǎn),簡稱點(diǎn),V為結(jié)點(diǎn)集； Ee1,e2,e3,,em是一個(gè)有限的集合，ei(i1,2,3,,m)稱為邊,E為邊集，E中的每個(gè)元素都有V中的結(jié)點(diǎn)對（有序偶或無序偶）與之對應(yīng)。 例,離散數(shù)學(xué),2,圖的術(shù)語,圖的術(shù)語 若邊e與結(jié)點(diǎn)無序偶(u，v)相對應(yīng)，則稱邊e為無向邊,記為e(u，v)，這時(shí)稱u，v是邊e的兩個(gè)端點(diǎn)； 若邊e與結(jié)點(diǎn)有偶相對應(yīng)，則稱邊e為有向邊(或弧)，記為e，這時(shí)稱u是邊e的始點(diǎn)(或弧尾).v是邊e的終點(diǎn)(或弧頭)，統(tǒng)稱為

2、e的端點(diǎn)； 在一個(gè)圖中，關(guān)聯(lián)結(jié)點(diǎn)vi和vj的邊e，無論是有向的還是無向的，均稱邊e與結(jié)點(diǎn)vI和vj相關(guān)聯(lián)，而vi和vj稱為鄰接點(diǎn)，否則稱為不鄰接的；,離散數(shù)學(xué),3,續(xù)：,續(xù)： 關(guān)聯(lián)于同一個(gè)結(jié)點(diǎn)的兩條邊稱為鄰接邊； 圖中關(guān)聯(lián)同一個(gè)結(jié)點(diǎn)的邊稱為自回路(或環(huán))； 圖中不與任何結(jié)點(diǎn)相鄰接的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)； 僅由孤立結(jié)點(diǎn)組成的圖稱為零圖； 僅含一個(gè)結(jié)點(diǎn)的零圖稱為平凡圖； 含有n個(gè)結(jié)點(diǎn)、m條邊的圖稱為(n，m)圖；,離散數(shù)學(xué),4,續(xù)：,續(xù)： 每條邊都是無向邊的圖稱為無向圖； 每條邊都是有向邊的圖稱為有向圖； 有些邊是無向邊，而另一些是有向邊的圖稱為混合圖。 在有向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有同

3、始點(diǎn)和同終點(diǎn)的幾條邊，則這幾條邊稱為平行邊，在無向圖中，兩個(gè)結(jié)點(diǎn)間(包括結(jié)點(diǎn)自身間)若有幾條邊，則這幾條邊稱為平行邊，兩結(jié)點(diǎn)vi，vj間相互平行的邊的條數(shù)稱為邊(vi，vj)或的重?cái)?shù)； 含有平行邊的圖稱為多重圖。非多重圖稱為線圖；無自回路的線圖稱為簡單圖。,離散數(shù)學(xué),5,(a),例：,(b),(c),(d),例：,離散數(shù)學(xué),6,(e),(f),例：,例：,(g),離散數(shù)學(xué),7,二、度數(shù) 定義 在無向圖G中，與結(jié)點(diǎn)v(vV)關(guān)聯(lián)的邊的條數(shù)，稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)；,二、度數(shù),定義 在有向圖G中，以結(jié)點(diǎn)v(vV)為始點(diǎn)引出的邊的條數(shù)，稱為該結(jié)點(diǎn)的引出度數(shù),簡稱出度,記為deg+(v)；

4、以結(jié)點(diǎn)v(vV)為終點(diǎn)引入的邊的條數(shù)，稱為該結(jié)點(diǎn)的引入度數(shù)，簡稱入度,記為deg-(v)；而結(jié)點(diǎn)的出度和入度之和稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)，即deg(v)deg+(v)+deg-(v)； (G)最小度，(G)最大度 定義 在圖G中，對任意結(jié)點(diǎn)vV，若度數(shù)deg(v)為奇數(shù)，則稱此結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn)，若度數(shù)deg(v)為偶數(shù)，則稱此結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn)。,離散數(shù)學(xué),8,例： deg(v1)3，deg+(v1)2，deg-(v1)1； deg(v2)3，deg+(v2)2，deg-(v2)1； deg(v3)5，deg+(v3)2，deg-(v3)3； deg(v4)deg+(v4)deg-(v

5、4)0； deg(v5)1，deg+(v5)0，deg-(v5)1；,例：,離散數(shù)學(xué),9,定理,定理 1.在圖G中，則所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍，即：,在有向圖G中，則所有結(jié)點(diǎn)的出度之和等于所有結(jié)點(diǎn)的入度之和，即： 3.定理 在所有圖中，度數(shù)為奇數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù).,離散數(shù)學(xué),10,定理,,。,證明設(shè)V1v|vV且deg(v)奇數(shù)，V2v|vV且deg(v)偶數(shù)。顯然，V1V2，且V1V2V，于是有：,由于上式中的2m和偶度數(shù)結(jié)點(diǎn)度數(shù)之和均為偶數(shù)，因而也為偶數(shù)。于是|V1|為偶數(shù)(因?yàn)閂1中的結(jié)點(diǎn)v之deg(v)都為奇數(shù))，即奇度數(shù)的結(jié)點(diǎn)個(gè)數(shù)為偶數(shù)。,離散數(shù)學(xué),11,三、完全圖,三、

6、完全圖 定義 在圖G中，若所有結(jié)點(diǎn)的度數(shù)均有相同度數(shù)d，則稱此圖為d次正則圖。 定義 一個(gè)(n，m)(n2)的簡單無向圖，若它為n-1次正則圖，則稱該(n，m)圖為無向簡單完全圖，簡稱完全圖,記為Kn。 有向完全圖 定理 設(shè)無向完全圖G有n個(gè)頂點(diǎn)，則G有 條邊。,離散數(shù)學(xué),12,四、子圖和補(bǔ)圖 定義 設(shè)有圖G和圖G1，若G和G1滿足： 若V1V，E1E，則稱G1是G的子圖，記為G1G； 若G1G，且G1G(即V1V或E1E)，則稱G1是G的真子圖，記為G1G； 定義 若V1V，E1E，則稱G1是G的生成子圖，記為G1G； 定義設(shè)有圖G和圖G2，若V2V，V2，以V2為結(jié)點(diǎn)集，以兩個(gè)端點(diǎn)均在V2

7、中的邊的全體為邊集的G的子圖稱為V2導(dǎo)出的子圖，簡稱G的導(dǎo)出子圖。,四、子圖和補(bǔ)圖,離散數(shù)學(xué),13,例：,例：,它的真子圖G和生成子圖G。,離散數(shù)學(xué),14,四、子圖和補(bǔ)圖 定義 設(shè)G為具有n個(gè)結(jié)點(diǎn)的簡單圖,從完全圖Kn中刪去G中的所有的邊而得到的圖稱為G的補(bǔ)圖(或G的補(bǔ))，記為 。關(guān)于完全圖的子圖的補(bǔ)圖稱為此子圖的絕對補(bǔ)圖。 定義 是圖，是的子圖，”，” 是”中邊所關(guān)聯(lián)的所有頂點(diǎn)集合，則”稱為關(guān)于的相對補(bǔ)圖。,四、子圖和補(bǔ)圖,離散數(shù)學(xué),15,例：,例：求下圖的補(bǔ)圖。,離散數(shù)學(xué),16,五、圖的同構(gòu),五、圖的同構(gòu) 例:如下圖 (a)、(b)、(c)、(d)所示。,圖(a)、圖(b)、圖(c)和圖(

8、d)所表示的圖形實(shí)際上都是一樣的,離散數(shù)學(xué),17,定義,定義 設(shè)有圖G和圖G1,如果存在雙射函數(shù)g:VV1,且e(vi,vj)(或)是G的一條邊當(dāng)且僅當(dāng)e1(g(vi),g(vj)) (或) 是G1的一條邊則稱G和G1同構(gòu)，記為GG1。 同構(gòu)的充要條件：兩個(gè)圖的結(jié)點(diǎn)和邊分別存在一一對應(yīng)，且保持關(guān)聯(lián)關(guān)系。,離散數(shù)學(xué),18,例：,例：如圖(a)、(b)所示的兩個(gè)圖G和G1，GG1？,解：顯然，定義函數(shù)g：VV1，滿足g(vi)vi（i1，2，3，4，5），可以驗(yàn)證g一定是一個(gè)滿足定義的雙射，所以GG1。,離散數(shù)學(xué),19,必要條件,兩個(gè)圖同構(gòu)的必要條件： 結(jié)點(diǎn)數(shù)目相同； 邊數(shù)相同； 度數(shù)相同的結(jié)點(diǎn)數(shù)

9、相同。,注意：這三個(gè)條件并不是充分條件。例如下面兩個(gè)圖滿足這三個(gè)條件，但它們不同構(gòu)。,離散數(shù)學(xué),20,7-2 路與回路,一、路,定義 給定圖G=V,E,設(shè)v0，v1，，vnV,e1，e2，，enE,其中ei是關(guān)聯(lián)結(jié)點(diǎn)vi-1,vi的邊,交替序列v0e1v1e2envn稱為聯(lián)結(jié)v0到vn的路。 v0,vn分別為該路的起點(diǎn)和終點(diǎn)，統(tǒng)稱為路的端點(diǎn)。 路中邊的條數(shù)稱為該路的長度。 此時(shí)，若v0vn，則該路稱為回路。,離散數(shù)學(xué),21,若路中所有邊全不相同，則稱此路為一條跡； 若路中所有結(jié)點(diǎn)全不相同，則稱此路為通路。 若回路中除v0vn以外所有結(jié)點(diǎn)全不相同，則稱此圈。（閉的通路） 在簡單圖中一條路v0e1

10、v1e2envn ，由它的結(jié)點(diǎn)序列v0v1 vn確定,所以簡單圖的路,由可由其結(jié)點(diǎn)序列v0v1 vn表示。在有向圖中,結(jié)點(diǎn)數(shù)大于1的一條路可由邊序列e1e2 en 表示。,續(xù)：,離散數(shù)學(xué),22,例：考慮如下路：,例：,離散數(shù)學(xué),23,定理,定理在一個(gè)具有n個(gè)結(jié)點(diǎn)的圖中，如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路，則從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk必存在一條不多于n-1條邊的路。,推論在無向圖G中，如果從結(jié)點(diǎn)vj到結(jié)點(diǎn)vk存在一條路，則必存在一條從vj到vk而長度小于n的通路。,離散數(shù)學(xué),24,二、無向圖的連通性,二、無向圖的連通性 定義 設(shè)G是一個(gè)圖，對vi，vjV，從vi到vj如存在一條路，則稱結(jié)點(diǎn)vi和vj是

11、連通的。 定義 設(shè)G是一個(gè)無向圖，該無向圖G中的每個(gè)連通的劃分塊稱為G的一個(gè)連通分支，用W(G)表示G中的連通分支數(shù)。 定義 設(shè)G是一個(gè)無向圖，若G中任意兩個(gè)結(jié)點(diǎn)之間都是連通的，即圖G只有一個(gè)連通分支，則稱該無向圖G是一個(gè)無向連通圖，否則，則稱G是一個(gè)非連通圖(或分離圖)。,離散數(shù)學(xué),25,G1是連通圖，W(G1)1； G2是非連通圖，且W(G2)4。,例：,例：,離散數(shù)學(xué),26,定義設(shè)無向圖G=V,E為連通的，若有結(jié)點(diǎn)集V1是V的真子集，使得圖G刪除了V1所有結(jié)點(diǎn)后，所得的子圖是不連通的，而刪除了V1的任意真子集后，所得的子圖仍然是連通圖。則稱集合V1為圖G的點(diǎn)割集。若某一結(jié)點(diǎn)就構(gòu)成點(diǎn)割集，

12、則稱該結(jié)點(diǎn)為割點(diǎn)。 這樣，一個(gè)連通圖，刪除它的一個(gè)點(diǎn)割集后，將分成兩個(gè)或多于兩個(gè)連通分支。,割點(diǎn),離散數(shù)學(xué),27,割點(diǎn),若G不是完全圖，我們定義k(G)=min| V1 | |V1 是G的點(diǎn)割集為G的點(diǎn)連通度(或連通度)。 連通度k(G)是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的 點(diǎn)的最少數(shù)目。 一個(gè)不連通圖的連通度等于 存在著割點(diǎn)的連通圖的點(diǎn)連通度 完全圖Kp的點(diǎn)連通度,離散數(shù)學(xué),28,定義 設(shè)無向圖G=V,E為連通的，若有邊集E1是E的真子集，使得圖G刪除了E1所有邊后，所得的子圖是不連通的，而刪除了E1的任意真子集后，所得的子圖仍然是連通圖。則稱集合E1為圖G的邊割集。若某一邊構(gòu)成邊割集，則稱該邊

13、為割邊(或橋)。 G的割邊也就是G中的一條邊e使得W(G-e)W(G)。 例,割邊,離散數(shù)學(xué),29,割邊,與點(diǎn)連通度相似，我們定義非平凡圖G的邊連通 度為：(G)=min| E1 ||E1是G的邊割集，邊連 通度(G)是為了產(chǎn)生一個(gè)不連通需要?jiǎng)h去邊的 最少數(shù)目。 平凡圖(G ) 一個(gè)不連通圖(G),離散數(shù)學(xué),30,定理 對于任何一個(gè)圖G =V,E，有 k(G)(G)(G) 證明 若G不連通，則k(G)=(G)=0，故上式成立。 若G連通， 證明(G)(G)。若G是平凡圖，則(G)=0(G)，若G是非平凡圖，則因每一結(jié)點(diǎn)的所有關(guān)連邊必含一個(gè)邊割集，故(G)(G)。,定理,離散數(shù)學(xué),31,再證k(

14、G)(G) .設(shè)(G)=1，即G有一割邊，顯然此時(shí)k(G)=1，上式成立。 .設(shè)(G)2，則必可刪去某(G)條邊，使G不連通，而刪除(G)-1條邊，它仍然連通，而且有一條橋e=(u，v)。對(G)-1條邊中每一條邊都選取一個(gè)不同于u，v的端點(diǎn)，將這些端點(diǎn)刪去必至少刪去(G)-1條邊。若這樣產(chǎn)生的圖是不連通的，則k(G)(G)-1(G)，若這樣產(chǎn)生的圖是連通的，則e=(u，v)仍然是橋，此時(shí)再刪去u，v，就必產(chǎn)生一個(gè)不連通圖，故k(G)(G)。 由此得k(G)(G)(G)。,續(xù)：,離散數(shù)學(xué),32,定理 一個(gè)連通無向圖G =V,E的某一點(diǎn)v是圖G的割點(diǎn)，當(dāng)且僅當(dāng)存在兩個(gè)節(jié)點(diǎn)u和w，使得節(jié)點(diǎn)u和w的

15、每一條路都通過v。,定理,離散數(shù)學(xué),33,三、有向圖的連通性,三、有向圖的連通性 定義 設(shè)G是一個(gè)有向圖，對vi，vjV，從vi到vj如存在一條路，則稱結(jié)點(diǎn)vi到vj是可達(dá)的。,在有向圖中，如從vi到vj可達(dá)，但從vj到vi則不一定是可達(dá)的。,為此，若將可達(dá)性看成是圖G的結(jié)點(diǎn)集合V上的二元關(guān)系的話，對有向圖來說，該可達(dá)性關(guān)系滿足什么性質(zhì)？,離散數(shù)學(xué),34,定義,定義 在圖G中，對vi，vjV，如果從vi到vj存在路，則稱長度最短的路為從vi到vj的短程線,從vi到vj的短程線的長度稱為從vi到vj的距離，記為d(vi,vj)。 d(vi，vj)滿足下列性質(zhì)： d(vi，vj)0； d(vi，v

16、i)0； d(vi，vk)+d(vk，vj) d(vi，vj)； d(vi，vj)(當(dāng)vi到vj不可達(dá))。 此外，有關(guān)距離的概念對無向圖也適用。,離散數(shù)學(xué),35,在(a)中有： d(v2，v1)d(v1，v2) d(v3，v1)d(v1，v3) 在(b)中有： d(v1，v3)，d(v3，v7)，d(v1，v7)。,例：,例：,離散數(shù)學(xué),36,定義 設(shè)G是一個(gè)有向圖，若G中任意兩個(gè)結(jié)點(diǎn)之間都是相互可達(dá)的，則稱該有向圖G是一個(gè)強(qiáng)連通圖 ； 設(shè)G是一個(gè)有向圖，若G中任意兩個(gè)結(jié)點(diǎn)之間至少單方向可達(dá)的，則稱該有向圖G是一個(gè)單側(cè)連通圖； 設(shè)G是一個(gè)有向圖，若略去G中所有有向邊的方向后所得到的無向圖G1是

17、一個(gè)無向連通圖，則稱該有向圖G是一個(gè)弱連通圖。,定義,離散數(shù)學(xué),37,,例：,例：,離散數(shù)學(xué),38,定理,定理 一個(gè)有向圖G是強(qiáng)連通圖當(dāng)且僅當(dāng)G中有一個(gè)回 路，它至少包含每一個(gè)結(jié)點(diǎn)一次。,證明：“”如G中有一個(gè)回路，它至少包含每個(gè)結(jié)點(diǎn)，則G中任何兩個(gè)結(jié)點(diǎn)間都是相互可達(dá)的，故G為強(qiáng)連通圖。 “”如G是強(qiáng)連通圖，則任意兩個(gè)結(jié)點(diǎn)之間都是相互可達(dá)的，設(shè)G，Vv1,v,v,,v，則v1到v2可達(dá)，v2到v3可達(dá)，v3到v4可達(dá)，，v-到v可達(dá)，vn到v1可達(dá)，由此可得到一條回路(v1，v，v，，v，v1)，它至少包含每個(gè)結(jié)點(diǎn)一次。,離散數(shù)學(xué),39,定義,定義 設(shè)G是一個(gè)有向圖，G1是G的導(dǎo)出子圖，若G1

18、是弱連通圖(單側(cè)連通圖，強(qiáng)連通圖)，且沒有包含G1的更大的子圖是弱連通圖(單側(cè)連通圖，強(qiáng)連通圖)，則稱G1是極大弱連通子圖(極大單側(cè)連通子圖，極大強(qiáng)連通子圖)或稱為弱分圖(單側(cè)分圖，強(qiáng)分圖)。,離散數(shù)學(xué),40,例：如上圖(a)所示，有：,例：,由v、v、v1,v,v,v,v所導(dǎo)出的子圖構(gòu)成了該圖的強(qiáng)分圖； 由v1,v,v,v,v,v7、v1,v,v,v5,v,v所導(dǎo)出的子圖構(gòu)成了該圖的單側(cè)分圖； (a)圖本身就是一個(gè)弱分圖。,離散數(shù)學(xué),41,例：,如上圖(b)所示，有：,由v1、v、v3、v4、v5,v6,v所導(dǎo)出的子圖構(gòu)成了該圖的強(qiáng)分圖； 由v1,v,v、v1,v3,v4、v,v,v所導(dǎo)出的

19、子圖構(gòu)成了該圖的單側(cè)分圖； 由v1,v,v,v、v,v,v所導(dǎo)出的子圖構(gòu)成了該圖的弱分圖。,離散數(shù)學(xué),42,定理 在有向圖G，它的每一個(gè)結(jié)點(diǎn)必然位于且僅位于一個(gè)強(qiáng)分圖中； 在有向圖G，它的每一個(gè)結(jié)點(diǎn)和每一條邊都至少位于一個(gè)單向分圖中； 在有向圖G，它的每一個(gè)結(jié)點(diǎn)和每一條邊必然位于且僅位于一個(gè)弱分圖中。,定理,離散數(shù)學(xué),43,證：(僅以1)為例加以說明),證：,. 對vV，令S是G中所有與v相互可達(dá)的結(jié)點(diǎn)集，則有vS，由于v與S中的一切結(jié)點(diǎn)相互可達(dá)，所以，由可達(dá)性具有傳遞性知：S中的一切結(jié)點(diǎn)之間是相互可達(dá)的，即S是G的一個(gè)強(qiáng)分圖，所以，v位于一個(gè)強(qiáng)分圖中； . 設(shè)v還位于另一個(gè)強(qiáng)分圖T中，則由S

20、中的每個(gè)結(jié)點(diǎn)都與v相互可達(dá)，且T中的每個(gè)結(jié)點(diǎn)也都與v相互可達(dá)，所以，由可達(dá)性具有傳遞性知：S中的一切結(jié)點(diǎn)與T中的一切結(jié)點(diǎn)之間是相互可達(dá)的，即由ST就構(gòu)成了一個(gè)更大的強(qiáng)連通的子圖，這就與S、T都是兩個(gè)強(qiáng)分圖矛盾，故G的每個(gè)結(jié)點(diǎn)僅位于一個(gè)強(qiáng)分圖中。,離散數(shù)學(xué),44,例：,在圖(a)中，結(jié)點(diǎn)v1，v2，v3，v4僅位于強(qiáng)分圖 v1，v2，v3，v4中，結(jié)點(diǎn)v5僅位于強(qiáng)分圖 v5 中，但邊、都不位于強(qiáng)分圖中； 結(jié)點(diǎn)v1，v2，v3，v4，v5僅位于單向分圖 v1，v2，v3，v4，v5，所有的邊也都僅位于單向分圖中； 結(jié)點(diǎn)v1，v2，v3，v4，v5僅位于弱分圖 v1，v2，v3，v4，v5；所有的邊

21、也都僅位于弱分圖中。 在圖(b)中，結(jié)點(diǎn)v2，v3和邊同時(shí)位于兩個(gè)單向分圖 v1，v2，v3和v2，v3，v4中。,例：,離散數(shù)學(xué),45,7-3 圖的矩陣表示,一、鄰接矩陣,設(shè)G是一個(gè)簡單圖，Vv1,v2,,vn，Ee1,e2,,en，則n階方陣A(G)(aij)nn稱為G的鄰接矩陣。其中：,由鄰接矩陣的定義知：其矩陣的元素是一個(gè)二值元素，所以，又稱該矩陣為位矩陣或布爾矩陣。,離散數(shù)學(xué),46,例：,鄰接矩陣：,例：,離散數(shù)學(xué),47,性質(zhì),設(shè)G是一個(gè)簡單圖，則有：,如aij1,則表示什么？(i,j1,2,3,,n) 如對i,j1,2,3,,n,都有aij0，則表示什么？ 如對i,j1,2,3,,

22、n,都有aij1(ij), aii0，則表示什么？ 如G是一個(gè)無向簡單圖,則對任意viV，都有：,離散數(shù)學(xué),48,性質(zhì),如G是一個(gè)有向簡單圖，則對任意viV，都有：,離散數(shù)學(xué),49,性質(zhì),令B(bij)AAA(aij(2))nn，則有：,此時(shí)，bij表示從vi到vj長度為2的路數(shù)目，如bij0，則無長度為2的路，而bii給出了經(jīng)過vi的長度為2的回路數(shù)目；,令C(cij)AmAAA(aij(m))nn，則有：,此時(shí)，cij表示從vi到vj長度為m的數(shù)目，如cij0，則無長度為m的路，而cii給出了經(jīng)過vi的長度為m的回路數(shù)目。,離散數(shù)學(xué),50,定理,定理 設(shè)A(G)為圖G的鄰接矩陣，則(A(G

23、))l中的i行j列元素等于G中聯(lián)結(jié)vi與vj的長度為l的路的數(shù)目。 證明 對l施歸納法 當(dāng)l =2時(shí)，由上得知是顯然成立。 設(shè)命題對l = t成立，由 故 根據(jù)鄰接矩陣的定義aik表示聯(lián)結(jié)vi與vk長度為1的路的數(shù)目，而是聯(lián)結(jié)vk與vj長度為t的路的數(shù)目，上式的每一項(xiàng)表示由vi經(jīng)過一條邊到vk，再由vk經(jīng)過長度為l的路到vj的，總長度為t+1的路的數(shù)目。對所有的k求和，即是所有從vi到v的長度為t+1的路的數(shù)目，故命題對成立。,,,離散數(shù)學(xué),51,性質(zhì),如下圖，Vv1,v2,v3,v4,v5，其鄰接矩陣A、A、A、A4,如下：,上面圖中結(jié)點(diǎn)的度數(shù)和兩結(jié)點(diǎn)間長度為k的路的條數(shù)。,離散數(shù)學(xué),52,

24、定理,例:給定一圖G=V，E如圖所示。 求v1與v2之間長度為3的路數(shù)，結(jié)點(diǎn)v1與v3之間長度為2的路數(shù)，在結(jié)點(diǎn)v2之間長度為4的回路數(shù)？,,,離散數(shù)學(xué),53,二、可達(dá)性矩陣,二、可達(dá)性矩陣,(i，j1，2，3，，n) 則稱矩陣P為圖G的可達(dá)性矩陣。,定義 設(shè)G(n，m)是一個(gè)簡單圖，Vv1,v2,v3,,vn，定義一個(gè)n階方陣P(pij)n*n，其中：,離散數(shù)學(xué),54,二、可達(dá)性矩陣,可達(dá)性矩陣的求法有兩種： 1) 計(jì)算矩陣 Bn=A+A2+A3+ 令中不為零的元素等于1，為零的元素不變，得到P。 見例題1。 Bn=A+A2+A3++An,離散數(shù)學(xué),55,例 ：,例 ：求如下圖所示的圖形

25、的可達(dá)性矩陣。,離散數(shù)學(xué),56,利用布爾求乘和布爾求和的運(yùn)算直接求可達(dá)性矩陣,PAA(2)A(3)...A(n) A(m)AAA...A(m1,2,3,n) 若把鄰接矩陣看作是結(jié)點(diǎn)集V上關(guān)系R的關(guān)系矩陣，則可達(dá)性矩陣P即為MR， 因此可達(dá)性矩陣可以用Warshall算法計(jì)算,2) 利用布爾求乘和布爾求和的運(yùn)算直接求可達(dá)性矩陣,離散數(shù)學(xué),57,例：,例：利用鄰接矩陣的布爾運(yùn)算求可達(dá)性矩陣。,離散數(shù)學(xué),58,三：完全關(guān)聯(lián)矩陣,三：完全關(guān)聯(lián)矩陣 定義 給定無向圖G，令v1,v2,,vp和e1,e2,,eq分別記為G的結(jié)點(diǎn)和邊，則矩陣M(G)=(mij)，其中 稱M(G)為完全關(guān)聯(lián)矩陣。,,離

26、散數(shù)學(xué),59,例：,例：如對于圖，可寫完全關(guān)聯(lián)矩陣：,,離散數(shù)學(xué),60,性質(zhì),從關(guān)聯(lián)矩陣中可以看出圖形的一些性質(zhì)： 圖中每一邊關(guān)聯(lián)兩個(gè)結(jié)點(diǎn)，故M(G)的每一列 。 每一行元素的和數(shù)對應(yīng)于 。 一行中的元素全為0，其對應(yīng)的結(jié)點(diǎn)為 。 兩個(gè)平行邊其對應(yīng)的兩列相同。 同一圖當(dāng)結(jié)點(diǎn)或邊的編序不同，其對應(yīng)M(G)僅有行序、列序的差別。,,離散數(shù)學(xué),61,定義,定義 給定簡單有向圖 G=V，E，V=v1,v2,vp，E=e1,e2,eq，pq階矩陣M(G)=(mij)，其中 稱M(G)為G的完全關(guān)聯(lián)矩陣。,,,離散數(shù)學(xué),62,性質(zhì),從關(guān)聯(lián)矩陣中可以看出圖形的一些性質(zhì)： (1)M(G)的每一列

27、 。 每一行元素”1”的個(gè)數(shù)對應(yīng)于 ，”-1”的個(gè)數(shù)對應(yīng)于 。 一行中的元素全為0，其對應(yīng)的結(jié)點(diǎn)為 。,離散數(shù)學(xué),63,例：,例：如對于圖，可寫完全關(guān)聯(lián)矩陣：,,離散數(shù)學(xué),64,邊的合并,對圖G的完全關(guān)聯(lián)矩陣中的兩個(gè)行相加定義如下： 若記vi對應(yīng)的行為 ，將第i行與第j行相加，規(guī)定 為：對有向圖是指對應(yīng)分量的加法運(yùn)算，對無向圖是 指對應(yīng)分量的模2的加法運(yùn)算，把這種運(yùn)算記作,,離散數(shù)學(xué),65,邊的合并--關(guān)聯(lián)矩陣的加法運(yùn)算,例：圖 (a)中使v4和v5合并得到圖 (b)。,,離散數(shù)學(xué),66,邊的合并,設(shè)圖G的結(jié)點(diǎn)vi與結(jié)點(diǎn)vj合并得到圖G，那么M(G) 是將M(G)中的第i行與第j行相加而得到。

28、因?yàn)槿粲?關(guān)項(xiàng)中第r個(gè)對應(yīng)分量有 ，則說明vi與 vj兩者之中只有一個(gè)結(jié)點(diǎn)是邊er的端點(diǎn)，且將這兩 個(gè)結(jié)點(diǎn)合并后的結(jié)點(diǎn)vi,j仍是er的端點(diǎn)。 若 ，則有兩種情況： vi與vj都不是邊er的端點(diǎn)，那么vi,j也不是er的端點(diǎn)。 vi與vj都是邊er的端點(diǎn)，那么合并后在G中er成為vi,j的自回路，按規(guī)定應(yīng)該被刪去。 此外，在M(G)中若有某些列，其元素全為0，說明G 中的一些結(jié)點(diǎn)合并后，消失了一些對應(yīng)邊,離散數(shù)學(xué),67,定理,定理 如果一個(gè)連通圖G有r個(gè)結(jié)點(diǎn)，則其完全關(guān)聯(lián)矩陣M(G)的秩為r-1，即rankM(G)=r-1。 證明 這里對無向圖進(jìn)行證明。 由于矩陣M(G)的每一列恰有

29、兩個(gè)1，若把M(G)的其它所有行加到最后一行上(模2加法)，得到矩陣，它的最后一行全為0，因?yàn)榈闹扰cM(G)的秩相同，故M(G)的秩小于行數(shù)，即rankM(G)r-1。 設(shè)M(G)的第一列對應(yīng)邊e，且e的端點(diǎn)為vi和vj，調(diào)整行序使第i行為第一行，這時(shí)M(G)的首列僅在第1行和第j行為1，其余各元素均為0，再把第一行加到第j行上去則得到矩陣M(G)。其中M(G1)是M(G)刪去第一行和第一列所得到的矩陣。,,離散數(shù)學(xué),68,證明,,離散數(shù)學(xué),69,證明（續(xù)）,證明 由于M(G1)是G1的完全關(guān)聯(lián)矩陣，而G1是由G的兩個(gè)結(jié)點(diǎn)vi和vj合并而得到。由于G是連通的，故G1必為連通圖，M(G1)也具有

30、連通圖完全關(guān)聯(lián)矩陣的所有性質(zhì)，故M(G1)沒有全零的行。如果M(G1)的第一列全為零，則可將M(G1)的非零列與第一列對調(diào)，不影響完全關(guān)聯(lián)矩陣的秩數(shù)。因此我們必可以通過調(diào)整行序和把一行加到另一行上這兩種運(yùn)算，使M(G1)的第一列首項(xiàng)元素為1，得到,,離散數(shù)學(xué),70,證明（續(xù)）,證明 繼續(xù)上述兩種運(yùn)算，并不改變矩陣的秩，經(jīng)過r-1次，最后將M(G)變換成如下矩陣。 顯然M(r-1)(G)有一個(gè)(r-1)階子陣，其行列式的值不為0，故M(r-1)(G)的秩至少為r-1。 由和可知 rankM(G)=r-1 對于有向圖的關(guān)聯(lián)矩陣可以仿此證明。,,離散數(shù)學(xué),71,矩陣與圖的連通性,矩陣與圖的連通性 無向線圖G是連通圖當(dāng)且僅當(dāng)它的可達(dá)性矩陣P的所有元素都 均為1； 有向線圖G是強(qiáng)連通圖當(dāng)且僅當(dāng)它的可達(dá)性矩陣P的所有元素 都均為1； 有向線圖G是單側(cè)連通圖當(dāng)且僅當(dāng)它的可達(dá)性矩陣P及其轉(zhuǎn)置 矩陣PT經(jīng)“布爾求和”運(yùn)算后所得矩陣P1PPT中除對角線以 外的其余元素均為1； 有向線圖G是弱連通圖當(dāng)且僅當(dāng)它的鄰接矩陣A及其轉(zhuǎn)置矩陣 AT經(jīng)“布爾求和”運(yùn)算后作為新的鄰接矩陣BAAT而求出的可 達(dá)性矩陣PB中所有元素均為1。,