離散數(shù)學(xué)第五版清華大學(xué)出版社習(xí)題解答

1、離散數(shù)學(xué)(第五版)清華大學(xué)生版社第7章習(xí)題解答7.1,(2)，,(5)都能構(gòu)成無向圖的度數(shù)列，其中除(5)外又都能構(gòu)成無向簡(jiǎn)單圖的 度數(shù)歹I.分析10非負(fù)整數(shù)列d,d ,L,d能構(gòu)成無向圖的度數(shù)列當(dāng)且僅當(dāng)n di為2nEi=1偶數(shù)，即d1,d2,L,dn中的奇數(shù)為偶數(shù)個(gè).(1) ,(2),(3),(5)中分別有4個(gè),0個(gè),4個(gè),4 個(gè)奇數(shù)，所以，它們都能構(gòu)成無向圖的度數(shù)列，當(dāng)然，所對(duì)應(yīng)的無向圖很可能是非簡(jiǎn) 單圖.而(4)中有3個(gè)奇數(shù)，因而它不能構(gòu)成無向圖度數(shù)列.否則就違背了握手定理 的推論.(5)雖然能構(gòu)成無向圖的度數(shù)列，但不能構(gòu)成無向簡(jiǎn)單度數(shù)列.否則，若存在無向 簡(jiǎn)單圖G,以1,3,3,3為

2、度數(shù)列，不妨設(shè)G中頂點(diǎn)為v1,v2,v3,v4,且d(vi)=1,于是 d(v2)=d(v3)=d(v4)=3.而v1只能與v2,v3,v4之一相鄰，設(shè)v1與v2相鄰，這樣一來， 除v2能達(dá)到3度外，v3,v4都達(dá)不到3度，這是矛盾的.在圖7.5所示的4個(gè)圖中,(1)以1為度數(shù)列，(2)以2為度數(shù)列，(3)以3為度數(shù)列，(4) 以4為度數(shù)列(非簡(jiǎn)單圖).設(shè)有幾簡(jiǎn)單圖D以2,2,3,3為度數(shù)列，對(duì)應(yīng)的頂點(diǎn)分別為v1,v2,v3,v4,由于d(v)=d+(v)+d_(v),所示,d+(v)-d-(v)=2-0=2,d+(v 尸d(v )-d-(v ) 11222=2-0=2,d+(v)=d(v)-

3、d-(v)=3-2=1,d+(v)=d(v)-d-(v)=3-3=033344481由此可知，D的出度列為 2,2,1,0凡滿足d+(v)=d-(v).請(qǐng)讀者畫出Ei Ei一個(gè)有向圖.以2,2,3,3為度數(shù)列J ,且以0,0,2,3為入度列，以2,2,1,0為出度列.D的入度列不可能為1,1,1,1.否則，必有出度列為 2,2,2,2(因?yàn)?d(v)=d+(v)+d-(v),)此時(shí)，入度列元素之和為 4,不等于出度列元素之和 8,這違背 握手定理.類似地討論可知，1,1,1,1也不能為D的出席列.不能.N階無向簡(jiǎn)單圖的最大度 A& n-俯這里的n個(gè)正整數(shù)彼此不同，因而這 n個(gè)數(shù)不能構(gòu)成無向簡(jiǎn)單

4、圖的度數(shù)列，否則所得圖的最大度大于 n,這與最大度應(yīng) 該小于等于n-1矛盾.(1) 16個(gè)頂點(diǎn).圖中邊數(shù) m=16，設(shè)圖中的頂點(diǎn)數(shù)為n.根據(jù)握手定理可知2m=32= n d(v)=2nEii=1所以,n=16.13個(gè)頂點(diǎn).圖中邊數(shù)m=21，設(shè)3度頂點(diǎn)個(gè)數(shù)為x,由握手定理有2m=42=3X 4+3x由此方程解出x=10.于是圖中頂點(diǎn)數(shù)n=3+10=13.(3)由握手定理及各頂點(diǎn)度數(shù)均相同，尋找方程224=nk的非負(fù)整數(shù)解，這里不會(huì)出現(xiàn)n,k均為奇數(shù)的情況.其中n為階級(jí)，即頂點(diǎn)數(shù),k為度 數(shù)共可得到下面10種情況.個(gè)頂點(diǎn) 度數(shù)為48.此圖一定是由一個(gè)頂點(diǎn)的24個(gè)環(huán)構(gòu)成，當(dāng)然為非簡(jiǎn)單圖.2個(gè)頂點(diǎn)，每

5、個(gè)頂點(diǎn)的度數(shù)均為24這樣的圖有多種非同構(gòu)的情況，一定為非簡(jiǎn)單圖.3個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為16.所地應(yīng)的圖也都是非簡(jiǎn)單圖.4個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為12.所對(duì)應(yīng)的圖也都是非簡(jiǎn)單圖.6個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為8,所對(duì)應(yīng)的圖也都是非簡(jiǎn)單圖.個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為 6.所對(duì)應(yīng)的非同構(gòu)的圖中有簡(jiǎn)單圖，也有非簡(jiǎn)單 圖.8212個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為 4.所對(duì)應(yīng)的非同構(gòu)的圖中有簡(jiǎn)單圖，也有非 簡(jiǎn)單圖.16個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為3,所對(duì)應(yīng)的非同構(gòu)白圖中有簡(jiǎn)單圖，也有非簡(jiǎn)單 圖.24個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為2.所對(duì)應(yīng)的非同構(gòu)白圖中有簡(jiǎn)單圖，也有非簡(jiǎn)單 圖.48個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度數(shù)均為1,

6、所對(duì)應(yīng)的圖是唯一的，即由24個(gè)K2構(gòu)成的簡(jiǎn) 單圖.分析 由于n階無向簡(jiǎn)單圖G中，AG( ) &n-1的以-所對(duì)應(yīng)的圖不可能有簡(jiǎn) 單圖.-既有簡(jiǎn)單圖 也有非簡(jiǎn)單圖，讀者可以畫出若干個(gè)非同構(gòu)的圖，而只能 為簡(jiǎn)單圖.設(shè)G為n階圖，由握手定理可知70=2X35= n d(v) 3n, E 1i=1所以，?70?n0 =23.?3?70?這里，？ 6 (G)=n可是由于 G為 簡(jiǎn)單圖，因而AG( ) &n-1這又使得d(v) &n-仔是d(v)=n-1,也就是說,G中每個(gè)頂 點(diǎn)的度數(shù)都是n-1,因而應(yīng)有AG( )&n-1于是G為(n-1)階正則圖，即G為n階完 全圖Kn.由G的補(bǔ)圖G的定義可知，GUG為

7、Kn,由于n為奇數(shù)，所以，Kn中各項(xiàng)頂點(diǎn)的 度數(shù)n-1為偶數(shù).對(duì)于任意的v V(G),應(yīng)有v V(G),且 dG(v)_d (v)=dK (v)=n-1Gn83其中dG(v)表示v在G中的度數(shù)，d (v)表示v在G中的度數(shù).由于n-1為偶G數(shù)，所以，dG(v)與d (v)同為奇數(shù)或同為偶數(shù)，因而若G有r個(gè)奇度頂點(diǎn)，則G也有r個(gè)奇度頂點(diǎn).由于D?D,所以,m 0而n階有向簡(jiǎn)單圖中，邊數(shù)n(n-1),所以，應(yīng)有 n(n-1)=m n則至少存在一巢飛入至少m只n鴿子.這里？彼示不小于x的最小整數(shù).例如，?2?=2,?2.5?=3.G是唯一的，即使G是簡(jiǎn)單圖也不唯一.85分析由握手定理可知2m=3n,

8、又由給的條件得聯(lián)立議程組?2m=3n ?2n-3=m. ?解出n=6,m=9.6個(gè)頂點(diǎn),9條邊,每個(gè)頂點(diǎn)的度數(shù)都是3的圖有多種非同構(gòu)的情況, 其中有多個(gè)非簡(jiǎn)單圖(帶平行邊或環(huán))，有兩個(gè)非同構(gòu)的簡(jiǎn)單圖，在圖7.8中(1),(2) 給出了這兩個(gè)非同構(gòu)的簡(jiǎn)單圖.滿足條件的非同構(gòu)的簡(jiǎn)單圖只有圖7.8中,(1),(2)所示的圖，(1)與(2)所示的圖,(1)與(2)是非同構(gòu)的.注意在(1)中不存在3個(gè)彼此相鄰的頂點(diǎn)，而在(2)中存在3個(gè)彼此相鄰的頂點(diǎn)，因而(1)圖與(2)圖非同構(gòu).下面分析滿足條件的簡(jiǎn)單 圖只有兩個(gè)是非同構(gòu)的.首先注意到(1)中與 (2)中圖都是K6的生成子圖，并且還有這樣 的事實(shí)，設(shè)G

9、1,G2都是n階簡(jiǎn)單圖，則G1?G2當(dāng)且僅當(dāng)G1?G2,其中G1,G2分別為 G1與G2的補(bǔ)圖.滿足要求的簡(jiǎn)單圖都是6階9條邊的3正則圖，因而它們的補(bǔ)圖 都為6階6條邊的2正則圖(即每個(gè)頂點(diǎn)度數(shù)都是2).而K6的所有生成子圖中,6 條邊2正則的非同構(gòu)的圖只有兩個(gè)，見圖7.8中(3),(4)所示的圖，其中(3)為(1)的補(bǔ) 圖,(4)為(2)的補(bǔ)圖，滿足要求的非同構(gòu)的簡(jiǎn)單圖只有兩個(gè).但滿足要求的非同簡(jiǎn)單圖有多個(gè)非同構(gòu)的，讀者可自己畫出多個(gè)來.將K6的頂點(diǎn)標(biāo)定順序，討論v1所關(guān)聯(lián)的邊.由鴿巢原理(見7.13題)，與v1 關(guān)聯(lián)的5條邊中至少有3條邊顏色相同，不妨設(shè)存在3條紅色邊，見圖7.9中(1)所

10、 示(用實(shí)線表示紅色的邊)并設(shè)它們關(guān)聯(lián)另外3個(gè)頂點(diǎn)分別為v2,v4,v6.若v2,v4,v6 構(gòu)成的K3中還有紅色邊，比如邊(v2,v4)為紅色，則v1,v2,v4構(gòu)成的K3為紅色K3, 見圖7.9中(2)所示.若v2,v4,v6構(gòu)成的K3各邊都是藍(lán)色(用虛線表示)，則v2,v4,v6 構(gòu)成的K3為藍(lán)色的.86在圖7.10所示的3個(gè)圖中，(1)為強(qiáng)連通圖，(2)為單向連通圖，但不是強(qiáng)連通 的,(3)是弱連通的，不是單向連通的，更不是強(qiáng)連通的.分析 在(1)中任何兩個(gè)頂點(diǎn)之間都有通路，即任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，因 而它是強(qiáng)連能的.(2)中c不可達(dá)任何頂點(diǎn)，因而它不是強(qiáng)連通的，但任兩個(gè)頂點(diǎn)存

11、在一個(gè)頂點(diǎn)可達(dá)另外一個(gè)頂點(diǎn)，所以，它是單向可達(dá)的.(3)中a,c互相均不可達(dá)，因而 它不是單向連通的，更不是強(qiáng)連通的.判斷有向圖的連通性有下面的兩個(gè)判別法.1 0有向圖D是強(qiáng)連通的當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路.2。有向圖D是單向連通的當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路.(1)中abcda為經(jīng)過每個(gè)頂點(diǎn)一次的回路，所以,它是強(qiáng)連能的.(2)中abdc為經(jīng)過每 個(gè)頂點(diǎn)的通路，所以，它是單向連通的，但沒有經(jīng)過每個(gè)頂點(diǎn)的回路，所以，它不是強(qiáng) 連通的.(3)中無經(jīng)過每個(gè)頂點(diǎn)的回路，也無經(jīng)過每個(gè)頂點(diǎn)的通路，所以，它只能是弱 連通的.7.17 G-E的連通分支一定為2,而G-V”的連通

12、分支數(shù)是不確定的.分析 設(shè)E為連通圖G的邊割集，則G-E的連通分支數(shù)p(G-E)=2,不可”能大于2.否則，比如p(G-E)=3,則G-E由3個(gè)小圖G,G,G組成，且E中邊23的兩個(gè)端點(diǎn)分屬于兩個(gè)不同的小圖.設(shè)E”中的邊的兩個(gè)端點(diǎn)一個(gè)在G中,另一個(gè)87在G中，則E”？E,易知p(G-E”)=2,這與E為邊割集矛盾，所以，p(G-E)=2.但p(G-V,)不是定數(shù)，當(dāng)然它大于等于 2,在圖7.11中,V=u,v為(1)的點(diǎn)割集， p(G-V)=2,其中G為(1)中圖.V=v為(2)中圖的點(diǎn)割集，且v為割點(diǎn)，p(G-V)=4, 其中G為(2)中圖.7.18解此題，只要求出D的鄰接矩陣的前4次幕即可

13、.?0 1 1 0?11 0 1?0 0 020 1 1 0A=?員=?0 1 0 1?0 0 1?0 0 0 0?Z 0 0 1?1 1 1 1?l 2 1 2?31 1 0 141 1 1 1A =? =?0 1 1 1?1 1 0 1?0 0 0 1?/0 0 0 1?D中長(zhǎng)度為4的通路數(shù)為A4中元素之和，等于15,其中對(duì)角線上元素之和為3,即D中長(zhǎng)度為3的回路數(shù)為3.v到v的長(zhǎng)度為4的通路數(shù)等于a(4)=2.3434分析 用鄰接矩陣的幕求有向圖D中的通路數(shù)和回路數(shù)應(yīng)該注意以下幾點(diǎn)：1。這里所談通路或回路是定義意義下的，不是同構(gòu)意義下的.比如，不同始點(diǎn)(終點(diǎn)) 的回路2這里的通路或回路不

14、但有初級(jí)的、簡(jiǎn)單的，還有復(fù)雜的.例如,v1,v2,v1,v2,v1是一條長(zhǎng)為4的復(fù)雜回路.3?；芈啡匀豢闯墒峭返奶厥馇闆r.88讀者可利用A2,A3,求D中長(zhǎng)度為2和3的通路和回路數(shù).答案A:.分析 G中有Nk個(gè)k度頂點(diǎn)，有(n-Nk)個(gè)(k+1)度頂點(diǎn)，由握手定理可知n d(v)=k?N +(k+1)(n-N 尸2m ikki=1? Nk=n(k+1)-2n .答案 A:；B:.分析 在圖7.12中，圖(1)與它的補(bǔ)同構(gòu)，再?zèng)]有與圖(1)非同構(gòu)的自補(bǔ)圖了，所以非 同構(gòu)的無向的4階自補(bǔ)圖只有1個(gè).圖(2)與它的補(bǔ)同構(gòu)，圖(3)與它的補(bǔ)也同構(gòu)，而圖 與圖(3)不同構(gòu)，再?zèng)]有與(2),(3)非同構(gòu)

15、的自補(bǔ)圖了，所以，非同械的5階自補(bǔ)圖有2個(gè).答案 A:；B:；C:；D:.分析(1)中存在經(jīng)過每個(gè)頂點(diǎn)的回路，如adcba.(2沖存在經(jīng)過每個(gè)頂點(diǎn).的通路，但無回路.(3)中無經(jīng)過每個(gè)頂點(diǎn)至少一次的通路，其實(shí),b,d兩個(gè)頂點(diǎn)互不可 達(dá).(4)中有經(jīng)過每個(gè)頂點(diǎn)至少一次的通路，但無回路,aedcbd為經(jīng)過每個(gè)頂點(diǎn)的通 路.(5)中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路，如aedbcdba(6加也存在經(jīng).過每個(gè)頂點(diǎn)的回路，如baebdcb.由 7.16題可知，(1),(5),(6)是強(qiáng)連通 的,(1),(2),(4),(5),(6)是單向連能的，(2),(4)是非強(qiáng)連通的單向連通圖.注意，強(qiáng)連通圖 必為單向

16、連通圖.6個(gè)圖中，只有(3)既不是強(qiáng)連通的，也不是連通的，它只是弱連通 圖.在(3)中，從a到b無通路，所以d,= 物b到a有唯一的通路ba所以d=1. 7.22 答案A:；B:(十)C:；D:.89分析 用Dijkstra標(biāo)號(hào)法，將計(jì)算機(jī)結(jié)果列在表7.1中.表中第x列最后標(biāo)定y/Z表 示b到x的最短路徑的權(quán)為y,且在b到x的最短路徑上,Z鄰接到x,即x的前驅(qū) 元為Z.由表7.1可知,a的前驅(qū)元為c(即a令口接至ij c),c的前驅(qū)元為b,所以,b到a的 最短路徑為bca其權(quán)為4.類似地計(jì)論可知，b到c的最短路徑為bc,其權(quán)為1.b到d 的最短路徑為bcegd其權(quán)為9.b到e的最短路徑為bce

17、其權(quán)為7.表7.1頂點(diǎn) a b c d e f g k0 7 1 00 00 00 0004 00 5 4 001/b12 5 44/c12 5 4/c1112 5/c7 5 97/e69/g4 01 9 5 4 77.23 答案 A:；B: C:；D:和.再求最晚分析 按求最早、最晚完成時(shí)間的公式，先求各頂點(diǎn)的最早完成時(shí)間, 完成時(shí)間，最后求緩沖時(shí)間。再求最晚(1)最早完成時(shí)間：TE(v1)=0r -(v)=v,v, TE(v 尸max0+3=321 22r -(v 尸v,v, TE(v )=max0+2,3+0=331 33r -(v 尸v,v, TE(v )=max0+4,3+2=541

18、 34r -(v 尸v ,v, TE(v )=max3+4,3+4=752 35r -(v 尸v ,v, TE(v )=max3+4,7+0=763 6690r -(v )=v ,v,TE(v)=max5+5,10+0=1074 57r -(v 尸v,v,TE(v)=max7+3,10+1=1186 78r-(v 尸v ,v, TE(v )=max7+6,11+1=1395 89(2)最晚完成時(shí)間：TL(v9)=13r +(v 尸v, TL(v )=min13-1=12;898r +(v 尸v,TL(v 尸min12-3=9;686r +(v 尸v,TL(v )=min12-1=11;787

19、r +(v 尸v ,v, TL(v 尸min9-0,13-6=7;56 95r +(v )=v,TL(v )=min11-5=6;474r +(v )=v ,v ,v, TL(v 尸min6-2.7-4.9-4=5;34 5 63r +(v 尸v,v, TL(v 尸min3-0.7-4=3;23 52r +(v)=v ,v ,v,TL(v)=min3-3.3-2,6-4=0;12 3 41(3)緩沖時(shí)間：TS(v1)=TS(v2)=TS(v3)=TS(v5)=TS(v9)=0TS(v4)=1,TS(v6)=2,TS(v7)=TS(v8)=1.(4)關(guān)鍵路徑有兩條：v1,v2,v5,v9 和 v

20、1,v2,v3,v5,v9.91第8章習(xí)題解答圖8.6中,(1)所示的圖為K1,3,(2)所示的圖為K2,3,(3)所示的圖為K2,2，它們 分別各有不同的同構(gòu)形式.若G為零圖，用一種顏色就夠了，若G是非零圖的二部圖，用兩種顏色就夠了 . 分析 根據(jù)二部圖的定義可知,n階零圖(無邊的圖)是三部圖(含平凡圖)，對(duì)n階零 圖的每個(gè)頂點(diǎn)都用同一種顏色染色，因?yàn)闊o邊，所以，不會(huì)出現(xiàn)相鄰頂點(diǎn)染同色，因 而一種顏色就夠用了 .完全二部圖Kr,s,中的邊數(shù)m-rs.分析 設(shè)完全二部圖Kr,s的頂點(diǎn)集為 V, WJ V=V1UV2,V1IV2= ?，且|V1|二r,|V2|二s, Kr,s是簡(jiǎn)單圖，且V1中每

21、個(gè)頂點(diǎn)與V2中所有頂點(diǎn)相鄰，而且V1中任何兩個(gè)不同 頂點(diǎn)關(guān)聯(lián)的邊互不相同，所以，邊數(shù)m-rs.完全二部圖Kr,s中匹配數(shù)B 1=minr,s即B 1等于r,s中的小者.分析 不妨設(shè)0處二部圖Kr,s中,|V1|二r,|V2|二s，由Hall定理可知，圖中存在V1到 的完備匹配，設(shè)M為一個(gè)完備匹配，則V1中頂點(diǎn)全為M飽和點(diǎn)，所以，B1=r.能安排多種方案，使每個(gè)工人去完成一項(xiàng)他們各自能勝任的任務(wù).分析 設(shè)V1=甲乙，內(nèi)，則V1為工人集合，V2=a,b,c,則V2為任務(wù)集合.92令V=V1UV2,E=(x,y)|x能勝任y,得無向圖G=,則G為二部圖，見圖8.7 所示.本題是求圖中完美匹配問題.給

22、圖中一個(gè)完美匹配就對(duì)應(yīng)一個(gè)分配方案.圖8.7滿足Hall定理中的相異性條件，所以，存在完備匹配，又因?yàn)閨V1|=V2|二3，所以，完備匹配也為完美匹配.其實(shí),從圖上，可以找到多個(gè)完美匹配.取M1=(甲,a),(乙,b),(丙,c)此匹配對(duì)應(yīng)的方案為甲完成a,乙完成b,丙完成c,見圖中粗邊所示的匹配.M =(甲,b),(乙,a),(丙,c)M2對(duì)應(yīng)的分配方案為甲完成b,乙完成a,丙完成c.請(qǐng)讀者再找出其余的分配方案.本題的答案太多，如果不限定畫出的圖為簡(jiǎn)單圖，非常容易地給出4族圖分 別滿足要求.n (n為偶數(shù)，且n吩圈都是偶數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊白歐拉圖.n (n為奇數(shù)，且n1階圈都是奇數(shù)個(gè)頂點(diǎn)，奇

23、數(shù)條邊白歐拉圖.(3)在(1)中的圈上任選一個(gè)頂點(diǎn)，在此頂點(diǎn)處加一個(gè)環(huán)，所務(wù)圖為奇數(shù)個(gè)頂點(diǎn)，偶 數(shù)條邊的歐拉圖.分析 上面給出的4族圖都是連通的，并且所有頂點(diǎn)的度數(shù)都是偶數(shù)，所以,都是歐 拉圖.并且(1),(2)中的圖都是簡(jiǎn)單圖.而(3),(4)中的圖都帶環(huán)，因而都是非簡(jiǎn)單圖. 于是，如果要求所給出的圖必須是簡(jiǎn)單圖，則(3),(4)中的圖不滿足要求.其實(shí)，歐拉圖是若干個(gè)邊不重的圖的并，由這種性質(zhì)，同樣可以得到滿足(3),(4)中要 求的簡(jiǎn)單歐拉圖.設(shè)G1,G2,L,Gk是長(zhǎng)度大于等于3的k個(gè)奇圈(長(zhǎng)度為奇數(shù)的圈 稱為奇圈)，其中k為偶數(shù)，將G1中某個(gè)頂點(diǎn)與G2中的某頂點(diǎn)重合，但邊不重合，G2

24、中某頂點(diǎn)與G3中某頂點(diǎn)重合，但邊不重合，繼續(xù)地,最后將Gk-1中某頂點(diǎn)與Gk中 某頂點(diǎn)重合，邊不重合，設(shè)最后得連通圖為G,則G中有奇數(shù)個(gè)頂點(diǎn)，偶數(shù)條邊，且所 有頂點(diǎn)度數(shù)均為偶數(shù)，所以，這樣的一族圖滿足(4)的要求，其中一93個(gè)特例為圖8.8中所示.在以上各圖中，若G1,G2,L,Gk中有一個(gè)偶圈，其他條件 不變,構(gòu)造方法同上，則所得圖G為偶數(shù)個(gè)頂點(diǎn)，奇數(shù)條邊的簡(jiǎn)單歐拉圖，滿足(3) 的要求，圖8.8中(2)所示為一個(gè)特殊的情況.本題的討論類似于8.6題，只是將所有無向圈全變成有向圈即可，請(qǐng)讀者自己 畫出滿足要求的一些特殊有向歐拉圖.本題的答案也是很多的，這里給出滿足要求的最簡(jiǎn)單一些圖案，而且全

25、為簡(jiǎn)單 圖.n(n第3圄，它們都是歐拉圖，又都是哈密爾頓圖.(2)給定k(k 2)長(zhǎng)度大于等于3的初級(jí)回路，即圈G1,G2,L,Gk,用8.6題方法構(gòu) 造的圖G均為歐拉圖，但都不是哈密爾頓圖，圖8.8給出的兩個(gè)圖是這里的特例.(3)n(n 阱圈中，找兩個(gè)不相鄰的頂點(diǎn)，在它們之間加一條邊，所得圖均為哈密爾 頓圖，但都不是歐拉圖. 在(2)中的圖中，設(shè)存在長(zhǎng)度大于等于4的圈,比如說G1,在G1中找兩個(gè)不相鄰 的相鄰頂點(diǎn)，在它們之間加一條新邊，然后用8.6題方法才造圖G,則G既不是歐拉圖，也不是哈密爾頓圖，見圖8.9所示的圖.分析 (1)中圖滿足要求是顯然的.(2)中構(gòu)造的圖G是連通的，并且各頂點(diǎn)度

26、數(shù)均為偶數(shù)，所以,都是歐拉圖，但因?yàn)镚 中存在割點(diǎn)，將割點(diǎn)從G中刪除，所得圖至少有兩個(gè)連通分支，這破壞了哈密爾頓 圖的必要條件，所以,G不是哈密爾頓圖.(3)中構(gòu)造的圖中，所有頂點(diǎn)都排在一個(gè) 圈上，所以，圖中存在哈密爾頓回路，因而為哈密爾頓圖，但因圖中有奇度頂點(diǎn)(度數(shù) 為奇數(shù)的頂點(diǎn))，所以,不是歐拉圖.由以上討論可知，(4)中圖既不是歐拉94圖也不是哈密爾頓圖.其實(shí),讀者可以找許多族圖，分別滿足題中的要求.請(qǐng)讀者自己討論.其逆命題不真.分析 若D是強(qiáng)連通的有向圖，則D中任何兩個(gè)頂點(diǎn)都是相互可達(dá)的，但并沒有要 求D中每個(gè)頂點(diǎn)的入度都等于出度.在圖8.2所示的3個(gè)強(qiáng)連通的有向釁都不是 歐拉圖.除K

27、2不是哈密爾頓圖之外，Kn(n3)r是哈密爾頓圖.Kn(n為奇數(shù))為歐拉 圖.規(guī)定K1(平凡圖)既是歐拉圖，又是哈密爾頓圖.分析從哈密爾頓圖的定義不難看出，n階圖G是否為哈密爾頓圖，就看是否能將 G中的所有頂點(diǎn)排在G中的一個(gè)長(zhǎng)為n的初級(jí)回路，即圈上.Kn(n乎存在多個(gè) 這樣的生成圈(含所有頂點(diǎn)的圖),所以Kn(n3都是哈密爾頓圖.在完全圖Kn中，各頂點(diǎn)的度數(shù)均為n-1,若Kn為歐拉圖,則必有n-1為偶數(shù)，即n 為奇數(shù)，于是，當(dāng)n為奇數(shù)時(shí)，Kn連通且無度頂點(diǎn)，所以，Kn(n為奇數(shù))都是歐拉圖. 當(dāng)n為偶數(shù)時(shí)，各頂點(diǎn)的度數(shù)均為奇數(shù)，當(dāng)然不是歐拉圖.有割點(diǎn)的圖也可以為歐拉圖.分析 無向圖G為歐拉圖當(dāng)

28、且僅當(dāng)G連通且沒有奇度頂點(diǎn).只要G連通且無奇度 頂點(diǎn)(割點(diǎn)的度數(shù)也為偶數(shù)),G就是歐拉圖.圖8.8所示的兩個(gè)圖都有割點(diǎn)，但它們 都是歐拉圖.將7個(gè)人排座在圓桌周圍，其排法為abdfgeca .分析做無向圖G=,其中，V=a,b,c,d,e,f,gE=(u,v)|u,v C V且u與v有共同語言圖G為圖8.10所示.圖G是連通圖，于是，能否將這7個(gè)人排座在圓桌周圍，使得每 個(gè)人能與兩邊的人交談，就轉(zhuǎn)化成了圖G中是否存在哈密爾頓回路(也就是G是 否為哈密爾頓圖).通過觀察發(fā)現(xiàn)G中存在哈密爾頓回路，abdfgeca就是其 95中的一條哈密爾頓回路.用vi表示顏色i,i=1,2,L,6.做無向圖G=,

29、其中V=v1,v2,v3,v4,v5,v6,E=(u,v)|u,v C V 且 uwvf且 u 與 v 能搭配.對(duì)于任意的vCV,d(v)表示頂點(diǎn)v與別的能搭配的顏色個(gè)數(shù)，易知G是簡(jiǎn)單圖，且對(duì) 于任意的u,vCV,均有d(u)+d(v) 3+3=6,定理8.9可知,G為哈密爾頓圖，因而G 中存在哈密爾頓回路，不妨設(shè)vi vivivivivivi為其中的一條，在這種回1 2 3 4 5 6 1路上，每個(gè)頂點(diǎn)工表的顏色都能與它相鄰頂點(diǎn)代表的顏色相.于是，讓vi與vi ,vi123與vi ,vi與vi所代表的顏色相搭配就能織出3種雙色布，包含了 6種顏色.4568.15deg(R)=4,deg(R

30、)=1,deg(R )=3而 deg(R 尸12.3 deg(R)=20=2 10,本圖邊1230Eii=0數(shù) m=10.分析 平面圖(平面嵌入)的面Ri的次數(shù)等于包圍它的邊界的回路的長(zhǎng)度，這里所 說回路，可能是初級(jí)的，可能是簡(jiǎn)單的也可能是復(fù)雜的，還可能由若干個(gè)回路組成. 圖8.1所示圖中，R1,R2,R3的邊界都是初級(jí)回路，而R0的邊界為復(fù)雜回路(有的邊 在回路中重復(fù)出現(xiàn))，即e1e2e3e4e5e6e7e8e9e10e1e2e33度為12,其中邊 e5,e6 在其中各出現(xiàn)兩次.圖8.11中,實(shí)線邊所示的圖為圖8.1中圖G,虛線邊，實(shí)心點(diǎn)圖為它的96對(duì)偶圖的頂點(diǎn)數(shù)n*,邊數(shù)m*,面數(shù)r*分別

31、為4,10和8,于是有分析 從圖8.11還可以發(fā)現(xiàn),G的每個(gè)頂點(diǎn)位于的一個(gè)面中，且的每個(gè)面只含G的 一個(gè)頂點(diǎn)，所以，這是連通平面圖 G是具有k個(gè)連通分支的平面圖 k2則應(yīng)有 r*=n-k+1.讀者自己給出一個(gè)非連通的平面圖 ，求出它的對(duì)偶圖來驗(yàn)證這個(gè)結(jié)論 . 另外，用圖8.1還可以驗(yàn)證，對(duì)于任意的v*(G*中的頂點(diǎn))，若它處于G的面R中，則 應(yīng)有 d(v)=deg(R).*ii不能與G同構(gòu).分析 任意平面圖的對(duì)偶圖都是連通的，因而與都是連通圖，而G是具有3個(gè)連 通分支的非連通圖，連通圖與非連通圖顯然是不能同構(gòu)的.圖8.12中，這線邊圖為圖8.2中的圖G,虛線邊圖為G的對(duì)偶圖，帶小杠的*邊組成的

32、圖是G的對(duì)偶圖，顯然G wG.因?yàn)楸说蒙瓐D中有長(zhǎng)度為奇數(shù)的圈，根據(jù)定理8.1可知它不是二部圖.圖中每 個(gè)頂點(diǎn)的度數(shù)均為3,由定8.5可知它不是歐拉圖.又因?yàn)樗梢允湛s成 K5,由庫 拉圖期基定理可知它也不是平面圖.其實(shí)，彼得森圖也不是哈密爾頓圖圖，這里就不給出證明了 .97將圖8.4重畫在圖8.13中，并且將頂點(diǎn)標(biāo)定.圖中afbdcea為圖中哈密爾頓回 路，見圖中粗邊所示，所以該圖為哈密爾頓圖.將圖中邊(d,e),(e,f),(f,d)三條去掉，所得圖為原來圖的子圖，它為K3,3,可取 V1=a,b,c V2=d,e,f),由庫拉圖期基定理可知，該圖不是平面圖.圖8.14所示圖為圖8.5所示圖

33、的平面嵌入.分析 該圖為極大平面圖.此圖G中，頂點(diǎn)數(shù)n=9,邊數(shù)m=12若G是不是極.大平面圖，則應(yīng)該存在不相鄰的頂點(diǎn)u,v,在它們之間再加一條邊所得G還應(yīng)該是簡(jiǎn)單平面圖，G的頂點(diǎn)數(shù)n=n=6,m=n+1=13，于是會(huì)有 m=133n-6=12.這與定理8.16矛盾，所以,G為極大平面圖.其實(shí),n(n 濯)笥單平面圖G為極大平面圖當(dāng)且僅當(dāng)G的每個(gè)面的次數(shù)均為3.由 圖8.14可知,G的每個(gè)面的次數(shù)均為3,所以,G為極大平面圖.答案 A,B,C,D全為分析(1)只有n為奇數(shù)時(shí)命題為真，見8.11的解答與分析.nw 2時(shí)，命題為真，見8.11的解答與分析.(3)只有n,m都是偶數(shù)時(shí)，Kn,m中才無

34、奇度數(shù)頂點(diǎn)，因而Kn,m為歐拉圖，其他情況 下，即n,m中至少有一個(gè)是奇數(shù)，這時(shí)Kn,m中必有奇度頂點(diǎn)，因而不是歐拉圖.只有n=m時(shí)，Kn,m中存在 哈密爾頓回路，因而為哈密爾頓圖.當(dāng)nwm時(shí)，不妨設(shè)n|V1|=n,這與定理8.8矛盾.所以，n w附，Kn,m不是哈密爾頓98圖.答案A:;B;C.分析圖8.15中,兩個(gè)實(shí)邊圖是同構(gòu)的，但它們的對(duì)偶力(虛邊圖)是不同構(gòu)的.(2)任何平面圖的對(duì)偶圖都是連通圖.設(shè)G是非連通的平面圖，顯然有 *Gw G .(3)當(dāng)G是非連通的平面圖時(shí)，r*=n-k+1,其中k為G的連通分支數(shù).答案A:;B;C.分析 根據(jù)庫期基定理可知，所求的圖必含有K5或K3,3同胚

35、子圖，或含可收縮成 K5或K3,3的子圖.由于頂點(diǎn)數(shù)和邊數(shù)均已限定，因而由K3,3力口 2條邊的圖可滿 足要求，由K5增加一個(gè)頂點(diǎn)，一條邊的圖可滿足要求，將所有的非同構(gòu)的簡(jiǎn)單圖畫 出來，共有4個(gè),其中由K3,3產(chǎn)生的有2個(gè)，由K5產(chǎn)生的有2個(gè).見圖8.16所示.99第9章習(xí)題解答有5片樹葉.分析 設(shè)T有x個(gè)1度頂點(diǎn)(即樹葉).則T的頂點(diǎn)數(shù)n=3+2+x=5+x,T的邊數(shù) m=n-1=4+x.由握手定理得方程.2m=2(4+x)= n d(v)=3 3+2 2+1 ?x=13+x.E ii=1由方程解出x=5.所求無向樹T的度數(shù)列為1,1,1,1,1,2,2,3,3,3由這個(gè)度數(shù)列可以畫多棵非同

36、構(gòu)的無 向樹，圖9.6給出的4棵都具有上述度數(shù)列，且它們是非同構(gòu)的.T中有5個(gè)3度頂點(diǎn).分析 設(shè)T中有x個(gè)3度頂點(diǎn)，則T中的頂點(diǎn)數(shù)n=7+x,邊數(shù)m=n-1=6+x,由握手 定理得方程.2m=12+2x= n d(v)=3x+7Eii=1由方程解出x=5.所求無向樹T的度數(shù)列為1,1,1,1,1,2,2,3,3,3由這個(gè)度數(shù)列可以畫多棵非同構(gòu)的無 向樹，圖9.6給出的4棵都具有上述度數(shù)列，且它們是非同構(gòu)的.T中有5個(gè)3度頂點(diǎn).要析 設(shè)T中有x個(gè)3度頂點(diǎn)，則T中的頂點(diǎn)數(shù)n=7+x,邊數(shù)m=n-1=6+x,由 握手定理得方程.1002m=12+2x= n d(v)=3x+7.E i i=1 由此解

37、出x=5，即T中有5個(gè)3度頂.T的度數(shù)列為 1,1,1,1,1,1,1,3,3,3,3,3由于T中只有樹葉和3度頂 點(diǎn)用而3度頂點(diǎn)可依次相鄰，見圖9.7所示.還有一棵 與它非同構(gòu)的樹，請(qǐng)讀者自己畫出.加k-1條新邊才能使所得圖為無向樹.分析 設(shè)具有k個(gè)連通分支的森林為G,則G有k個(gè)連通分支T1,T2,LTK,Ti全為 樹,i=1,2,L,k.加新邊不能在Ti內(nèi)部加，否則必產(chǎn)生回路.因而必須在不同的小樹之 間加新邊.每加一條新邊后，所得到的森林就減少一個(gè)連通分支.恰好加k-1條新 邊，就使得圖連通且無回路，因而是樹.在加邊過程中，只需注意，不在同一人連通分 支中加邊.下面給出一種加邊方法，取vi

38、為Ti中頂點(diǎn)，加新邊(vi,vi+1)i=1,2,L,k-1, 則所得圖為樹，見圖9.8給出的一個(gè)特例.圖中虛線邊為新加的邊.不一定.分析 n階無向樹T具有n-1條邊，這是無向樹T的必要條件，但不是充公條件. 例如，階圈(即n-1個(gè)頂點(diǎn)的初級(jí)回路)和一個(gè)孤立點(diǎn)組成無向簡(jiǎn)單圖具有 n-1條 邊，但它顯然不是樹.非同構(gòu)的無向樹共有2棵，如圖9.9所示.101分析由度數(shù)列1,1,1,1,2,2,4不難看出，唯一的4度頂點(diǎn)必須與2度頂點(diǎn)相鄰，它與1個(gè)2度頂點(diǎn)相鄰，還是與兩個(gè)2度頂點(diǎn)都相鄰，所得樹是非同構(gòu)的，再?zèng)] 有其他情況.因而是兩棵非同構(gòu)的樹.有兩棵非同構(gòu)的生成樹，見圖9.10所示.分析 圖9.10

39、是5階圖(5個(gè)頂點(diǎn)的圖),5階非同構(gòu)的無向樹只有3棵，理由如下. 5階無向樹中，頂點(diǎn)數(shù)n=5,邊數(shù)m=4各頂點(diǎn)度數(shù)之和為8,度數(shù)分配方案有3種，分 別為1,1,1,1,4；1,1,1,2,3;1,1,2,2.2.每種方案只有一棵非同構(gòu)的樹.圖9.10所示的5階圖的非同構(gòu)的生成樹的度數(shù)列 不能超出以上3種，也就是說，它至多有3棵非同構(gòu)白生成樹，但由于圖中無4度 頂點(diǎn)，所示，不可能有度數(shù)列為的生成樹，于是該圖最多有兩棵非同構(gòu)的生成樹. 但在圖9.10中已經(jīng)找出了兩個(gè)非同構(gòu)的生成樹，其中(1)的度數(shù)列為,(2)的度 數(shù)列為，因而該圖準(zhǔn)確地有兩棵非同構(gòu)的生成樹.基本回路為：Cc=cbad,Ce=ead

40、,Cg =gfa,Ch =hfab .基本回路系統(tǒng)為Cc,Ce,Cg,Ch.基本割集為：Sa =a,e,c,g,h,Sb=b,c,h,Sd =d,e,cSf =f,g,h基本回路系統(tǒng)為Sa,Sb,Sd,Sf).分析1 0注意基本回路用邊的序列表示，而基本割集用邊的集合表示.1022基本回路中，只含一條弦，其余的邊全為樹枝，其求法是這樣的：設(shè)弦e=(vi,vj), 則vi,vj在生成樹T中，且在T中，vi,vj之間存在唯一的路徑 F i,j與e=(vi,vj)組成 的回路為G中對(duì)應(yīng)弦e的基本回路.3。基本割集中，只含一條樹枝，其余的邊都是弦，其求法是這樣的：設(shè)樹枝e=(vi,vj), 則e為T中

41、橋，于是T-e(將e從T中支掉),產(chǎn)生兩棵小樹T1和T2,則S =e|e在G中且e的兩端點(diǎn)分別在T和T中”e1 2Se為樹枝e對(duì)應(yīng)的基本割集.顯然eC Se,Se中另外的邊全是弦.注意，兩棵小樹 T1和T2,中很可能有平凡的樹(一個(gè)頂點(diǎn)).T-a得兩棵小樹如圖9.11中(1)所示.G中一個(gè)端點(diǎn)在Ti中,另一個(gè)端點(diǎn)在T2中 的邊為a(樹枝),e,c,g,h,它們?nèi)窍?，于是Sa =a,e,c,g,hT-b得兩棵小樹如圖9.11中(2)所示，其中有一棵為平凡樹.G中一個(gè)端點(diǎn)在T1 中,另一個(gè)端點(diǎn)在T2中的邊數(shù)除樹枝b外,還有弦c,h所以，Sb =b,c,hT-d產(chǎn)生的兩棵小樹如圖9.11中(3)所

42、示.G中一個(gè)端點(diǎn)在T1中,另中一個(gè)端點(diǎn)在T2中的邊，除樹枝d外，還有兩條弦c,e所示，Sd =d,c,eT-f產(chǎn)生的兩棵小樹如圖9.11中(4)所示.由它產(chǎn)生的基本割集為Sf =f,g,h.103按Kruskal求最小生成樹的算法，求出的圖9.3(1)的最小生成樹T為圖9.12中 (1)所示，其W(T)=7.(2)的最小生成樹 T為圖9.12中(2)所示，其W(T)=11 .B1,B2,B4為前綴碼.分析 在B1,B2,B4中任何符號(hào)用都不是另外符號(hào)用的前用，因而它們都是前綴碼 而在B3中，1是11,101的前綴，因而B3不是前綴碼.在B5中,a是aa,ac等的前 綴用而B5也不是前綴碼.由圖9.4 (1)給出的2元前綴碼.B1=00,0100,01010,011,11由(2)給出的