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

《離散數(shù)學(xué)屈婉玲第九章》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)屈婉玲第九章（55頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1,第三部分 圖論,本部分主要內(nèi)容 圖的基本概念 樹 歐拉圖與哈密頓圖 二部圖與匹配 平面圖 著色,2,第九章 圖的基本概念,主要內(nèi)容 圖 通路與回路 圖的連通性 圖的矩陣表示 預(yù)備知識(shí) 多重集合元素可以重復(fù)出現(xiàn)的集合 無序集AB=(x,y) | xAyB,14.1 圖,定義9.1 無向圖G = , 其中 (1) V為非空有窮集, 稱為頂點(diǎn)集，其元素稱為頂點(diǎn) (2) E為VV 的多重有窮集, 稱為邊集, 其元素稱為無向邊, 簡(jiǎn)稱邊 例 無向圖G = , 其中 V = v1, v2, v3, v4, v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,

2、v5), (v1,v5), (v4,v5),4,有向圖,定義9.2 有向圖D=,其中 (1) V 為非空有窮集, 稱為頂點(diǎn)集，其元素稱為頂點(diǎn) (2) E為VV 的多重有窮集, 稱為邊集, 其元素稱為有向邊, 簡(jiǎn)稱邊 例 有向圖D=, 其中 V=a,b,c,d E=, , 注意：圖的集合表示與圖形表示之間的對(duì)應(yīng),5,相關(guān)概念,1. 無向圖和有向圖通稱圖. 記頂點(diǎn)集V(G), 邊集E(G). 2. 圖的階, n階圖. 3. n 階零圖Nn, 平凡圖N1. 4. 空?qǐng)D. 5. 標(biāo)定圖與非標(biāo)定圖. 6. 有向圖的基圖. 7. 無向圖中頂點(diǎn)與邊的關(guān)聯(lián)及關(guān)聯(lián)次數(shù), 頂點(diǎn)與頂點(diǎn)、邊與 邊的相鄰關(guān)系. 8.

3、有向圖中頂點(diǎn)與邊的關(guān)聯(lián), 頂點(diǎn)與頂點(diǎn)、邊與邊的相鄰關(guān) 系. 9. 環(huán), 孤立點(diǎn).,6,多重圖與簡(jiǎn)單圖,定義9.3 無向圖中關(guān)聯(lián)同一對(duì)頂點(diǎn)的2條和2條以上的邊稱為 平行邊. 有向圖中2條和2條以上始點(diǎn)、終點(diǎn)相同的邊稱為平 行邊. 平行邊的條數(shù)稱為重?cái)?shù). 含平行邊的圖稱為多重圖, 不含平行邊和環(huán)的圖稱為簡(jiǎn)單圖. 定義9.4 設(shè)G=為無向圖, vV, 稱v作為邊的端點(diǎn)的次 數(shù)之和為v的度數(shù), 簡(jiǎn)稱度, 記作d(v). 設(shè)D=為有向圖, vV, 稱v作為邊的始點(diǎn)的次數(shù)之和 為v的出度, 記作d+(v); 稱v作為邊的終點(diǎn)的次數(shù)之和為v的入 度, 記作d(v); 稱d+(v)+d(v)為v的度數(shù), 記作

4、d(v).,7,頂點(diǎn)的度數(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 懸掛頂點(diǎn): 度數(shù)為1的頂點(diǎn), 懸掛邊: 與懸掛頂點(diǎn)關(guān)聯(lián)的邊. 偶度(奇度)頂點(diǎn): 度數(shù)為偶數(shù)(奇數(shù))的頂點(diǎn),8,實(shí)例,d(v1)=4, d(v2)=4, d(v

5、3)=2, d(v4)=1, d(v5)=3. =4, =1. v4是懸掛點(diǎn), 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 在任何無向圖中, 所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的2倍.,證 G中每條邊 (包括環(huán)) 均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，m 條邊共提供 2m 度.,握手定理,定理9.2 在任何有向圖中，所有頂點(diǎn)的度數(shù)之和等于邊

6、數(shù)的2倍; 所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和, 都等于邊數(shù).,推論 任何圖 (無向或有向) 中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù). 證 由握手定理, 所有頂點(diǎn)的度數(shù)之和是偶數(shù), 而偶度頂點(diǎn)的度 數(shù)之和是偶數(shù), 故奇度頂點(diǎn)的度數(shù)之和也是偶數(shù). 所以奇度頂 點(diǎn)的個(gè)數(shù)必是偶數(shù),10,例1 無向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余均為2度頂點(diǎn)度，問G的階數(shù)n為幾？,解 本題的關(guān)鍵是應(yīng)用握手定理. 設(shè)除3度與4度頂點(diǎn)外，還有x個(gè)頂點(diǎn), 由握手定理, 162=32 = 34+43+2x 解得 x = 4, 階數(shù) n = 4+4+3=11.,握手定理應(yīng)用,定理9.3 設(shè)G為任意n階無向簡(jiǎn)單圖，則(G

7、)n1,圖的同構(gòu),定義9.5 設(shè)G1=, G2=為兩個(gè)無向圖(兩個(gè)有向 圖)，若存在雙射函數(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)（）的重?cái)?shù)相 同，則稱G1與G2是同構(gòu)的，記作G1G2.,12,圖同構(gòu)的實(shí)例,(1) (2) (3) (4),(1)與(2), (3)與(4), (5)與(6)均不同構(gòu).,(5) (6),說明: 1. 圖的同構(gòu)關(guān)系具有自反性、對(duì)稱性和傳遞性. 2. 判斷兩個(gè)圖同構(gòu)是個(gè)難題,圖同構(gòu)的實(shí)例,所有4階3條邊非同構(gòu)的簡(jiǎn)單無向圖,13,

8、所有3階2條邊非同構(gòu)的簡(jiǎn)單有向圖,補(bǔ)圖與自補(bǔ)圖,定義9.6 設(shè)G=為n階無向簡(jiǎn)單圖，令 =(u,v) | uVvVuv(u,v)E, 稱 =為G的補(bǔ)圖 若G 則稱G是自補(bǔ)圖,例,(b)與(c)互為補(bǔ)圖，(a)是自補(bǔ)圖,15,完全圖與競(jìng)賽圖,定義9.7 (1) n (n1) 階無向完全圖每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的無向簡(jiǎn)單圖，記作 Kn. 簡(jiǎn)單性質(zhì)：m=n(n-1)/2, =n-1 (2) n (n1)階有向完全圖每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的有向簡(jiǎn)單圖. 簡(jiǎn)單性質(zhì)： m=n(n-1), =2(n-1) +=+=n-1 (3) n (n1) 階競(jìng)賽圖基圖為Kn的有向簡(jiǎn)單圖. 簡(jiǎn)單性質(zhì)： m

9、=n(n-1)/2, =n-1,正則圖,K5 3階有向完全圖 4階競(jìng)賽圖,定義9.8 k-正則圖=k 的無向簡(jiǎn)單圖 簡(jiǎn)單性質(zhì)：m=kn/2, 當(dāng)k是奇數(shù)時(shí), n必為偶數(shù). 例 Kn是 (n1)-正則圖 彼得松圖是3-正則圖,子圖,定義9.9 設(shè)兩個(gè)圖G=, G =（同為無向圖或同為有向圖）, 若VV且EE，則稱G是G的子圖，G為G 母圖，記作G G. 又若VV或EE，則稱G 為G的真子圖. 若G G且V=V，則稱G 為G的生成子圖 設(shè)V1V且V1, 稱以V1為頂點(diǎn)集, 以G中兩個(gè)端點(diǎn)都在V1中的邊組成邊集的圖為G中V1的導(dǎo)出子圖, 記作GV1. 設(shè)E1E且E1, 稱以E1為邊集, 以E1中邊關(guān)

10、聯(lián)的頂點(diǎn)為頂點(diǎ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)的所有邊，稱為刪除頂點(diǎn)v又設(shè)V V，用GV 表示從G中刪除V 中所有的頂點(diǎn)，稱為刪除V (3) 設(shè)e=(u,v)E，用Ge表示從G中刪除e后，將e的兩個(gè)端點(diǎn)u,v用一個(gè)新的頂點(diǎn)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可能相鄰，也可能不相鄰），

11、用G(u,v)（或G+(u,v)）表示在u,v之間加一條邊(u,v)，稱為加新邊 在收縮邊和加新邊過程中可能產(chǎn)生環(huán)和平行邊,刪除, 收縮與加新邊,19,實(shí)例,20,9.2 通路與回路,定義9.11 設(shè)圖G= (無向或有向的), G中頂點(diǎn)與邊的交 替序列 = v0e1v1e2elvl，如果vi1, vi 是 ei 的端點(diǎn)(始點(diǎn)和終 點(diǎn)), 1il, 則稱 為v0到vl的通路. v0,vl分別稱作 的始點(diǎn)和終 點(diǎn). 中的邊數(shù)l稱作它的長(zhǎng)度. 又若 v0=vl, 則稱 為回路. 若 所有的邊各異, 則稱 為簡(jiǎn)單通路. 又若v0=vl, 則稱 為簡(jiǎn)單回 路. 若 中所有頂點(diǎn)各異(除v0和vl可能相同外

12、)且所有邊也各 異, 則稱 為初級(jí)通路或路徑. 若又有v0=vl, 則稱 為初級(jí)回 路或圈. 長(zhǎng)度為奇數(shù)的圈稱為奇圈, 長(zhǎng)度為偶數(shù)的圈稱為偶圈. 若 中有邊重復(fù)出現(xiàn), 則 稱為復(fù)雜通路. 若又有v0=vl, 則稱 為復(fù)雜回路.,21,通路與回路,定理9.4 在n 階圖G中，若從頂點(diǎn)u 到v（uv）存在通路，則 從u 到 v 存在長(zhǎng)度小于或等于n1 的通路. 推論 在 n 階圖G中，若從頂點(diǎn)u 到 v（uv）存在通路，則 從u 到v 存在長(zhǎng)度小于或等于n1的初級(jí)通路（路徑）. 定理9.5 在n 階圖G中，若存在 v 到自身的回路，則一定存在 v 到自身長(zhǎng)度小于或等于 n 的回路. 推論 在n 階

13、圖G中，若存在 v 到自身的簡(jiǎn)單回路，則一定存 在v 到自身的長(zhǎng)度小于或等于n 的初級(jí)回路.,22,同構(gòu)意義下和定義意義下的圈,例2 無向完全圖Kn（n3）中有幾種非同構(gòu)的圈？,解 長(zhǎng)度相同的圈都是同構(gòu)的. 易知Kn(n3)中含長(zhǎng)度3,4,n 的圈，共有n2種非同構(gòu)的圈,長(zhǎng)度相同的圈都是同構(gòu)的, 因此在同構(gòu)意義下給定長(zhǎng)度的圈 只有一個(gè). 在標(biāo)定圖中, 圈表示成頂點(diǎn)和邊的標(biāo)記序列. 如果 只要兩個(gè)圈的標(biāo)記序列不同, 稱這兩個(gè)圈在定義意義下不同.,例3 無向完全圖K3的頂點(diǎn)依次標(biāo)定為a,b,c在定義意義下K3中有多少個(gè)不同的長(zhǎng)度為3的圈？,解 在定義意義下, 不同起點(diǎn)(終點(diǎn))的圈是不同的, 頂點(diǎn)間

14、排列順序不同的圈也是不同的, 因而K3中有3!=6個(gè)不同的長(zhǎng)為3的圈：abca，acba，bacb，bcab，cabc，cbac,23,帶權(quán)圖與最短路徑,定義9.12 設(shè)圖G= (無向圖或有向圖), 對(duì)G的每一條邊e, 給定一個(gè)數(shù)W(e),稱作邊e的權(quán). 把這樣的圖稱為帶權(quán)圖, 記作 G=. 當(dāng)e=(u,v)()時(shí), 把W(e)記作W(u,v). 設(shè)P是G中的一條通路, P中所有邊的權(quán)之和稱為P的長(zhǎng)度, 記作W(P). 類似地, 可定義回路C的長(zhǎng)度W(C). 設(shè)帶權(quán)圖G= (無向圖或有向圖), 其中每一條邊e的 權(quán)W(e)為非負(fù)實(shí)數(shù). u,vV, 當(dāng)u和v連通(u可達(dá)v)時(shí), 稱從u到 v長(zhǎng)度

15、最短的路徑為從u到v的最短路徑, 稱其長(zhǎng)度為從u到v的 距離, 記作d(u,v). 約定: d(u,u)=0; 當(dāng)u和v不連通(u不可達(dá)v)時(shí), d(u,v)=+.,24,最短路問題,最短路問題: 給定帶權(quán)圖G=及頂點(diǎn)u和v, 其中每一條 邊e的權(quán)W(e)為非負(fù)實(shí)數(shù), 求從u到v的最短路徑. Dijkstra標(biāo)號(hào)法 (求從s到其余各點(diǎn)的最短路徑和距離) 1. 令l(s)(s,0), l(v)(s,+) (vV-s), i1, l(s)是永久標(biāo)號(hào), 其余標(biāo)號(hào)均為臨時(shí)標(biāo)號(hào), us 2. for 與u關(guān)聯(lián)的臨時(shí)標(biāo)號(hào)的頂點(diǎn)v 3. if l2(u)+W(u,v) l2(v) then 令l(v)(u,

16、l2(u)+W(u,v) 4. 計(jì)算l2(t)=min l2(v) | vV且有臨時(shí)標(biāo)號(hào), l(t)改為永久標(biāo)號(hào) 5. if in then 令ut, ii+1, 轉(zhuǎn)2 對(duì)每一個(gè)u, d(s,u)= l2(u),根據(jù)l1(v)回溯找到s到u的最短路徑.,25,實(shí)例,例9.5 一個(gè)總部和6個(gè)工地, 求從總部到各工地的最短路徑 解,26,實(shí)例,27,實(shí)例,28,實(shí)例,29,實(shí)例,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 v1v3v5v6v

17、7, d(v1,v7)=22,30,9.3 圖的連通性,定義9.13 設(shè)無向圖G=，若u,vV之間存在通路，則稱 u,v是連通的，記作uv. 規(guī)定: vV vv 若無向圖G是平凡圖或G中任何兩個(gè)頂點(diǎn)都是連通的，則 稱G為連通圖，否則稱G為非連通圖 是V上的等價(jià)關(guān)系, 具有自反性、對(duì)稱性和傳遞性 定義9.14 設(shè)無向圖G=，Vi是V關(guān)于頂點(diǎn)之間連通關(guān) 系的一個(gè)等價(jià)類，稱導(dǎo)出子圖GVi為G的一個(gè)連通分支. G的連通分支數(shù)記為p(G),31,點(diǎn)割集與邊割集,定義9.15 設(shè)無向圖G=. 若VV使得p(GV )p(G), 且 對(duì)于任意的V V, 均有p(GV)=p(G), 則稱V是G的點(diǎn)割集. 若V

18、=v, 則稱v為割點(diǎn) 定義9.16 設(shè)無向圖G=, 若EE使得p(GE )p(G), 且 對(duì)于任意的EE, 均有p(GE)=p(G), 則稱E是G的邊割集， 簡(jiǎn)稱為割集. 若E =e, 則稱e為割邊或橋,例3 v1,v4，v6是點(diǎn)割集， v6是割點(diǎn). v2,v5不是. e1,e2，e1,e3,e5,e6，e8等 是邊割集，e8是橋. 而e7,e9,e5,e6 不是.,32,點(diǎn)連通度與邊連通度,定義9.17 G為連通非完全圖, 稱 (G) = min |V |V 為點(diǎn)割集 為G的點(diǎn)連通度, 簡(jiǎn)稱連通度. 若(G)k，則稱G為 k-連通圖 . 規(guī)定 (Kn) = n1, 非連通圖的連通度為0. 定

19、義9.18 設(shè)G為連通圖, 稱 (G) = min|E|E為邊割集 為G的邊連通度. 若(G)r，則稱G是 r 邊-連通圖. 規(guī)定非連通圖的邊連通度為0.,例 =2, 2-連通圖, 也是1-連通. =2, 2邊-連通圖, 也是1邊-連通.,33,幾點(diǎn)說明,(Kn)=(Kn)=n1 G非連通，則 =0 若G中有割點(diǎn)，則=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

20、 設(shè)D=為一個(gè)有向圖, vi,vjV, 若從vi到vj存在 通路, 則稱vi可達(dá)vj, 記作vivj . 規(guī)定vi vi. 若vivj且vjvi， 則稱vi與vj是相互可達(dá)的, 記作vivj. 規(guī)定vivi 性質(zhì): 具有自反性(vi vi)、傳遞性 具有自反性、對(duì)稱性、傳遞性 定義9.20 若有向圖D=V,E)的基圖是連通圖, 則稱D是弱連通 圖, 簡(jiǎn)稱為連通圖. 若vi,vjV, vivj與vjvi至少有一個(gè)成立， 則稱 D是單向連通圖. 若vi,vjV, 均有vivj, 則稱D是強(qiáng)連 通圖,35,有向圖的連通性,強(qiáng)連通 單向連通 弱連通,定理9.7 有向圖D=是強(qiáng)連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過

21、每個(gè)頂點(diǎn)至少一次的回路 證 充分性顯然. 證必要性. 設(shè)V=v1,v2,vn, i為vi到vi+1的通路( i=1,2,n1), n為vn到v1的通路. 依次連接1, 2, , n1, n所得到的回路經(jīng)過D中每個(gè)頂點(diǎn)至少一次 定理9.8 有向圖D是單向連通圖當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路,例,擴(kuò)大路徑法,設(shè)G=為無向圖, 為G中一條路徑. 若此路徑的兩個(gè)端 點(diǎn)都不與通路外的頂點(diǎn)相鄰, 則稱 是極大路徑. 任取一條邊, 如果它有一個(gè)端點(diǎn)與其他的頂點(diǎn)相鄰, 就將這條 邊延伸到這個(gè)頂點(diǎn). 繼續(xù)這一過程, 直至得到一條極大路徑為 止. 稱此種方法為“擴(kuò)大路徑法”. 用擴(kuò)大路徑法總可以得到

22、一條極大路徑. 在有向圖中可類似討論.,例 由一條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是 最長(zhǎng)的路徑,37,擴(kuò)大路徑法的應(yīng)用,例4 設(shè) G 為 n（n3）階無向簡(jiǎn)單圖， 2，證明G 中存在 長(zhǎng)度 +1 的圈.,證 設(shè) = v0v1vl 是一條極大路徑, 則 l . 因?yàn)関0 不與 外 頂點(diǎn)相鄰, 又 d(v0) , 因而在 上除 v1外, 至少還存在1個(gè) 頂點(diǎn)與 v0 相鄰. 設(shè) vx 是離 v0 最遠(yuǎn)的頂點(diǎn), 于是v0v1vxv0 為 G 中長(zhǎng)度 +1 的圈.,38,9.4 圖的矩陣表示,無向圖的關(guān)聯(lián)矩陣 定義9.21 無向圖G=，|V|=n，|E|=m，令 mij為 vi 與 ej

23、的關(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) 每列恰好有一個(gè)+1和一個(gè)-1 (2) -1的個(gè)數(shù)等于+1的個(gè)數(shù)，都等于邊數(shù)m. 第i行中，+1的個(gè)數(shù)等于d+(vi)，-1的個(gè)數(shù)等于d(vi) (4) 平行邊對(duì)應(yīng)的列相同,有向圖關(guān)聯(lián)矩陣的性質(zhì),42,有向圖的鄰接矩陣,定義9.23 設(shè)有向圖D=, V=v1, v2, , vn, 令 為頂點(diǎn) vi 鄰接到頂點(diǎn) vj 邊的條數(shù)，稱( )為D的鄰接矩陣，記作 A(D)，

24、或簡(jiǎn)記為A.,例,43,有向圖鄰接矩陣的性質(zhì),定理9.9 設(shè) A為有向圖 D 的鄰接矩陣, 頂點(diǎn)集V=v1,v2, vn，則 A 的 l 次冪 Al（l1）中元素,鄰接矩陣的應(yīng)用,45,例5 有向圖D如圖所示，求 A, A2, A3, A4，并回答諸問題： (1) D 中長(zhǎng)度為1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？ (2) D 中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回路？,實(shí)例,46,(1) D中長(zhǎng)度為1的通路為8條，其中有1條是回路. D中長(zhǎng)度為2的通路為11條，其中有3條是回路. D中長(zhǎng)度為3的通路為14條，其中有1條是回路. D中長(zhǎng)度為4的通路為17條，其中

25、有3條是回路. (2) D中長(zhǎng)度小于等于4的通路為50條，其中有8條是回路.,實(shí)例求解,47,定義9.24 設(shè)D=為有向圖. V=v1, v2, , vn, 令,有向圖的可達(dá)矩陣,稱 (pij)nn 為D的可達(dá)矩陣，記作P(D)，簡(jiǎn)記為P. P(D)的主對(duì)角線上的元素全為1. D 強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全1矩陣.,例,48,第九章 習(xí)題課,主要內(nèi)容 無向圖和有向圖及其有關(guān)的概念; 握手定理及其推論；圖的同構(gòu) 通路與回路 無向圖的連通性與連通度 有向圖的連通性及其分類 圖的矩陣表示,49,基本要求,深刻理解圖及其有關(guān)的概念 深刻理解和靈活地應(yīng)用握手定理及推論 記住通路與回路的定義、分類及表示

26、法 深刻理解與無向圖連通性、連通度有關(guān)的諸多概念 會(huì)判別有向圖連通性的類型 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣,50,19階無向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是5就是6. 證明G中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn).,練習(xí)1,證 關(guān)鍵是利用握手定理的推論. 方法一：窮舉法 設(shè)G中有x個(gè)5度頂點(diǎn)，(9x)個(gè)6度頂點(diǎn)，由于奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)，(x, 9x)只有5種可能：(0,9), (2,7), (4,5), (6,3), (8,1）它們都滿足要求.,方法二：反證法 否則，至多有4個(gè)5度頂點(diǎn)并且至多有4個(gè)6度頂點(diǎn)，這與G是 9 階圖矛盾.,51,2存在以2, 2,

27、2, 2, 3, 3為頂點(diǎn)度數(shù)的簡(jiǎn)單圖嗎？若存在，畫出盡可能多的這種非同構(gòu)的圖來.,練習(xí)2,解,52,證 用擴(kuò)大路徑法證明. 設(shè) +, 證明D中存在長(zhǎng)度 +1的圈. 設(shè) = v0v1vl為極大路徑, 則l . 在 上存在d(v0) 個(gè)頂點(diǎn) 鄰接到v0, 設(shè)vk是其中離v0最遠(yuǎn)的頂點(diǎn), k . 于是, v0v1vkv0為D中長(zhǎng)度 +1的圈 . 當(dāng) + 時(shí), 類似可證.,3設(shè)D=為有向簡(jiǎn)單圖, 已知 (D) 2, +(D)0, (D)0, 證明D中存在長(zhǎng)度 max +, +1的圈.,練習(xí)3,53,(1) D中有幾種不同構(gòu)的圈？ (2) D中有幾種不同構(gòu)的非圈簡(jiǎn)單回路？ (3) D是哪類連通圖? (

28、4) D中v1到v4長(zhǎng)度為1,2,3,4的通路各多少條？ (5) D中v1到v1長(zhǎng)度為1,2,3,4的回路各多少條？ (6) D中長(zhǎng)度為4的通路（不含回路）有多少條？ (7) D中長(zhǎng)度為4的回路有多少條？ (8) D中長(zhǎng)度4的通路有多少條？其中有幾條是回路？ (9) 寫出D的可達(dá)矩陣.,4有向圖D如圖所示，回答下列諸問：,練習(xí)4,54,解答,解 (1) 有3種非同構(gòu)的圈，長(zhǎng)度分別為1,2,3.,(2) 有3種非同構(gòu)的非圈簡(jiǎn)單回路，它們的長(zhǎng)度分別為 4,5,6.,(3) D是強(qiáng)連通的.,為解(4)(8), 先求D的鄰接矩陣的前4次冪.,55,(4) v1到v4長(zhǎng)度為1,2,3,4的通路數(shù)分別為0,0,2,2. (定義意義下).,解答,(5) v1到v1長(zhǎng)度為1,2,3,4的回路數(shù)分別為1,1,3,5.,(6) 長(zhǎng)度為4的通路(不含回路)為33條.,(7) 長(zhǎng)度為4的回路為11條.,(8) 長(zhǎng)度4的通路88條，其中22條為回路.,(9) 44的全1矩陣.,