《《離散數學》PPT課件》由會員分享，可在線閱讀，更多相關《《離散數學》PPT課件（71頁珍藏版）》請在裝配圖網上搜索。
1、離散數學,1,一、圖 定義一個圖是一個三元組,簡記為G。,7-1 圖的基本概念,其中： Vv1,v2,v3,,vn是一個非空集合,vi(i1,2,3,,n)稱為結點,簡稱點,V為結點集； Ee1,e2,e3,,em是一個有限的集合，ei(i1,2,3,,m)稱為邊,E為邊集，E中的每個元素都有V中的結點對（有序偶或無序偶）與之對應。 例,離散數學,2,圖的術語,圖的術語 若邊e與結點無序偶(u，v)相對應，則稱邊e為無向邊,記為e(u，v)，這時稱u，v是邊e的兩個端點； 若邊e與結點有偶相對應，則稱邊e為有向邊(或弧)，記為e，這時稱u是邊e的始點(或弧尾).v是邊e的終點(或弧頭)，統(tǒng)稱為
2、e的端點； 在一個圖中，關聯結點vi和vj的邊e，無論是有向的還是無向的，均稱邊e與結點vI和vj相關聯，而vi和vj稱為鄰接點，否則稱為不鄰接的；,離散數學,3,續(xù)：,續(xù)： 關聯于同一個結點的兩條邊稱為鄰接邊； 圖中關聯同一個結點的邊稱為自回路(或環(huán))； 圖中不與任何結點相鄰接的結點稱為孤立結點； 僅由孤立結點組成的圖稱為零圖； 僅含一個結點的零圖稱為平凡圖； 含有n個結點、m條邊的圖稱為(n，m)圖；,離散數學,4,續(xù)：,續(xù)： 每條邊都是無向邊的圖稱為無向圖； 每條邊都是有向邊的圖稱為有向圖； 有些邊是無向邊，而另一些是有向邊的圖稱為混合圖。 在有向圖中，兩個結點間(包括結點自身間)若有同
3、始點和同終點的幾條邊，則這幾條邊稱為平行邊，在無向圖中，兩個結點間(包括結點自身間)若有幾條邊，則這幾條邊稱為平行邊，兩結點vi，vj間相互平行的邊的條數稱為邊(vi，vj)或的重數； 含有平行邊的圖稱為多重圖。非多重圖稱為線圖；無自回路的線圖稱為簡單圖。,離散數學,5,(a),例：,(b),(c),(d),例：,離散數學,6,(e),(f),例：,例：,(g),離散數學,7,二、度數 定義 在無向圖G中，與結點v(vV)關聯的邊的條數，稱為該結點的度數，記為deg(v)；,二、度數,定義 在有向圖G中，以結點v(vV)為始點引出的邊的條數，稱為該結點的引出度數,簡稱出度,記為deg+(v)；
4、以結點v(vV)為終點引入的邊的條數，稱為該結點的引入度數，簡稱入度,記為deg-(v)；而結點的出度和入度之和稱為該結點的度數，記為deg(v)，即deg(v)deg+(v)+deg-(v)； (G)最小度，(G)最大度 定義 在圖G中，對任意結點vV，若度數deg(v)為奇數，則稱此結點為奇度數結點，若度數deg(v)為偶數，則稱此結點為偶度數結點。,離散數學,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；,例：,離散數學,9,定理,定理 1.在圖G中，則所有結點的度數的總和等于邊數的兩倍，即：,在有向圖G中，則所有結點的出度之和等于所有結點的入度之和，即： 3.定理 在所有圖中，度數為奇數的結點個數為偶數.,離散數學,10,定理,,。,證明設V1v|vV且deg(v)奇數，V2v|vV且deg(v)偶數。顯然，V1V2，且V1V2V，于是有：,由于上式中的2m和偶度數結點度數之和均為偶數，因而也為偶數。于是|V1|為偶數(因為V1中的結點v之deg(v)都為奇數)，即奇度數的結點個數為偶數。,離散數學,11,三、完全圖,三、
6、完全圖 定義 在圖G中，若所有結點的度數均有相同度數d，則稱此圖為d次正則圖。 定義 一個(n，m)(n2)的簡單無向圖，若它為n-1次正則圖，則稱該(n，m)圖為無向簡單完全圖，簡稱完全圖,記為Kn。 有向完全圖 定理 設無向完全圖G有n個頂點，則G有 條邊。,離散數學,12,四、子圖和補圖 定義 設有圖G和圖G1，若G和G1滿足： 若V1V，E1E，則稱G1是G的子圖，記為G1G； 若G1G，且G1G(即V1V或E1E)，則稱G1是G的真子圖，記為G1G； 定義 若V1V，E1E，則稱G1是G的生成子圖，記為G1G； 定義設有圖G和圖G2，若V2V，V2，以V2為結點集，以兩個端點均在V2
7、中的邊的全體為邊集的G的子圖稱為V2導出的子圖，簡稱G的導出子圖。,四、子圖和補圖,離散數學,13,例：,例：,它的真子圖G和生成子圖G。,離散數學,14,四、子圖和補圖 定義 設G為具有n個結點的簡單圖,從完全圖Kn中刪去G中的所有的邊而得到的圖稱為G的補圖(或G的補)，記為 。關于完全圖的子圖的補圖稱為此子圖的絕對補圖。 定義 是圖，是的子圖，”，” 是”中邊所關聯的所有頂點集合，則”稱為關于的相對補圖。,四、子圖和補圖,離散數學,15,例：,例：求下圖的補圖。,離散數學,16,五、圖的同構,五、圖的同構 例:如下圖 (a)、(b)、(c)、(d)所示。,圖(a)、圖(b)、圖(c)和圖(
8、d)所表示的圖形實際上都是一樣的,離散數學,17,定義,定義 設有圖G和圖G1,如果存在雙射函數g:VV1,且e(vi,vj)(或)是G的一條邊當且僅當e1(g(vi),g(vj)) (或) 是G1的一條邊則稱G和G1同構，記為GG1。 同構的充要條件：兩個圖的結點和邊分別存在一一對應，且保持關聯關系。,離散數學,18,例：,例：如圖(a)、(b)所示的兩個圖G和G1，GG1？,解：顯然，定義函數g：VV1，滿足g(vi)vi（i1，2，3，4，5），可以驗證g一定是一個滿足定義的雙射，所以GG1。,離散數學,19,必要條件,兩個圖同構的必要條件： 結點數目相同； 邊數相同； 度數相同的結點數
9、相同。,注意：這三個條件并不是充分條件。例如下面兩個圖滿足這三個條件，但它們不同構。,離散數學,20,7-2 路與回路,一、路,定義 給定圖G=V,E,設v0，v1，，vnV,e1，e2，，enE,其中ei是關聯結點vi-1,vi的邊,交替序列v0e1v1e2envn稱為聯結v0到vn的路。 v0,vn分別為該路的起點和終點，統(tǒng)稱為路的端點。 路中邊的條數稱為該路的長度。 此時，若v0vn，則該路稱為回路。,離散數學,21,若路中所有邊全不相同，則稱此路為一條跡； 若路中所有結點全不相同，則稱此路為通路。 若回路中除v0vn以外所有結點全不相同，則稱此圈。（閉的通路） 在簡單圖中一條路v0e1
10、v1e2envn ，由它的結點序列v0v1 vn確定,所以簡單圖的路,由可由其結點序列v0v1 vn表示。在有向圖中,結點數大于1的一條路可由邊序列e1e2 en 表示。,續(xù)：,離散數學,22,例：考慮如下路：,例：,離散數學,23,定理,定理在一個具有n個結點的圖中，如果從結點vj到結點vk存在一條路，則從結點vj到結點vk必存在一條不多于n-1條邊的路。,推論在無向圖G中，如果從結點vj到結點vk存在一條路，則必存在一條從vj到vk而長度小于n的通路。,離散數學,24,二、無向圖的連通性,二、無向圖的連通性 定義 設G是一個圖，對vi，vjV，從vi到vj如存在一條路，則稱結點vi和vj是
11、連通的。 定義 設G是一個無向圖，該無向圖G中的每個連通的劃分塊稱為G的一個連通分支，用W(G)表示G中的連通分支數。 定義 設G是一個無向圖，若G中任意兩個結點之間都是連通的，即圖G只有一個連通分支，則稱該無向圖G是一個無向連通圖，否則，則稱G是一個非連通圖(或分離圖)。,離散數學,25,G1是連通圖，W(G1)1； G2是非連通圖，且W(G2)4。,例：,例：,離散數學,26,定義設無向圖G=V,E為連通的，若有結點集V1是V的真子集，使得圖G刪除了V1所有結點后，所得的子圖是不連通的，而刪除了V1的任意真子集后，所得的子圖仍然是連通圖。則稱集合V1為圖G的點割集。若某一結點就構成點割集，
12、則稱該結點為割點。 這樣，一個連通圖，刪除它的一個點割集后，將分成兩個或多于兩個連通分支。,割點,離散數學,27,割點,若G不是完全圖，我們定義k(G)=min| V1 | |V1 是G的點割集為G的點連通度(或連通度)。 連通度k(G)是為了產生一個不連通圖需要刪去的 點的最少數目。 一個不連通圖的連通度等于 存在著割點的連通圖的點連通度 完全圖Kp的點連通度,離散數學,28,定義 設無向圖G=V,E為連通的，若有邊集E1是E的真子集，使得圖G刪除了E1所有邊后，所得的子圖是不連通的，而刪除了E1的任意真子集后，所得的子圖仍然是連通圖。則稱集合E1為圖G的邊割集。若某一邊構成邊割集，則稱該邊
13、為割邊(或橋)。 G的割邊也就是G中的一條邊e使得W(G-e)W(G)。 例,割邊,離散數學,29,割邊,與點連通度相似，我們定義非平凡圖G的邊連通 度為：(G)=min| E1 ||E1是G的邊割集，邊連 通度(G)是為了產生一個不連通需要刪去邊的 最少數目。 平凡圖(G ) 一個不連通圖(G),離散數學,30,定理 對于任何一個圖G =V,E，有 k(G)(G)(G) 證明 若G不連通，則k(G)=(G)=0，故上式成立。 若G連通， 證明(G)(G)。若G是平凡圖，則(G)=0(G)，若G是非平凡圖，則因每一結點的所有關連邊必含一個邊割集，故(G)(G)。,定理,離散數學,31,再證k(
14、G)(G) .設(G)=1，即G有一割邊，顯然此時k(G)=1，上式成立。 .設(G)2，則必可刪去某(G)條邊，使G不連通，而刪除(G)-1條邊，它仍然連通，而且有一條橋e=(u，v)。對(G)-1條邊中每一條邊都選取一個不同于u，v的端點，將這些端點刪去必至少刪去(G)-1條邊。若這樣產生的圖是不連通的，則k(G)(G)-1(G)，若這樣產生的圖是連通的，則e=(u，v)仍然是橋，此時再刪去u，v，就必產生一個不連通圖，故k(G)(G)。 由此得k(G)(G)(G)。,續(xù)：,離散數學,32,定理 一個連通無向圖G =V,E的某一點v是圖G的割點，當且僅當存在兩個節(jié)點u和w，使得節(jié)點u和w的
15、每一條路都通過v。,定理,離散數學,33,三、有向圖的連通性,三、有向圖的連通性 定義 設G是一個有向圖，對vi，vjV，從vi到vj如存在一條路，則稱結點vi到vj是可達的。,在有向圖中，如從vi到vj可達，但從vj到vi則不一定是可達的。,為此，若將可達性看成是圖G的結點集合V上的二元關系的話，對有向圖來說，該可達性關系滿足什么性質？,離散數學,34,定義,定義 在圖G中，對vi，vjV，如果從vi到vj存在路，則稱長度最短的路為從vi到vj的短程線,從vi到vj的短程線的長度稱為從vi到vj的距離，記為d(vi,vj)。 d(vi，vj)滿足下列性質： d(vi，vj)0； d(vi，v
16、i)0； d(vi，vk)+d(vk，vj) d(vi，vj)； d(vi，vj)(當vi到vj不可達)。 此外，有關距離的概念對無向圖也適用。,離散數學,35,在(a)中有： d(v2，v1)d(v1，v2) d(v3，v1)d(v1，v3) 在(b)中有： d(v1，v3)，d(v3，v7)，d(v1，v7)。,例：,例：,離散數學,36,定義 設G是一個有向圖，若G中任意兩個結點之間都是相互可達的，則稱該有向圖G是一個強連通圖 ； 設G是一個有向圖，若G中任意兩個結點之間至少單方向可達的，則稱該有向圖G是一個單側連通圖； 設G是一個有向圖，若略去G中所有有向邊的方向后所得到的無向圖G1是
17、一個無向連通圖，則稱該有向圖G是一個弱連通圖。,定義,離散數學,37,,例：,例：,離散數學,38,定理,定理 一個有向圖G是強連通圖當且僅當G中有一個回 路，它至少包含每一個結點一次。,證明：“”如G中有一個回路，它至少包含每個結點，則G中任何兩個結點間都是相互可達的，故G為強連通圖。 “”如G是強連通圖，則任意兩個結點之間都是相互可達的，設G，Vv1,v,v,,v，則v1到v2可達，v2到v3可達，v3到v4可達，，v-到v可達，vn到v1可達，由此可得到一條回路(v1，v，v，，v，v1)，它至少包含每個結點一次。,離散數學,39,定義,定義 設G是一個有向圖，G1是G的導出子圖，若G1
18、是弱連通圖(單側連通圖，強連通圖)，且沒有包含G1的更大的子圖是弱連通圖(單側連通圖，強連通圖)，則稱G1是極大弱連通子圖(極大單側連通子圖，極大強連通子圖)或稱為弱分圖(單側分圖，強分圖)。,離散數學,40,例：如上圖(a)所示，有：,例：,由v、v、v1,v,v,v,v所導出的子圖構成了該圖的強分圖； 由v1,v,v,v,v,v7、v1,v,v,v5,v,v所導出的子圖構成了該圖的單側分圖； (a)圖本身就是一個弱分圖。,離散數學,41,例：,如上圖(b)所示，有：,由v1、v、v3、v4、v5,v6,v所導出的子圖構成了該圖的強分圖； 由v1,v,v、v1,v3,v4、v,v,v所導出的
19、子圖構成了該圖的單側分圖； 由v1,v,v,v、v,v,v所導出的子圖構成了該圖的弱分圖。,離散數學,42,定理 在有向圖G，它的每一個結點必然位于且僅位于一個強分圖中； 在有向圖G，它的每一個結點和每一條邊都至少位于一個單向分圖中； 在有向圖G，它的每一個結點和每一條邊必然位于且僅位于一個弱分圖中。,定理,離散數學,43,證：(僅以1)為例加以說明),證：,. 對vV，令S是G中所有與v相互可達的結點集，則有vS，由于v與S中的一切結點相互可達，所以，由可達性具有傳遞性知：S中的一切結點之間是相互可達的，即S是G的一個強分圖，所以，v位于一個強分圖中； . 設v還位于另一個強分圖T中，則由S
20、中的每個結點都與v相互可達，且T中的每個結點也都與v相互可達，所以，由可達性具有傳遞性知：S中的一切結點與T中的一切結點之間是相互可達的，即由ST就構成了一個更大的強連通的子圖，這就與S、T都是兩個強分圖矛盾，故G的每個結點僅位于一個強分圖中。,離散數學,44,例：,在圖(a)中，結點v1，v2，v3，v4僅位于強分圖 v1，v2，v3，v4中，結點v5僅位于強分圖 v5 中，但邊、都不位于強分圖中； 結點v1，v2，v3，v4，v5僅位于單向分圖 v1，v2，v3，v4，v5，所有的邊也都僅位于單向分圖中； 結點v1，v2，v3，v4，v5僅位于弱分圖 v1，v2，v3，v4，v5；所有的邊
21、也都僅位于弱分圖中。 在圖(b)中，結點v2，v3和邊同時位于兩個單向分圖 v1，v2，v3和v2，v3，v4中。,例：,離散數學,45,7-3 圖的矩陣表示,一、鄰接矩陣,設G是一個簡單圖，Vv1,v2,,vn，Ee1,e2,,en，則n階方陣A(G)(aij)nn稱為G的鄰接矩陣。其中：,由鄰接矩陣的定義知：其矩陣的元素是一個二值元素，所以，又稱該矩陣為位矩陣或布爾矩陣。,離散數學,46,例：,鄰接矩陣：,例：,離散數學,47,性質,設G是一個簡單圖，則有：,如aij1,則表示什么？(i,j1,2,3,,n) 如對i,j1,2,3,,n,都有aij0，則表示什么？ 如對i,j1,2,3,,
22、n,都有aij1(ij), aii0，則表示什么？ 如G是一個無向簡單圖,則對任意viV，都有：,離散數學,48,性質,如G是一個有向簡單圖，則對任意viV，都有：,離散數學,49,性質,令B(bij)AAA(aij(2))nn，則有：,此時，bij表示從vi到vj長度為2的路數目，如bij0，則無長度為2的路，而bii給出了經過vi的長度為2的回路數目；,令C(cij)AmAAA(aij(m))nn，則有：,此時，cij表示從vi到vj長度為m的數目，如cij0，則無長度為m的路，而cii給出了經過vi的長度為m的回路數目。,離散數學,50,定理,定理 設A(G)為圖G的鄰接矩陣，則(A(G
23、))l中的i行j列元素等于G中聯結vi與vj的長度為l的路的數目。 證明 對l施歸納法 當l =2時，由上得知是顯然成立。 設命題對l = t成立，由 故 根據鄰接矩陣的定義aik表示聯結vi與vk長度為1的路的數目，而是聯結vk與vj長度為t的路的數目，上式的每一項表示由vi經過一條邊到vk，再由vk經過長度為l的路到vj的，總長度為t+1的路的數目。對所有的k求和，即是所有從vi到v的長度為t+1的路的數目，故命題對成立。,,,離散數學,51,性質,如下圖，Vv1,v2,v3,v4,v5，其鄰接矩陣A、A、A、A4,如下：,上面圖中結點的度數和兩結點間長度為k的路的條數。,離散數學,52,
24、定理,例:給定一圖G=V，E如圖所示。 求v1與v2之間長度為3的路數，結點v1與v3之間長度為2的路數，在結點v2之間長度為4的回路數？,,,離散數學,53,二、可達性矩陣,二、可達性矩陣,(i，j1，2，3，，n) 則稱矩陣P為圖G的可達性矩陣。,定義 設G(n，m)是一個簡單圖，Vv1,v2,v3,,vn，定義一個n階方陣P(pij)n*n，其中：,離散數學,54,二、可達性矩陣,可達性矩陣的求法有兩種： 1) 計算矩陣 Bn=A+A2+A3+ 令中不為零的元素等于1，為零的元素不變，得到P。 見例題1。 Bn=A+A2+A3++An,離散數學,55,例 ：,例 ：求如下圖所示的圖形
25、的可達性矩陣。,離散數學,56,利用布爾求乘和布爾求和的運算直接求可達性矩陣,PAA(2)A(3)...A(n) A(m)AAA...A(m1,2,3,n) 若把鄰接矩陣看作是結點集V上關系R的關系矩陣，則可達性矩陣P即為MR， 因此可達性矩陣可以用Warshall算法計算,2) 利用布爾求乘和布爾求和的運算直接求可達性矩陣,離散數學,57,例：,例：利用鄰接矩陣的布爾運算求可達性矩陣。,離散數學,58,三：完全關聯矩陣,三：完全關聯矩陣 定義 給定無向圖G，令v1,v2,,vp和e1,e2,,eq分別記為G的結點和邊，則矩陣M(G)=(mij)，其中 稱M(G)為完全關聯矩陣。,,離
26、散數學,59,例：,例：如對于圖，可寫完全關聯矩陣：,,離散數學,60,性質,從關聯矩陣中可以看出圖形的一些性質： 圖中每一邊關聯兩個結點，故M(G)的每一列 。 每一行元素的和數對應于 。 一行中的元素全為0，其對應的結點為 。 兩個平行邊其對應的兩列相同。 同一圖當結點或邊的編序不同，其對應M(G)僅有行序、列序的差別。,,離散數學,61,定義,定義 給定簡單有向圖 G=V，E，V=v1,v2,vp，E=e1,e2,eq，pq階矩陣M(G)=(mij)，其中 稱M(G)為G的完全關聯矩陣。,,,離散數學,62,性質,從關聯矩陣中可以看出圖形的一些性質： (1)M(G)的每一列
27、 。 每一行元素”1”的個數對應于 ，”-1”的個數對應于 。 一行中的元素全為0，其對應的結點為 。,離散數學,63,例：,例：如對于圖，可寫完全關聯矩陣：,,離散數學,64,邊的合并,對圖G的完全關聯矩陣中的兩個行相加定義如下： 若記vi對應的行為 ，將第i行與第j行相加，規(guī)定 為：對有向圖是指對應分量的加法運算，對無向圖是 指對應分量的模2的加法運算，把這種運算記作,,離散數學,65,邊的合并--關聯矩陣的加法運算,例：圖 (a)中使v4和v5合并得到圖 (b)。,,離散數學,66,邊的合并,設圖G的結點vi與結點vj合并得到圖G，那么M(G) 是將M(G)中的第i行與第j行相加而得到。
28、因為若有 關項中第r個對應分量有 ，則說明vi與 vj兩者之中只有一個結點是邊er的端點，且將這兩 個結點合并后的結點vi,j仍是er的端點。 若 ，則有兩種情況： vi與vj都不是邊er的端點，那么vi,j也不是er的端點。 vi與vj都是邊er的端點，那么合并后在G中er成為vi,j的自回路，按規(guī)定應該被刪去。 此外，在M(G)中若有某些列，其元素全為0，說明G 中的一些結點合并后，消失了一些對應邊,離散數學,67,定理,定理 如果一個連通圖G有r個結點，則其完全關聯矩陣M(G)的秩為r-1，即rankM(G)=r-1。 證明 這里對無向圖進行證明。 由于矩陣M(G)的每一列恰有
29、兩個1，若把M(G)的其它所有行加到最后一行上(模2加法)，得到矩陣，它的最后一行全為0，因為的秩與M(G)的秩相同，故M(G)的秩小于行數，即rankM(G)r-1。 設M(G)的第一列對應邊e，且e的端點為vi和vj，調整行序使第i行為第一行，這時M(G)的首列僅在第1行和第j行為1，其余各元素均為0，再把第一行加到第j行上去則得到矩陣M(G)。其中M(G1)是M(G)刪去第一行和第一列所得到的矩陣。,,離散數學,68,證明,,離散數學,69,證明（續(xù)）,證明 由于M(G1)是G1的完全關聯矩陣，而G1是由G的兩個結點vi和vj合并而得到。由于G是連通的，故G1必為連通圖，M(G1)也具有
30、連通圖完全關聯矩陣的所有性質，故M(G1)沒有全零的行。如果M(G1)的第一列全為零，則可將M(G1)的非零列與第一列對調，不影響完全關聯矩陣的秩數。因此我們必可以通過調整行序和把一行加到另一行上這兩種運算，使M(G1)的第一列首項元素為1，得到,,離散數學,70,證明（續(xù)）,證明 繼續(xù)上述兩種運算，并不改變矩陣的秩，經過r-1次，最后將M(G)變換成如下矩陣。 顯然M(r-1)(G)有一個(r-1)階子陣，其行列式的值不為0，故M(r-1)(G)的秩至少為r-1。 由和可知 rankM(G)=r-1 對于有向圖的關聯矩陣可以仿此證明。,,離散數學,71,矩陣與圖的連通性,矩陣與圖的連通性 無向線圖G是連通圖當且僅當它的可達性矩陣P的所有元素都 均為1； 有向線圖G是強連通圖當且僅當它的可達性矩陣P的所有元素 都均為1； 有向線圖G是單側連通圖當且僅當它的可達性矩陣P及其轉置 矩陣PT經“布爾求和”運算后所得矩陣P1PPT中除對角線以 外的其余元素均為1； 有向線圖G是弱連通圖當且僅當它的鄰接矩陣A及其轉置矩陣 AT經“布爾求和”運算后作為新的鄰接矩陣BAAT而求出的可 達性矩陣PB中所有元素均為1。,
《離散數學》PPT課件
