離散數(shù)學(xué)屈婉玲第九章

1,第三部分 圖論,本部分主要內(nèi)容 圖的基本概念 樹 歐拉圖與哈密頓圖 二部圖與匹配 平面圖 著色,2,第九章 圖的基本概念,主要內(nèi)容 圖 通路與回路 圖的連通性 圖的矩陣表示 預(yù)備知識 多重集合元素可以重復(fù)出現(xiàn)的集合 無序集AB=(x,y) | xAyB,14.1 圖,定義9.1 無向圖G = , 其中 (1) V為非空有窮集, 稱為頂點集，其元素稱為頂點 (2) E為VV 的多重有窮集, 稱為邊集, 其元素稱為無向邊, 簡稱邊 例 無向圖G = , 其中 V = v1, v2, v3, v4, v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5),4,有向圖,定義9.2 有向圖D=,其中 (1) V 為非空有窮集, 稱為頂點集，其元素稱為頂點 (2) E為VV 的多重有窮集, 稱為邊集, 其元素稱為有向邊, 簡稱邊 例 有向圖D=, 其中 V=a,b,c,d E=, , 注意：圖的集合表示與圖形表示之間的對應(yīng),5,相關(guān)概念,1. 無向圖和有向圖通稱圖. 記頂點集V(G), 邊集E(G). 2. 圖的階, n階圖. 3. n 階零圖Nn, 平凡圖N1. 4. 空圖. 5. 標(biāo)定圖與非標(biāo)定圖. 6. 有向圖的基圖. 7. 無向圖中頂點與邊的關(guān)聯(lián)及關(guān)聯(lián)次數(shù), 頂點與頂點、邊與 邊的相鄰關(guān)系. 8. 有向圖中頂點與邊的關(guān)聯(lián), 頂點與頂點、邊與邊的相鄰關(guān) 系. 9. 環(huán), 孤立點.,6,多重圖與簡單圖,定義9.3 無向圖中關(guān)聯(lián)同一對頂點的2條和2條以上的邊稱為 平行邊. 有向圖中2條和2條以上始點、終點相同的邊稱為平 行邊. 平行邊的條數(shù)稱為重數(shù). 含平行邊的圖稱為多重圖, 不含平行邊和環(huán)的圖稱為簡單圖. 定義9.4 設(shè)G=為無向圖, vV, 稱v作為邊的端點的次 數(shù)之和為v的度數(shù), 簡稱度, 記作d(v). 設(shè)D=為有向圖, vV, 稱v作為邊的始點的次數(shù)之和 為v的出度, 記作d+(v); 稱v作為邊的終點的次數(shù)之和為v的入 度, 記作d(v); 稱d+(v)+d(v)為v的度數(shù), 記作d(v).,7,頂點的度數(shù),設(shè)G=為無向圖, G的最大度(G)=maxd(v) | vV G的最小度 (G)=mind(v) | vV 設(shè)D=為無向圖, D的最大度(D)=maxd(v) | vV D的最小度 (D)=mind(v) | vV D的最大出度+(D)=maxd+(v) | vV D的最小出度 +(D)=mind+(v) | vV D的最大入度(D)=maxd(v) | vV D的最小入度 (D)=mind(v) | vV 懸掛頂點: 度數(shù)為1的頂點, 懸掛邊: 與懸掛頂點關(guān)聯(lián)的邊. 偶度(奇度)頂點: 度數(shù)為偶數(shù)(奇數(shù))的頂點,8,實例,d(v1)=4, d(v2)=4, d(v3)=2, d(v4)=1, d(v5)=3. =4, =1. v4是懸掛點, e7是懸掛邊.,d+(a)=4, d(a)=1, d(a)=5, d+(b)=0, d(b)=3, d(b)=3, d+(c)=2, d(c)=1, d(c)=3, d+(d)=1, d(d)=2, d(d)=3, +=4, +=0, =3, =1, =5, =3.,9,定理9.1 在任何無向圖中, 所有頂點的度數(shù)之和等于邊數(shù)的2倍.,證 G中每條邊 (包括環(huán)) 均有兩個端點，所以在計算G中各頂點度數(shù)之和時，每條邊均提供2度，m 條邊共提供 2m 度.,握手定理,定理9.2 在任何有向圖中，所有頂點的度數(shù)之和等于邊數(shù)的2倍; 所有頂點的入度之和等于所有頂點的出度之和, 都等于邊數(shù).,推論 任何圖 (無向或有向) 中，奇度頂點的個數(shù)是偶數(shù). 證 由握手定理, 所有頂點的度數(shù)之和是偶數(shù), 而偶度頂點的度 數(shù)之和是偶數(shù), 故奇度頂點的度數(shù)之和也是偶數(shù). 所以奇度頂 點的個數(shù)必是偶數(shù),10,例1 無向圖G有16條邊，3個4度頂點，4個3度頂點，其余均為2度頂點度，問G的階數(shù)n為幾？,解 本題的關(guān)鍵是應(yīng)用握手定理. 設(shè)除3度與4度頂點外，還有x個頂點, 由握手定理, 162=32 = 34+43+2x 解得 x = 4, 階數(shù) n = 4+4+3=11.,握手定理應(yīng)用,定理9.3 設(shè)G為任意n階無向簡單圖，則(G)n1,圖的同構(gòu),定義9.5 設(shè)G1=, G2=為兩個無向圖(兩個有向 圖)，若存在雙射函數(shù)f:V1V2, 使得vi,vjV1, (vi,vj)E1 當(dāng)且僅當(dāng) (f(vi),f(vj)E2 （E1 當(dāng)且僅當(dāng) E2 ) 并且, (vi,vj)（）與 (f(vi),f(vj)（）的重數(shù)相 同，則稱G1與G2是同構(gòu)的，記作G1G2.,12,圖同構(gòu)的實例,(1) (2) (3) (4),(1)與(2), (3)與(4), (5)與(6)均不同構(gòu).,(5) (6),說明: 1. 圖的同構(gòu)關(guān)系具有自反性、對稱性和傳遞性. 2. 判斷兩個圖同構(gòu)是個難題,圖同構(gòu)的實例,所有4階3條邊非同構(gòu)的簡單無向圖,13,所有3階2條邊非同構(gòu)的簡單有向圖,補(bǔ)圖與自補(bǔ)圖,定義9.6 設(shè)G=為n階無向簡單圖，令 =(u,v) | uVvVuv(u,v)E, 稱 =為G的補(bǔ)圖 若G 則稱G是自補(bǔ)圖,例,(b)與(c)互為補(bǔ)圖，(a)是自補(bǔ)圖,15,完全圖與競賽圖,定義9.7 (1) n (n1) 階無向完全圖每個頂點與其余頂點均相鄰的無向簡單圖，記作 Kn. 簡單性質(zhì)：m=n(n-1)/2, =n-1 (2) n (n1)階有向完全圖每對頂點之間均有兩條方向相反的有向邊的有向簡單圖. 簡單性質(zhì)： m=n(n-1), =2(n-1) +=+=n-1 (3) n (n1) 階競賽圖基圖為Kn的有向簡單圖. 簡單性質(zhì)： m=n(n-1)/2, =n-1,正則圖,K5 3階有向完全圖 4階競賽圖,定義9.8 k-正則圖=k 的無向簡單圖 簡單性質(zhì)：m=kn/2, 當(dāng)k是奇數(shù)時, n必為偶數(shù). 例 Kn是 (n1)-正則圖 彼得松圖是3-正則圖,子圖,定義9.9 設(shè)兩個圖G=, G =（同為無向圖或同為有向圖）, 若VV且EE，則稱G是G的子圖，G為G 母圖，記作G G. 又若VV或EE，則稱G 為G的真子圖. 若G G且V=V，則稱G 為G的生成子圖 設(shè)V1V且V1, 稱以V1為頂點集, 以G中兩個端點都在V1中的邊組成邊集的圖為G中V1的導(dǎo)出子圖, 記作GV1. 設(shè)E1E且E1, 稱以E1為邊集, 以E1中邊關(guān)聯(lián)的頂點為頂點集的圖為G中E1的導(dǎo)出子圖, 記作GE1 例 G Ga,b,c Ge1,e3,18,定義9.10 設(shè)G=為無向圖 (1) 設(shè)eE，用Ge表示從G中去掉邊e，稱為刪除邊e又設(shè)EE，用 GE 表示從G中刪除E 中的所有邊，稱為刪除E (2) 設(shè)vV，用Gv表示從G中去掉v及所關(guān)聯(lián)的所有邊，稱為刪除頂點v又設(shè)V V，用GV 表示從G中刪除V 中所有的頂點，稱為刪除V (3) 設(shè)e=(u,v)E，用Ge表示從G中刪除e后，將e的兩個端點u,v用一個新的頂點w（可以用u或v充當(dāng)w）代替，并使w關(guān)聯(lián)除e以外u,v關(guān)聯(lián)的所有邊，稱為收縮邊e (4) 設(shè)u,vV（u,v可能相鄰，也可能不相鄰），用G(u,v)（或G+(u,v)）表示在u,v之間加一條邊(u,v)，稱為加新邊 在收縮邊和加新邊過程中可能產(chǎn)生環(huán)和平行邊,刪除, 收縮與加新邊,19,實例,20,9.2 通路與回路,定義9.11 設(shè)圖G= (無向或有向的), G中頂點與邊的交 替序列 = v0e1v1e2elvl，如果vi1, vi 是 ei 的端點(始點和終 點), 1il, 則稱 為v0到vl的通路. v0,vl分別稱作 的始點和終 點. 中的邊數(shù)l稱作它的長度. 又若 v0=vl, 則稱 為回路. 若 所有的邊各異, 則稱 為簡單通路. 又若v0=vl, 則稱 為簡單回 路. 若 中所有頂點各異(除v0和vl可能相同外)且所有邊也各 異, 則稱 為初級通路或路徑. 若又有v0=vl, 則稱 為初級回 路或圈. 長度為奇數(shù)的圈稱為奇圈, 長度為偶數(shù)的圈稱為偶圈. 若 中有邊重復(fù)出現(xiàn), 則 稱為復(fù)雜通路. 若又有v0=vl, 則稱 為復(fù)雜回路.,21,通路與回路,定理9.4 在n 階圖G中，若從頂點u 到v（uv）存在通路，則 從u 到 v 存在長度小于或等于n1 的通路. 推論 在 n 階圖G中，若從頂點u 到 v（uv）存在通路，則 從u 到v 存在長度小于或等于n1的初級通路（路徑）. 定理9.5 在n 階圖G中，若存在 v 到自身的回路，則一定存在 v 到自身長度小于或等于 n 的回路. 推論 在n 階圖G中，若存在 v 到自身的簡單回路，則一定存 在v 到自身的長度小于或等于n 的初級回路.,22,同構(gòu)意義下和定義意義下的圈,例2 無向完全圖Kn（n3）中有幾種非同構(gòu)的圈？,解 長度相同的圈都是同構(gòu)的. 易知Kn(n3)中含長度3,4,n 的圈，共有n2種非同構(gòu)的圈,長度相同的圈都是同構(gòu)的, 因此在同構(gòu)意義下給定長度的圈 只有一個. 在標(biāo)定圖中, 圈表示成頂點和邊的標(biāo)記序列. 如果 只要兩個圈的標(biāo)記序列不同, 稱這兩個圈在定義意義下不同.,例3 無向完全圖K3的頂點依次標(biāo)定為a,b,c在定義意義下K3中有多少個不同的長度為3的圈？,解 在定義意義下, 不同起點(終點)的圈是不同的, 頂點間排列順序不同的圈也是不同的, 因而K3中有3!=6個不同的長為3的圈：abca，acba，bacb，bcab，cabc，cbac,23,帶權(quán)圖與最短路徑,定義9.12 設(shè)圖G= (無向圖或有向圖), 對G的每一條邊e, 給定一個數(shù)W(e),稱作邊e的權(quán). 把這樣的圖稱為帶權(quán)圖, 記作 G=. 當(dāng)e=(u,v)()時, 把W(e)記作W(u,v). 設(shè)P是G中的一條通路, P中所有邊的權(quán)之和稱為P的長度, 記作W(P). 類似地, 可定義回路C的長度W(C). 設(shè)帶權(quán)圖G= (無向圖或有向圖), 其中每一條邊e的 權(quán)W(e)為非負(fù)實數(shù). u,vV, 當(dāng)u和v連通(u可達(dá)v)時, 稱從u到 v長度最短的路徑為從u到v的最短路徑, 稱其長度為從u到v的 距離, 記作d(u,v). 約定: d(u,u)=0; 當(dāng)u和v不連通(u不可達(dá)v)時, d(u,v)=+.,24,最短路問題,最短路問題: 給定帶權(quán)圖G=及頂點u和v, 其中每一條 邊e的權(quán)W(e)為非負(fù)實數(shù), 求從u到v的最短路徑. Dijkstra標(biāo)號法 (求從s到其余各點的最短路徑和距離) 1. 令l(s)(s,0), l(v)(s,+) (vV-s), i1, l(s)是永久標(biāo)號, 其余標(biāo)號均為臨時標(biāo)號, us 2. for 與u關(guān)聯(lián)的臨時標(biāo)號的頂點v 3. if l2(u)+W(u,v)< l2(v) then 令l(v)(u,l2(u)+W(u,v) 4. 計算l2(t)=min l2(v) | vV且有臨時標(biāo)號, l(t)改為永久標(biāo)號 5. if i<n then 令ut, ii+1, 轉(zhuǎn)2 對每一個u, d(s,u)= l2(u),根據(jù)l1(v)回溯找到s到u的最短路徑.,25,實例,例9.5 一個總部和6個工地, 求從總部到各工地的最短路徑 解,26,實例,27,實例,28,實例,29,實例,v1v3v2, d(v1,v2)=13 v1v3, d(v1,v3)=10 v1v3v5v4, d(v1,v4)=18 v1v3v5, d(v1,v5)=14 v1v3v5v6, d(v1,v6)=16 v1v3v5v6v7, d(v1,v7)=22,30,9.3 圖的連通性,定義9.13 設(shè)無向圖G=，若u,vV之間存在通路，則稱 u,v是連通的，記作uv. 規(guī)定: vV vv 若無向圖G是平凡圖或G中任何兩個頂點都是連通的，則 稱G為連通圖，否則稱G為非連通圖 是V上的等價關(guān)系, 具有自反性、對稱性和傳遞性 定義9.14 設(shè)無向圖G=，Vi是V關(guān)于頂點之間連通關(guān) 系的一個等價類，稱導(dǎo)出子圖GVi為G的一個連通分支. G的連通分支數(shù)記為p(G),31,點割集與邊割集,定義9.15 設(shè)無向圖G=. 若VV使得p(GV )p(G), 且 對于任意的V V, 均有p(GV)=p(G), 則稱V是G的點割集. 若V =v, 則稱v為割點 定義9.16 設(shè)無向圖G=, 若EE使得p(GE )p(G), 且 對于任意的EE, 均有p(GE)=p(G), 則稱E是G的邊割集， 簡稱為割集. 若E =e, 則稱e為割邊或橋,例3 v1,v4，v6是點割集， v6是割點. v2,v5不是. e1,e2，e1,e3,e5,e6，e8等 是邊割集，e8是橋. 而e7,e9,e5,e6 不是.,32,點連通度與邊連通度,定義9.17 G為連通非完全圖, 稱 (G) = min |V |V 為點割集 為G的點連通度, 簡稱連通度. 若(G)k，則稱G為 k-連通圖 . 規(guī)定 (Kn) = n1, 非連通圖的連通度為0. 定義9.18 設(shè)G為連通圖, 稱 (G) = min|E|E為邊割集 為G的邊連通度. 若(G)r，則稱G是 r 邊-連通圖. 規(guī)定非連通圖的邊連通度為0.,例 =2, 2-連通圖, 也是1-連通. =2, 2邊-連通圖, 也是1邊-連通.,33,幾點說明,(Kn)=(Kn)=n1 G非連通，則 =0 若G中有割點，則=1，若有橋，則=1 若(G)=k, 則G是1-連通圖，2-連通圖，k-連通圖，但不是(k+s)-連通圖，s1 若(G)=r, 則G是1邊-連通圖，2邊-連通圖，r邊-連通圖，但不是(r+s)-邊連通圖，s1 定理9.6 (G)(G)(G),34,有向圖的連通性及分類,定義9.19 設(shè)D=為一個有向圖, vi,vjV, 若從vi到vj存在 通路, 則稱vi可達(dá)vj, 記作vivj . 規(guī)定vi vi. 若vivj且vjvi， 則稱vi與vj是相互可達(dá)的, 記作vivj. 規(guī)定vivi 性質(zhì): 具有自反性(vi vi)、傳遞性 具有自反性、對稱性、傳遞性 定義9.20 若有向圖D=<V,E)的基圖是連通圖, 則稱D是弱連通 圖, 簡稱為連通圖. 若vi,vjV, vivj與vjvi至少有一個成立， 則稱 D是單向連通圖. 若vi,vjV, 均有vivj, 則稱D是強(qiáng)連 通圖,35,有向圖的連通性,強(qiáng)連通 單向連通 弱連通,定理9.7 有向圖D=是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的回路 證 充分性顯然. 證必要性. 設(shè)V=v1,v2,vn, i為vi到vi+1的通路( i=1,2,n1), n為vn到v1的通路. 依次連接1, 2, , n1, n所得到的回路經(jīng)過D中每個頂點至少一次 定理9.8 有向圖D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個頂點至少一次的通路,例,擴(kuò)大路徑法,設(shè)G=為無向圖, 為G中一條路徑. 若此路徑的兩個端 點都不與通路外的頂點相鄰, 則稱 是極大路徑. 任取一條邊, 如果它有一個端點與其他的頂點相鄰, 就將這條 邊延伸到這個頂點. 繼續(xù)這一過程, 直至得到一條極大路徑為 止. 稱此種方法為“擴(kuò)大路徑法”. 用擴(kuò)大路徑法總可以得到 一條極大路徑. 在有向圖中可類似討論.,例 由一條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是 最長的路徑,37,擴(kuò)大路徑法的應(yīng)用,例4 設(shè) G 為 n（n3）階無向簡單圖， 2，證明G 中存在 長度 +1 的圈.,證 設(shè) = v0v1vl 是一條極大路徑, 則 l . 因為v0 不與 外 頂點相鄰, 又 d(v0) , 因而在 上除 v1外, 至少還存在1個 頂點與 v0 相鄰. 設(shè) vx 是離 v0 最遠(yuǎn)的頂點, 于是v0v1vxv0 為 G 中長度 +1 的圈.,38,9.4 圖的矩陣表示,無向圖的關(guān)聯(lián)矩陣 定義9.21 無向圖G=，|V|=n，|E|=m，令 mij為 vi 與 ej 的關(guān)聯(lián)次數(shù)，稱(mij)nm為G 的關(guān)聯(lián)矩陣，記為M(G).,例,39,無向圖關(guān)聯(lián)矩陣的性質(zhì),40,定義9.22 設(shè)有向圖D=中無環(huán)，令 則稱 (mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).,例,有向圖(無環(huán))的關(guān)聯(lián)矩陣,41,(1) 每列恰好有一個+1和一個-1 (2) -1的個數(shù)等于+1的個數(shù)，都等于邊數(shù)m. 第i行中，+1的個數(shù)等于d+(vi)，-1的個數(shù)等于d(vi) (4) 平行邊對應(yīng)的列相同,有向圖關(guān)聯(lián)矩陣的性質(zhì),42,有向圖的鄰接矩陣,定義9.23 設(shè)有向圖D=, V=v1, v2, , vn, 令 為頂點 vi 鄰接到頂點 vj 邊的條數(shù)，稱( )為D的鄰接矩陣，記作 A(D)，或簡記為A.,例,43,有向圖鄰接矩陣的性質(zhì),定理9.9 設(shè) A為有向圖 D 的鄰接矩陣, 頂點集V=v1,v2, vn，則 A 的 l 次冪 Al（l1）中元素,鄰接矩陣的應(yīng)用,45,例5 有向圖D如圖所示，求 A, A2, A3, A4，并回答諸問題： (1) D 中長度為1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？ (2) D 中長度小于或等于4的通路為多少條？其中有多少條回路？,實例,46,(1) D中長度為1的通路為8條，其中有1條是回路. D中長度為2的通路為11條，其中有3條是回路. D中長度為3的通路為14條，其中有1條是回路. D中長度為4的通路為17條，其中有3條是回路. (2) D中長度小于等于4的通路為50條，其中有8條是回路.,實例求解,47,定義9.24 設(shè)D=為有向圖. V=v1, v2, , vn, 令,有向圖的可達(dá)矩陣,稱 (pij)nn 為D的可達(dá)矩陣，記作P(D)，簡記為P. P(D)的主對角線上的元素全為1. D 強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全1矩陣.,例,48,第九章 習(xí)題課,主要內(nèi)容 無向圖和有向圖及其有關(guān)的概念; 握手定理及其推論；圖的同構(gòu) 通路與回路 無向圖的連通性與連通度 有向圖的連通性及其分類 圖的矩陣表示,49,基本要求,深刻理解圖及其有關(guān)的概念 深刻理解和靈活地應(yīng)用握手定理及推論 記住通路與回路的定義、分類及表示法 深刻理解與無向圖連通性、連通度有關(guān)的諸多概念 會判別有向圖連通性的類型 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達(dá)矩陣,50,19階無向圖G中，每個頂點的度數(shù)不是5就是6. 證明G中至少有5個6度頂點或至少有6個5度頂點.,練習(xí)1,證 關(guān)鍵是利用握手定理的推論. 方法一：窮舉法 設(shè)G中有x個5度頂點，(9x)個6度頂點，由于奇度頂點的個數(shù)是偶數(shù)，(x, 9x)只有5種可能：(0,9), (2,7), (4,5), (6,3), (8,1）它們都滿足要求.,方法二：反證法 否則，至多有4個5度頂點并且至多有4個6度頂點，這與G是 9 階圖矛盾.,51,2存在以2, 2, 2, 2, 3, 3為頂點度數(shù)的簡單圖嗎？若存在，畫出盡可能多的這種非同構(gòu)的圖來.,練習(xí)2,解,52,證 用擴(kuò)大路徑法證明. 設(shè) +, 證明D中存在長度 +1的圈. 設(shè) = v0v1vl為極大路徑, 則l . 在 上存在d(v0) 個頂點 鄰接到v0, 設(shè)vk是其中離v0最遠(yuǎn)的頂點, k . 于是, v0v1vkv0為D中長度 +1的圈 . 當(dāng) + 時, 類似可證.,3設(shè)D=為有向簡單圖, 已知 (D) 2, +(D)0, (D)0, 證明D中存在長度 max +, +1的圈.,練習(xí)3,53,(1) D中有幾種不同構(gòu)的圈？ (2) D中有幾種不同構(gòu)的非圈簡單回路？ (3) D是哪類連通圖? (4) D中v1到v4長度為1,2,3,4的通路各多少條？ (5) D中v1到v1長度為1,2,3,4的回路各多少條？ (6) D中長度為4的通路（不含回路）有多少條？ (7) D中長度為4的回路有多少條？ (8) D中長度4的通路有多少條？其中有幾條是回路？ (9) 寫出D的可達(dá)矩陣.,4有向圖D如圖所示，回答下列諸問：,練習(xí)4,54,解答,解 (1) 有3種非同構(gòu)的圈，長度分別為1,2,3.,(2) 有3種非同構(gòu)的非圈簡單回路，它們的長度分別為 4,5,6.,(3) D是強(qiáng)連通的.,為解(4)(8), 先求D的鄰接矩陣的前4次冪.,55,(4) v1到v4長度為1,2,3,4的通路數(shù)分別為0,0,2,2. (定義意義下).,解答,(5) v1到v1長度為1,2,3,4的回路數(shù)分別為1,1,3,5.,(6) 長度為4的通路(不含回路)為33條.,(7) 長度為4的回路為11條.,(8) 長度4的通路88條，其中22條為回路.,(9) 44的全1矩陣.,