1、閩南師范大學(xué) 計(jì)算機(jī)學(xué)院 2014年11月,第五部分 組合數(shù)學(xué) 作業(yè),作業(yè)講評,14-5設(shè)無向圖有10條邊，3度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)的度數(shù)均小于3，問G中至少有幾個(gè)頂點(diǎn)？在最少頂點(diǎn)情況下，寫出G的度數(shù)列， (G), (G) 解：設(shè)G的階數(shù)為n,已知有2個(gè)3度頂點(diǎn)和2個(gè)4度頂點(diǎn)，其余n-4個(gè)頂點(diǎn)的度數(shù)均小于或等于2，由握手定理得 2m=20=7,即G中至少有7個(gè)頂點(diǎn)，當(dāng)D有7個(gè)頂點(diǎn)時(shí)，其度數(shù)列為2，2，2，3，3，4，4， (G) =4， (G) =3,作業(yè)講評,14-15 下列各數(shù)列中哪些是可簡單圖化的？對于簡單圖化的試給出兩個(gè)非同構(gòu)的簡單圖。 (2) (1,1,2,2,3,3,5,5)

2、 (3) (2,2,2,2,3,3) 解： (2)可簡單圖化 (3)可簡單圖化,作業(yè)講評,14-21 無向圖G如圖所示，求(1)求G圖的全部點(diǎn)割集和邊集，并指出其中的割點(diǎn)和橋（割邊） (2) 求G的點(diǎn)連通度k(G) 和邊連通度(G) 解:(1) 點(diǎn)割集2個(gè)：a,c,d,其中d是割點(diǎn)，邊割集有7個(gè)：e5,e1 e3e2 e4e1 e2e2 e3e3 e4e1 e4，其中是e5橋。 (2)因?yàn)榧扔懈铧c(diǎn)又有橋，所以k= =1,作業(yè)講評,14-15 下列各數(shù)列中哪些是可簡單圖化的？對于簡單圖化的試給出兩個(gè)非同構(gòu)的簡單圖。 (1) (2,3,3,5,5,6,6) 解：(1) (2,3,3,5,5,6,6

3、) 不可簡單圖化。 （反證法）假設(shè)存在無向簡單圖G以它為度數(shù)列設(shè)d(v1)=2, d(v2)= d(v3)=3, d(v4)= d(v5)=5, d(v6)= d(v7)=6, 由于只有7個(gè)頂點(diǎn)，v6，v7必與v1，v5均相鄰， v6與v7也相鄰，因?yàn)閐(v1)=2, 故v1不能再與v2，v5相鄰，于是，要滿足v4，v5的度數(shù)，它們必須與v2，v3均相鄰，從而d(v2)=4, d(v3)=4,這與d(v2)= d(v3)=3矛盾,作業(yè)講評,14-41 設(shè)G是無向圖簡單圖， (G)=2,證明G中存在長度大于或等于(G)+1的圈。 證明：用擴(kuò)大路徑法證明。 設(shè) = v0v1vl為極大路徑（可用擴(kuò)大

4、路徑法得到），則l=(G) 由極大路徑的性質(zhì)（ 的兩個(gè)端點(diǎn)v0與v0不與 外頂點(diǎn)相鄰）以及簡單圖的定義可知，v0要達(dá)到其度數(shù)d(v0 )= (G),必須與上至少(G)個(gè)頂點(diǎn)相鄰，設(shè)其為vi1= v1, vi2, vi于是，圈v0vi1, vi2 ,vi v0,長度大于或等于(G)+1，式中=(G) ，參見例14.8,作業(yè)講評,14-25 畫出5階3條邊的所有非同構(gòu)的無向簡單圖 解：3條邊產(chǎn)生6度，分配給5個(gè)頂點(diǎn)，按簡單圖度數(shù)的要求，有4種分配方案： (1) 1,1,1,1,2 (2) 0,1,1,2,2 (3) 0,1,1,1,3 (4) 0,0,2,2,2 在同構(gòu)意義下，每種方案對應(yīng)一個(gè)簡單

5、圖，4個(gè)非同構(gòu)的圖如下圖實(shí)線邊所示：,作業(yè)講評,14-29 設(shè)G是n階n+1條邊的無向圖，證明G中存在頂點(diǎn)v，使得d(v)=3 解: 反證法 假設(shè)不然， v V(G),均有d(v)=2,則由握手定理可得 2n+2=2m=2n,其中m為邊數(shù) 這顯然是矛盾的。,作業(yè)講評,14-43 有向圖D，如圖所示 (1) D中有多少種非同構(gòu)的圈？ 有多少種非同構(gòu)的簡單回路？ (2) 求a到d的短程線和距離d (3) 求d到a的短程線和距離d 解:(1)有2種非同構(gòu)的圈:ede, aeba,長度分別為2與3; 有3種非同構(gòu)的簡單回路:ede, aeba, aedeba, 長度分別為2，3，5 (2) a到d的短

6、程線為aed, d=2 (3) d到a的短程線為deba, d=3,作業(yè)講評,14-43 (4) 判斷D中是哪類連通圖？ (5) 對D的基圖求解(1),(2),(3) 解:(4)D中存在經(jīng)過每個(gè)頂點(diǎn)的 通路，但不存在經(jīng)過每個(gè)頂點(diǎn)的 回路，所以D是單向連通圖。 (5)I. D的基圖中有4種非同構(gòu)的圈: ede, aeba, aedba, aedcba，長度分別為2，3，4，5，有7種非同構(gòu)的簡單回路，其中除4種非同構(gòu)的圈之外，還有3種非圈的簡單回路:aedeba, aebdcba, aedebdcba, 長度分別為5，6，8； II. a到d的短程線有3條，d =2III.d到a的短程線有3條，

7、d =2,作業(yè)講評,14-44 有向圖如圖所示， (1)D中v1到v4長度為1,2,3,4的通路各為幾條? (2) D中v1到v1長度為1,2,3,4的通路各為幾條? (3)D中長度為4的 通路有多少條，其中長為4的回路為多少條？ (4)D中長度小于或等于4的通路為多少條？其中多少條為回路？ (5)寫出D的矩陣。,作業(yè)講評,14-44 解：利用D的鄰接矩陣的前4次冪,作業(yè)講評,(1)v1到v4長度為1,2,3,4的通路數(shù)分別為0,0,2,2. 即a14=0, a14(2)=0, a14(3)=2, a14(4)=2 其中只有長度為4的兩條是非初級的簡單通路（定義意義下），見下圖所示.,作業(yè)講評

8、,(2) v1到v1長度為1,2,3,4的回路數(shù)分別為1,1,3,5.即a11=1, a11(2)=1, a11(3)=3, a11(4)=5 其中長度為1的是初級的(環(huán))；長度為2的是復(fù)雜的；長度為3的中有1條是復(fù)雜的，2條是初級的；長度為4的有1條是復(fù)雜的，有4條是非初級的簡單回路. (3)D中長度為4的通路為44條（即A4中元素之和），其中有11條是回路（即A4中對角線元素之和）。,作業(yè)講評,14-44解： (4) D中長度小于或等于4的通路為88條（即A，A2，A3，A4中元素之和），其中有22條是回路（即A，A2，A3，A4中所有對角線元素之和）（5）因?yàn)镈中存在經(jīng)過所有頂點(diǎn)的回路，

9、是強(qiáng)連通圖，所以可達(dá)矩陣為4階全1方陣。,作業(yè)講評,15-1 判斷圖15-12中哪些是歐拉圖？對不是歐拉圖的至少要加多少條邊才能成為歐拉圖？ 解：(a) (c)為歐拉圖，它們均連通且都無奇度頂點(diǎn)。 (b)(d)都不是歐拉圖。(b)雖然無奇度頂點(diǎn)，但不連通；(d)既不連通、又有奇度頂點(diǎn)。 要使(b)(d)變?yōu)闅W拉圖均至少加兩條邊，使其連通并且無奇度頂點(diǎn)。,作業(yè)講評,15-11 彼得松圖既不是歐拉圖也不是哈密頓圖，至少加幾條邊才能使它成為歐拉圖，又至少加幾條新邊才能使它變成哈密頓圖？ 解：彼得松圖是10階3-正則圖，要想消除所有奇數(shù)頂點(diǎn)，至少加5條邊，才能使其變成所有頂點(diǎn)都是4度的頂點(diǎn)，成為歐拉圖

10、。如(a)(b)所示。 彼得松圖是半哈密頓圖，因而只需加一條新邊就可以得到哈密頓圖，如圖(c)所示。,作業(yè)講評,15-13 今有2k(k=2)個(gè)人去完成任務(wù)，已知每個(gè)人均能與另外k個(gè)人中的任何人組成一組（每組2個(gè)人）完成他們共同熟悉的任務(wù),問這2k個(gè)人能否分成 k組，每組完成一項(xiàng)他們共同熟悉的任務(wù) 解：做2k個(gè)無向簡單圖G=,其中，V=v|v為去完成任務(wù)的人，E=(u.v)|u,vV,u!=v且u與v有共同熟悉的任務(wù)，根據(jù)題設(shè)u,vV,有 d(u)+d(v)=2k 由定理15.7可知，G中存在哈密頓通路，設(shè)C=vi1vi2vi2k為G的一條哈密頓通路，則在C上相鄰的頂點(diǎn)均有共同熟悉的任務(wù)，于是

11、，沿通路將相鄰的兩個(gè)人各組成小組，則每個(gè)小組的兩個(gè)人都能去完成他們共同的任務(wù)。,作業(yè)講評,15-21 用DijKstra標(biāo)號(hào)法求下述圖中從頂點(diǎn)v1到其各頂點(diǎn)的最短路徑和距離。,15.3 最短路問題與貨郎擔(dān)問題,15-21(a)Dijkstra求解過程,15.3 最短路問題與貨郎擔(dān)問題,15-21(b)Dijkstra求解過程,最短路徑可能不唯一，如：v1v2v4v5和v1v2v5都是v1到v5的最短路徑，距離均為10。,作業(yè)講評,16-1 畫出所有5階和7階非同構(gòu)的無向樹。 解：方法步驟 (1) 計(jì)算總度數(shù)，n階無向樹的邊數(shù)m=n-1，由握手定理可知頂點(diǎn)度數(shù)總和 (2) 構(gòu)造可能的度數(shù)列，將2

12、n-2劃分成n份，第i份為對應(yīng)頂點(diǎn)vi的度數(shù)d(vi)， 且在這個(gè)數(shù)中奇偶數(shù)個(gè)； 按每個(gè)度數(shù)列畫樹，按不同的度數(shù)畫出的樹都是不同構(gòu)的，對同一個(gè)度數(shù)列可能畫畫出非構(gòu)的樹。,作業(yè)講評,16-1 解: (1) 5階無向樹，n=5, m=4,度數(shù)之和為8，劃分成5份有3種方案： 1) 1，1，1，1，4 2) 1，1，1，2，3 3) 1，1，2，2，2,作業(yè)講評,16-1 解： (2) 7階無向樹，n=7, m=6,度數(shù)之和為12，劃分成7份有7種方案： 1) 1,1,1,1,1,1,6 有1棵非同構(gòu)樹 2) 1,1,1,1,1,2,5 有1棵非同構(gòu)樹 3) 1,1,1,1,1,3,4 有1棵非同構(gòu)

13、樹 4) 1,1,1,1,2,2,4 有2棵非同構(gòu)樹 5) 1,1,1,1,2,3,3 有2棵非同構(gòu)樹 6) 1,1,1,2,2,2,3 有3棵非同構(gòu)樹 7) 1,1,2,2,2,2,2 有1棵非同構(gòu)樹,作業(yè)講評,16-2 一棵無向樹T有5片樹葉，3個(gè)2度分支點(diǎn)，其的分支點(diǎn)都是3度頂點(diǎn)，問T有向個(gè)頂點(diǎn)？ 解：設(shè)3度頂點(diǎn)為x個(gè)，則階數(shù)n=5+3+x=8+x, 邊數(shù)m=7+x,由握手定理2m=14+2x=5*1+3*2+3x=11+3x 解得x=3，故n=8+3=11,作業(yè)講評,16-13 在下面兩個(gè)正整數(shù)數(shù)列中，哪個(gè)（些）能充當(dāng)無向樹的度數(shù)列？若能，請畫出3棵非同構(gòu)的無向樹 （1）1,1,1,1,2,3,3,4 （2）1,1,1,1,2,2,3,3 解： （1）不能，若能，則階數(shù)n=8,m=7,度數(shù)之和應(yīng)為14，而此數(shù)列之和為16 （2）能。,作業(yè)講評,16-7 證明：n(n=2)階無向樹不是歐拉圖。 證明： 當(dāng)n=2時(shí)，無向樹T至少有2片樹葉，樹葉是奇度頂點(diǎn)， 故T不可能為歐拉圖。,作業(yè)講評,16-25 求圖16.17中兩個(gè)帶權(quán)圖的最小生成樹。 解： a:W(T)=27 b:W(T)=14,作業(yè)講評,16-31 根樹T如圖16.18所示，回答以下問題： (1) T是幾叉樹？ (2) T的樹高為幾 (