離散課后習(xí)題答案

1、第十四章部分課后習(xí)題參考答案5、設(shè)無向圖 G 有 10 條邊，3 度與 4 度頂點(diǎn)各 2 個(gè)，其余頂點(diǎn)的度數(shù)均小于 3，問 G 至G、少有多少個(gè)頂點(diǎn)？在最少頂點(diǎn)的情況下，寫出度數(shù)列、解：由握手定理圖 G 的度數(shù)之和為： 2 10 = 20( ) (G) 。3 度與 4 度頂點(diǎn)各 2 個(gè)，這 4 個(gè)頂點(diǎn)的度數(shù)之和為 14 度。其余頂點(diǎn)的度數(shù)共有 6 度。其余頂點(diǎn)的度數(shù)均小于 3，欲使 G 的頂點(diǎn)最少，其余頂點(diǎn)的度數(shù)應(yīng)都取 2,所以，G 至少有 7 個(gè)頂點(diǎn), 出度數(shù)列為 3,3,4,4,2,2,2, () = 4 ,( ) = 2 .G G7、設(shè)有向圖 D 的度數(shù)列為 2，3，2，3，出度列為 1

2、，2，1，1，求 D 的入度列，并求(D), (D) ，+ (D),+ ( ) , D( D),(D) .解：D 的度數(shù)列為 2，3，2，3，出度列為 1，2，1，1，D 的入度列為 1,1,1,2.( ) = 3, ( ) = 2 , +D D(D) = 2, + ( ) = 1, D( D) = 2,( D) = 18、設(shè)無向圖中有 6 條邊，3 度與 5 度頂點(diǎn)各 1 個(gè)，其余頂點(diǎn)都是 2 度點(diǎn)，問該圖有多少個(gè)頂點(diǎn)？解：由握手定理圖 G 的度數(shù)之和為： 2 6 = 12設(shè) 2 度點(diǎn) x 個(gè)，則 3 1 + 5 1 + 2x = 12 ， x = 2 ，該圖有 4 個(gè)頂點(diǎn).14、下面給出的

3、兩個(gè)正整數(shù)數(shù)列中哪個(gè)是可圖化的？對(duì)可圖化的數(shù)列，試給出 3 種非同構(gòu)的無向圖，其中至少有兩個(gè)時(shí)簡(jiǎn)單圖。(1) 2,2,3,3,4,4,5(2)2,2,2,2,3,3,4,4 解：(1) 2+2+3+3+4+4+5=23是奇數(shù)，不可圖化；(2)22+2+2+3+3+4+4=16, 是偶數(shù)，可圖化；18、設(shè)有 3 個(gè) 4 階 4 條邊的無向簡(jiǎn)單圖 G1、G2、G3，證明它們至少有兩個(gè)是同構(gòu)的。證明：4 階 4 條邊的無向簡(jiǎn)單圖的頂點(diǎn)的最大度數(shù)為 3，度數(shù)之和為 8，因而度數(shù)列1為 2，2，2，2；3，2，2，1；3，3，1，1。但 3，3，1，1 對(duì)應(yīng)的圖不是簡(jiǎn)單圖。所以從同構(gòu)的觀點(diǎn)看，4 階 4

4、 條邊的無向簡(jiǎn)單圖只有兩個(gè)：所以，G1、G2、G3 至少有兩個(gè)是同構(gòu)的。20、已知 n 階無向簡(jiǎn)單圖 G 有 m 條邊，試求 G 的補(bǔ)圖 G 的邊數(shù) m 。 解： = n(n 1)m2m21、無向圖 G 如下圖(1)求 G 的全部點(diǎn)割集與邊割集，指出其中的割點(diǎn)和橋；(2) 求 G 的點(diǎn)連通度 k (G) 與邊連通度 (G) 。ae1e2debe5解：點(diǎn)割集: a,b,(d)e3e4c邊割集e2,e3,e3,e4,e1,e2,e1,e4e1,e3,e2,e4,e5k( ) = (GG) =1k23、求 G 的點(diǎn)連通度 (G) 、邊連通度 ( G) 與最小度數(shù) ( ) 。 Gk解： (G) = 2

5、 、 (G) = 3、 ( ) = 4G28、設(shè) n 階無向簡(jiǎn)單圖為 3-正則圖，且邊數(shù) m 與 n 滿足 2n-3=m 問這樣的無向圖有幾種非同構(gòu)的情況？3解： n = 2m得 n=6,m=9.2n 3 = m231、設(shè)圖 G 和它的部圖 G 的邊數(shù)分別為 m 和 m ，試確定 G 的階數(shù)。 解： m + m= n(n + 1)2 1 +得 n =1 + 8(m + m)245、有向圖 D 如圖(1)求 v2 到 v5 長(zhǎng)度為 1，2，3，4 的通路數(shù)；(2)求 v5 到 v5 長(zhǎng)度為 1，2，3，4 的回路數(shù)；(3)求 D 中長(zhǎng)度為 4 的通路數(shù)；(4)求 D 中長(zhǎng)度小于或等于 4 的回路

6、數(shù)；(5)寫出 D 的可達(dá)矩陣。v1v4v5v2v3解：有向圖 D 的鄰接矩陣為： 0000 10100 00002 02020 0 01011 1 ， A 01A = 000021013020 10100 00002 02020 = 0 20010 0 A020 20200 = 20 4 0000 00004 40400 4 = 00004 A 40400 0 04042A + A +3A + A 01 524 = 21 42 25215 522 215 522 425(1) v2 到 v5 長(zhǎng)度為 1，2，3，4 的通路數(shù)為 0,2,0,0；(2) v5 到 v5 長(zhǎng)度為 1，2，3，4

7、的回路數(shù)為 0,0,4,0；(3)D 中長(zhǎng)度為 4 的通路數(shù)為 32；(4)D 中長(zhǎng)度小于或等于 4 的回路數(shù) 10；311(4)出 D 的可達(dá)矩陣= 1P111 1 1 11 1 1 11 1 1 11 1 1 111 1 1第十六章部分課后習(xí)題參考答案1、畫出所有 5 階和 7 階非同構(gòu)的無向樹.2、一棵無向樹 T 有 5 片樹葉，3 個(gè) 2 度分支點(diǎn)，其余的分支點(diǎn)都是 3 度頂點(diǎn)，問 T 有幾個(gè)頂點(diǎn)?解：設(shè) 3 度分支點(diǎn) x 個(gè)，則5 1 + 3 2 + 3x = 2 (5 + 3 + x 1) ，解得 x = 3T 有 11 個(gè)頂點(diǎn)3、無向樹 T 有 8 個(gè)樹葉，2 個(gè) 3 度分支點(diǎn)，

8、其余的分支點(diǎn)都是 4 度頂點(diǎn)，問 T 有幾個(gè) 4度分支點(diǎn)？根據(jù) T 的度數(shù)列，請(qǐng)至少畫出 4 棵非同構(gòu)的無向樹。 解：設(shè) 4 度分支點(diǎn) x 個(gè)，則8 1 + 2 3 + 4x = 2 (8 + 2 + x 1) ，解得 x = 2度數(shù)列 444、棵無向樹 T 有ni幾片樹葉?(i=2，3，k )個(gè) i 度分支點(diǎn)，其余頂點(diǎn)都是樹葉，問 T 應(yīng)該有解：設(shè)樹葉片，則xini i + x 1 = 2 (ni+ x 1) ，解得 x = ( 2)ni + 2評(píng)論：2，3，4 題都是用了兩個(gè)結(jié)論,一是握手定理，二是 m = n 1至5、n(n3)階無向樹 T 的最大度 少為幾？最多為幾？解：2，n-16、

9、若 n(n3)階無向樹 T 的最大度 =2，問 T 中最長(zhǎng)的路徑長(zhǎng)度為幾？解：n-17、證明：n(n2) 階無向樹不是歐拉圖. 證明：無向樹沒有回路，因而不是歐拉圖。8、證明：n(n2) 階無向樹不是哈密頓圖. 證明：無向樹沒有回路，因而不是哈密頓圖。9、證明：任何無向樹 T 都是二部圖.證明：無向樹沒有回路，因而不存在技術(shù)長(zhǎng)度的圈，是二部圖。10、什么樣的無向樹 T 既是歐拉圖，又是哈密頓圖? 解：一階無向樹14、設(shè) e 為無向連通圖 G 中的一條邊， e 在 G 的任何生成樹中，問 e 應(yīng)有什么性質(zhì)?解：e 是橋15、設(shè) e 為無向連通圖 G 中的一條邊， e 不在 G 的任何生成樹中，

10、問 e 應(yīng)有什么性質(zhì)?解：e 是環(huán)23、已知 n 階 m 條的無向圖 G 是 k(k2)棵樹組成的森林，證明：m = n-k.； 證明：數(shù)學(xué)歸納法。k=1 時(shí), m = n-1，結(jié)論成立；設(shè) k=t-1(t-1 1 )時(shí)，結(jié)論成立，當(dāng) k=t 時(shí), 無向圖 G 是 t 棵樹組成的森林,任取兩棵樹，每棵樹任取一個(gè)頂點(diǎn)，這兩個(gè)頂點(diǎn)連線。則所得新圖有 t-1 棵樹，所以 m = n -（k-1）.所以原圖中 m = n-k得證。24、在圖 16.6 所示 2 圖中，實(shí)邊所示的生成子圖 T 是該圖的生成樹.(1)指出 T 的弦，及每條弦對(duì)應(yīng)的基本回路和對(duì)應(yīng) T 的基本回路系統(tǒng).5(2) 指出 T 的所

11、有樹枝， 及每條樹枝對(duì)應(yīng)的基本割集和對(duì)應(yīng) T 的基本割集系統(tǒng).(a)(b)圖 16.16解：(a)T 的弦：c,d,g,hT 的基本回路系統(tǒng): S=a,c,b,a,b,f,d,e,a,b,h,e,a,b,f,gT 的所有樹枝: e,a,b,fT 的基本割集系統(tǒng): S=e,g,h,a,c,d,g,h,b,c,d,g,h,f,d,g(b)有關(guān)問題仿照給出25、求圖 16.17 所示帶權(quán)圖中的最小生成樹.(a)(b)圖 16.17解：注：答案不唯一。37、畫一棵權(quán)為 3，4，5，6，7，8，9 的最優(yōu) 2 叉樹，并計(jì)算出它的權(quán).638.下面給出的各符號(hào)串集合哪些是前綴碼?A1=0，10，110，1111是前綴碼 A2=1，01，001，000 是前綴碼 A3=1，11，101，001，0011不是前綴碼 A4=b，c，aa，ac，aba，abb，abc是前綴碼 A5= b，c，a，aa，ac，abc，abb，aba不是前綴碼41.設(shè) 7 個(gè)字母在通信中出現(xiàn)的頻率如下:a: 35%b: 20% c: 15%d: 10% e: 10%f: 5%g: 5%用 Huffman 算法求傳輸它