離散數(shù)學(xué)課后答案

P146習(xí)題9.1

9.1.1解：⑴幾何圖表示如右。

⑵deg(vj=3deg(v2)=4deg(v3)=3deg(v4)=3/

V3

deg(v5)=ldeg(v6)=0奇度數(shù)結(jié)點(diǎn)數(shù)為4?！?/p>

⑶(v2,v2)為自環(huán)；(Vl,V3)與(v3,Vi)為平行邊；

(V4,V5)為懸掛邊；V5為懸掛點(diǎn)；V6為孤立點(diǎn)。該圖為偽圖。V5A

9.1.2證：⑴n個結(jié)點(diǎn)的所有圖中，完全圖邊數(shù)最多。V

每點(diǎn)n-1度，n個點(diǎn)的總度數(shù)為：2m=￡deg(%)=n(nT)m=n(n-l)/2

n個結(jié)點(diǎn)的任一圖的邊數(shù)W完全圖的邊數(shù)，mWn(n-l)/2

⑵：在簡單有向完全圖中，任二點(diǎn)之間有兩條方向相反的邊，

/.每點(diǎn)的度數(shù)為2(n-1),.?.總度數(shù)為2m=2(n-L)n,m=n(n-l)o

9.1.3解：⑴去掉v點(diǎn)后，有nT個結(jié)點(diǎn)，m-d條邊。

⑵去掉e邊后，有n個結(jié)點(diǎn)，mT條邊。

9.1.4證：假設(shè)n個結(jié)點(diǎn)的度數(shù)皆不相同

在簡單無向圖中，一個結(jié)點(diǎn)的最大度數(shù)為n-1,最小度數(shù)為0。

它們只能為0,1,…，n-1n個值。

?/0度點(diǎn)不與其它任何結(jié)點(diǎn)相鄰，而n-1度點(diǎn)與其它任何結(jié)點(diǎn)相鄰，

，二者產(chǎn)生一個矛盾。X

⑶否。n個結(jié)點(diǎn)的簡單無向圖中，結(jié)點(diǎn)的最大度數(shù)為nT,5不可。

⑷否。后三點(diǎn)均與其它各點(diǎn)有邊，故第一點(diǎn)也應(yīng)三度。

⑸否。后二點(diǎn)均與其它各點(diǎn)有邊，故第一點(diǎn)至少應(yīng)為二度。

9.1.6解：2m=nkm=nk/2。

9.1.7證：⑴當(dāng)圖G中n個點(diǎn)的度數(shù)都為3(G)時(shí)，總度數(shù)為2m=nb(G)。

但一般情況下，5(G)為最小度數(shù)，而并非所有結(jié)點(diǎn)的度數(shù)都為3(G)時(shí)，

必有2m》n3(G),/.2m/n>8(G)。

(2)當(dāng)圖G中n個點(diǎn)的度數(shù)都為△&)時(shí)，總度數(shù)為2m=nA(G)

但一般情況下，△&)為最大度數(shù)，而并非所有結(jié)點(diǎn)的度數(shù)都為△4)時(shí)，

必有2m^nA(G),2m/n^A(G)。X

P148習(xí)題9.2

9.2.1解：同構(gòu)的只給出其一。

(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)

補(bǔ)圖對表

(16)(15)?(11)(13)(14)皆為自補(bǔ)圖

9.2.2解:

H的補(bǔ)圖H相對于G的補(bǔ)圖

9.2.3解:

9.2.4解:

⑴

四點(diǎn)的自補(bǔ)圖五點(diǎn)的自補(bǔ)圖

⑵不存在3個結(jié)點(diǎn)或6個結(jié)點(diǎn)的自補(bǔ)圖，因?yàn)樗麄兊耐耆珗D邊數(shù)為奇數(shù)。

⑶證明：設(shè)結(jié)點(diǎn)數(shù)和邊數(shù)分別為n和m。

有n個結(jié)點(diǎn)的自補(bǔ)圖，則n個結(jié)點(diǎn)的完全圖邊數(shù)必為偶數(shù)，

:.m=2ttel+,又■:完全圖邊數(shù)m=n(n-l)/2,/.n(n-l)=4t；

若n為偶數(shù),則n-1必為奇數(shù)，n必為4的倍數(shù)，,n=4k,keL,

若n為奇數(shù),n必為4的倍數(shù)，.，.n-l=4k,/.n=4k+l,kel+。X

“，?fl2345678910

9.2.5證：⑴構(gòu)造置換f：V-V,f=

ab(12341059857

⑵經(jīng)驗(yàn)證，V(x,y)eEa,(f(x),f(y))eEb,反之亦然。

根據(jù)同構(gòu)的定義，兩圖同構(gòu)。X

9.2.6證：假設(shè)兩圖同構(gòu)，根據(jù)前面介紹的兩途同構(gòu)的必要條件，

在(a)中只有1和2兩點(diǎn)間有平行邊，在(b)中只有2和3兩點(diǎn)間有平行邊,

所以必然是(a)中的1和2兩點(diǎn)與(b)中的2和3兩點(diǎn)相對應(yīng)。

又因在(a)中1點(diǎn)4度，2點(diǎn)3度，在(b)中2點(diǎn)3度，3點(diǎn)4度，

所以必然是(a)中2點(diǎn)對應(yīng)(b)中2點(diǎn)，(a)中1點(diǎn)對應(yīng)(b)中3點(diǎn)。

又在(a)中1點(diǎn)的3個鄰接點(diǎn)的度數(shù)皆不超過3度，而在⑹中3點(diǎn)與4度點(diǎn)4鄰接,

故出現(xiàn)了矛盾。所以原命題成立。

9.2.7證：因四個結(jié)點(diǎn)兩條邊的無向簡單圖，只有兩種非同構(gòu)的狀態(tài),

一種是這兩條邊鄰接，另一種是這兩條邊不鄰接，如右圖所示。

所三個這樣的圖，必至少有兩個圖同構(gòu)。X(a)(b)

P151習(xí)題9.3

9.3.1解：各舉一例。

長度為9的跡長度為8的不是徑的跡長度為5的圈

長度為6的圈長度為8的圈長度為9的圈:

（Vi,V2）或（V4,V1）均可。

9.3.5證：若從u到v存在徑，則因徑是跡，所以從u到v存在跡。

若從U到V存在跡，

⑴跡上點(diǎn)不重復(fù)，則該跡即為徑。

（2）跡上有重復(fù)的點(diǎn)，如：u…ab…a…v,則將b…a這段路去掉，得到的仍是從u到v

的跡。如果還有重復(fù)結(jié)點(diǎn)，則繼續(xù)重復(fù)作上述刪除工作，直到跡上沒有重復(fù)的點(diǎn)，便得到從u

到v的徑。X

P165習(xí)題9.4

9.4.1解：

(1)V1-*V10；V1-*V21；V]-*V33；V1-V42；

V1—V56;VLV64;VLV77;V1—V85;V9-V90

⑵D=8

⑶弱分圖：{vi,V2,v3,V4,V5,v6,V7,V8,Viol,{vj

單分圖：{vi,V2)V3,V4,V5)V6)V7,V8},{v5,V7)V8)Vifl},{v9}

強(qiáng)分圖：{vi,V2,V3,V4,V6),{v5,V7,V8},{v9},{vto}

94.2解:%在Vi到Vk的短程線上。

9.4.3反證：假設(shè)兩個奇度數(shù)結(jié)點(diǎn)u和v之間無路

則結(jié)點(diǎn)u和v必分居于兩個不同的連通分支中，

于是u所在的連通分支中，奇度數(shù)結(jié)點(diǎn)的數(shù)目為1,與定理9.1-1的推論1矛盾！

9.4.4見P172,定理9.18的證明。

9.4.5反證：假設(shè)5(G)^0o

設(shè)|V|=no任取一點(diǎn)，???8(G)#0,/.該點(diǎn)至少有一入度。沿提供入度的邊反向走到該

邊的起點(diǎn)。又因該點(diǎn)也至少有一入度，再沿提供入度的邊反向走到該邊的起點(diǎn)。如此走下去，

不外乎兩種結(jié)果：①再向前走便回到已走過的點(diǎn)上，形成回路。②一路上走全了所有點(diǎn)，但

因最后一點(diǎn)仍有入度，再向前走必然回到已走過的點(diǎn)上，形成回路。兩種情況都存在回路，與

前提無回路矛盾。X

P168習(xí)題9.5

0101

9.5.1解：⑴A=°°11⑵3條。⑶0條。⑷路65條。其中回路15條。

0101

0100

-10000-100oo-

1110001100

9.5.2解:p=11100P^pT=01100強(qiáng)分圖為：{vj,{v2,V3},{v.1,V5}。

1111100011

1111100011

9.5.3解：⑴ei62036465?6

Vir-i

V211-1

V3-11-1

V411-1

-11

J

(2)degin(vi)=l；degOut(vi)=0；degin(v3)=2；degout(v3)=l

⑶矩陣中所有元素絕對值之和為12,而邊數(shù)為6。

0121

9.5.4解:0001Idij=l說明從i點(diǎn)到j(luò)點(diǎn)存在一條邊。

00101

00120

9.5.5解：(1)將距離矩陣中8項(xiàng)置為0,將非8項(xiàng)置為1,便得到可達(dá)矩陣。

⑵非主對角線上的元素丸表示從一點(diǎn)Vi到另外一點(diǎn)V」的距離，該距離值不是8說明

從Vi到V」存在通路。非主對角線上的所有元素不為8,說明從任一點(diǎn)Vi到其它任

一點(diǎn)都有路相通，所以該圖是連通的。

9.5.6說明：⑴二元運(yùn)算八和V定義于右面的運(yùn)算表。鄧1VTo

⑵。為布爾陣的布爾乘法，定義如下：°；°0。

設(shè)A為n行k列布爾陣，B為k行m列布爾陣，1——1

則C=AOB為n行m列布爾陣，

?！竿馕?0

P-1

⑶V為布爾陣的并運(yùn)算，定義為：設(shè)X,Y,Z皆為n行m列布爾陣，

Z=XVY,Zij=XijAyij。

(4)。的一定義為:A°=I,An=An-*OA。

(5)。對V滿足分配律。令￡=人。①"0，D=BVC,R=AOB,S=AOC

kkk

eij=v(ajpAdpj)=v(ajpA(bpjV.))=.,(%Abpj)v(aipAc”))

kk

=v(aipAbpj)vv(aipAC^^IJVs^?

，E=RVS,即AO(BVC)=AOBVAOC

證：對n是以歸納證明。

當(dāng)n=l時(shí)，IVA=IVA

當(dāng)n=2時(shí)，(IVA)2=(IVA)O(IVA)=IOIVIOAVA0IVAG)A=I2VIOAVAOIVA2,

*/IOA=AOI=A,且101=1,且V運(yùn)算滿足嘉等律，二(IVA)2=IVAVA2,

假設(shè)當(dāng)n=k(keN,k23)時(shí)成立,即(IVA)k=IVAV…VA14,

當(dāng)n=k+l時(shí)，

(IVA)k+1=(IVA)kO(IVA)=((IVA)kOI)V((IVA)kOA)

=(IVA)kV((IVAV-VAk)OA)

=(IVAV-VAk)V(AVA2V-VAk+1)=IVAV-VAk+1派

P162習(xí)題9.6

9.6.1解：(a)否。：有4個奇度數(shù)結(jié)點(diǎn)。

(b)可。???所有結(jié)點(diǎn)皆為偶度數(shù)。

9.6.4(1)證：???G是歐拉圖，，是連通的。歐拉圖中必有歐拉回路，題9.6.3圖

，所有的點(diǎn)都在此回路上，.?.任兩點(diǎn)可互達(dá)，，該圖是強(qiáng)連通的。

⑵不一定是歐拉圖。右圖是強(qiáng)連通的，但不是歐拉圖。

9.6.5證：無向完全圖每個結(jié)點(diǎn)的度數(shù)為n-1,任兩個結(jié)點(diǎn)的度數(shù)之和為2n-2,

當(dāng)n22時(shí)，2n-22n。但注意n=2時(shí)不存在漢密爾頓回路，

當(dāng)n23時(shí)，根據(jù)推論9.5,無向完全圖必是漢密爾頓圖。X

9.6.6證：以人為結(jié)點(diǎn)，兩點(diǎn)之間有邊，表示兩人互相認(rèn)識，得到無向圖G=(V,E)。

(1)當(dāng)n=3,即V={a,b,c},a,b合起來認(rèn)識c,/.a,b至少有一人認(rèn)識c,不妨設(shè)a

認(rèn)識c；又?:a,c合起來認(rèn)識b,若a認(rèn)識b,則b-a-c為所求；若c認(rèn)識b,則b-c-a為所求。

⑵當(dāng)n24,Va,beV,Va,b合起來認(rèn)識其余n-2個人,:.deg(a)+deg(b)2n-2。

①若a與b互相認(rèn)識，則deg(a)+deg(b)2(n-2)+2=n?

②若a與b互相不認(rèn)識，則a認(rèn)識其余n-2個人，b也認(rèn)識其余n-2個人。

否則，若mdeV,a認(rèn)識d,b不認(rèn)識d,則a,d合起來不認(rèn)識b,與題給條件矛盾。

此種情況下，deg(a)+deg(b)=2(n-2)2n

根據(jù)推論9.5,存在漢密爾頓回路。

9.6.7證：任選兩個奇度數(shù)結(jié)點(diǎn)，在他們之間連一條邊，于是這兩個奇度數(shù)結(jié)點(diǎn)變成偶度數(shù)

結(jié)點(diǎn)。再選兩個奇度數(shù)結(jié)點(diǎn)，在他們之間連一條邊，顯然第二條外加邊與第一外加邊

不相鄰。在k個奇度數(shù)結(jié)點(diǎn)間共加入k/2條不相鄰的邊，使所有結(jié)點(diǎn)皆為偶度數(shù)結(jié)點(diǎn)。

根據(jù)推論9.3,存在一條歐拉回路。再將k/2條不相鄰的外加邊去掉，則必形成k/2

條不相鄰的跡。由于可把一條及分成多條跡，所以跡的總數(shù)2k/2。X

9.6.8解：(a)4筆；(b)2筆。

P166習(xí)題9.7

9.7.1解：是?；パa(bǔ)結(jié)點(diǎn)集如下圖。

9.7.2解:⑴VI每點(diǎn)至少2度，

V2中每點(diǎn)至多2度，t=2o

⑵見下表。

⑶匹配如右上圖。題9.7.1圖題9.7.2圖

st(S)ST(S)ST(S)

16,81,36,7,8,101,2,36,7,8,9,10

27,9,101,46,8,91,2,46,7,8,9,10

37,102,37,9,101,3,46,7,8,9,10

46,8,92,46,7,8,9,102,3,46,7,8,9,10

1.26,7,8,9,103.46,7,8,9,101,2,3,46,7,8,9,10

9.7.3解：如下圖。9.7.4解：如下圖。9.7.5解：如下圖。

&8,23.435比8-73gHgSio

9.7.6證：設(shè)|Vj=m,則|V2|=n-nio*.*完全二分圖時(shí)便數(shù)最多為m=|Vj|V21=ni(n-n。,

該式當(dāng)ni=n/2時(shí)有極大值n2/4，,m^n2/4。

P168習(xí)題9.8

9.8.1證：：每個面至少由k條邊圍成，，f個面至少由kf條邊圍成。

又；每條邊在計(jì)算面的邊界時(shí)都計(jì)了兩次，...總邊數(shù)m?kf/2。

又???平面圖的歐拉公式n-m+f=2,代入上式解得mWk(n-2)/(k-2)

9.8.2解

1

9.8.3證：⑴將粗紅筆所畫子圖的6,7兩點(diǎn)串聯(lián)合并后如右圖為K5。

...原圖存在與K5同胚子圖，根據(jù)庫氏定理原圖為非平面圖。

⑵如右圖，粗紅筆所畫子圖為K3.3,根據(jù)庫氏定理，,原圖為非平面圖。

9.8.4反證：假設(shè)G和不皆為平面圖

n點(diǎn)完全圖的邊數(shù)應(yīng)為m=n(n-l)/2.......①

G是平面圖，,G的邊數(shù)W3n-6。G是平面圖，二3的邊數(shù)W3n-6。

■n點(diǎn)完全圖的邊數(shù)=6的邊數(shù)+G的邊數(shù)，mW2(3n-6)=6n-12.......②

當(dāng)n?ll時(shí)，①式結(jié)果為m255,而②式結(jié)果為mW54,矛盾！證畢

9.8.5反證1：假設(shè)G不連通，有k22個連通分支:Gi,G2)-,Gk?

在G與G2，G2與G3與G4,…,Gk-i與Gk之間分別各加一條邊，

共加了kT條邊，于是新圖G，為連通的了，且仍為簡單平面圖。

/.m'=m+kTW3n-6,將n=7和m=15代入，得kWl,與k22矛盾！證畢

反證2：假設(shè)G不連通,有k22個連通分支：—2,…，Gk。

則每個連通分支均為簡單平面圖，miW3n「6,

m=(mi+ni2+…+nik)W(3n「6)+(3n2-6)+…+(3nk-6)

=3(ni+n2k+…+nk)-6k=3n-6k

將n=7和m=15代入，得kWl,與k22矛盾！證畢

9.8.6反證：假設(shè)存在邊界邊數(shù)24的面

:.m>3f/2,再與n-m+f=2聯(lián)立，解得m<3n-6o

將n=6代入，解得m<12,這與已知m=12矛盾！證畢

9.8.7證：對于2度點(diǎn)插入操作，點(diǎn)增加一個，邊也增加一條。

對于2度點(diǎn)消去操作，點(diǎn)減少一個，邊也減少一條。

對于2度點(diǎn)的操作，

按同胚的定義，若Gi與G2同構(gòu)，則ni=n2,mi=m2,mi-ni=m2-n2o

,,

若Gi通過2度點(diǎn)操作后得到GJ與G2同構(gòu)，ni-n2,?*.mi-ni=m2-n2，

mi,=mi+Ami,ni,=ni+Ani,(mi+Ami)-(ni+Ani)=m2-n2，

Am^Arii,/.m「ni=m2-n2。X

P170習(xí)題9.9

9.9.1解:

廣一

/

9.9.2解：黑圖的對偶圖為紅圖。

(1)黑色圖(a)到(b),點(diǎn)集之間的雙射為f(x)=x。

經(jīng)驗(yàn)證，邊之間的對應(yīng)關(guān)系也符合同構(gòu)的定義，故兩圖同構(gòu)。

(a)

(2)由于(b)的對偶圖，即紅圖中有一5度點(diǎn)

所以兩對偶圖不同構(gòu)。

9.9.3證：設(shè)圖G的對偶圖為G，，，G，是連通圖，且gfo

?.?圖G與圖。同構(gòu)，,G是連通圖，且n=M=fo

又???圖G有對偶，圖G是平面圖，加之G是連通圖，,n-f+m=2。

m=n+f-2=n+n-2=2n-2。證畢

9.9.5解:

9.9.6解：見上右兩圖。

9.9.7證：用數(shù)學(xué)歸納法證明。

當(dāng)nW6時(shí)顯然成立。

假設(shè)當(dāng)n=k是成立，keN,k?7。

當(dāng)n=k+l時(shí)，根據(jù)定理9.16,存在一點(diǎn)vdeg(v)W5。

將點(diǎn)v刪去得到圖G，，根據(jù)歸納假設(shè)，J可六色。

再將點(diǎn)v恢復(fù)，由于在G中與v鄰接的點(diǎn)不超過5個，并且有六種顏色，

故取與所有鄰結(jié)點(diǎn)不同的顏色給點(diǎn)v著色，二圖G仍是6色的。X

9.9.8證：⑴反證：假設(shè)所有結(jié)點(diǎn)度數(shù)都24,...G的總度數(shù)24n,即2m24n,m>2n0

G是簡單圖，I.不含自環(huán)和平行邊，二面的邊界不能由1條或2條邊構(gòu)成。

又?；G不含七,二面的邊界不能由3條邊構(gòu)成，即有至少4條邊構(gòu)成。

又G是連通的平面圖，根據(jù)推論9.7,mW2n-4,與m22n矛盾。

⑵證明方法與題9.9.7相同。X

P175習(xí)題9.10

9.10.1解：⑴設(shè)總結(jié)點(diǎn)數(shù)為n,1度結(jié)點(diǎn)數(shù)為n“邊數(shù)為m。

總度數(shù)為3X3+2X1+IXn)=2m

總結(jié)點(diǎn)數(shù)為n=3+1+n,

樹中點(diǎn)與邊的關(guān)系m=n-1

三式聯(lián)立解得n,=5o

9.10.2證：⑴反證：假設(shè)G不是一棵樹

???G是連通的，I.G必有回路。而刪去此回路中任一邊，圖仍連通。

這與每一邊都是割邊的前提條件矛盾！G是一棵樹。

⑵根據(jù)定理9.10-1(5),樹是連通的，但刪去任一邊便不連通了。

再根據(jù)割邊的定義，可知樹上任一邊都是割邊。證畢

kk

9.10.3解：(1)2m=2(n-1)=2(-1)=/??,，「?2(n1+n2+---+nki)=ni+2n2+---+knk)

；=1/=1

/.ni=n3+2n4+,--+(k-2)nk+2

kf(2—i)…

(2)(r-2)n.=V(2-i)n-2/.〃,,=?上---------。

)ir-2

9.10.4證：⑴：G是樹，...m=n-l,，總度數(shù)=2m=2(nT)=2n-2。X

⑵構(gòu)造算法：

①將個結(jié)點(diǎn)的度數(shù)從大到小排序，結(jié)果為：出,d2,…,d"。令i=l。

②畫出一個5度的點(diǎn)，以及與它鄰接的小個結(jié)點(diǎn)，及相應(yīng)的邊。

③i=i+l,若5=1,結(jié)束。

④將圖的任一葉結(jié)點(diǎn)變?yōu)?度結(jié)點(diǎn)，畫出與它鄰接的其它d「l個結(jié)點(diǎn)，

及相應(yīng)的邊。轉(zhuǎn)③。

證明：?.?構(gòu)造出的圖連通無回路，所以是樹。又因非葉結(jié)點(diǎn)都按要求度數(shù)實(shí)

現(xiàn)了，也結(jié)點(diǎn)的樹木必然也符合要求，該圖即為滿足各點(diǎn)度數(shù)條件的樹。

⑶例：(dbd2)d8)=(4,3,2,1,1,1,1,1)，n=8,di+d2+-+d8=14=2n-2。

9.10.5證：在T「｛a｝中，必形成兩個不連通的部分，用結(jié)點(diǎn)集表示為％和V?。

對于丁2來說，必存在連接％和Vz的邊，否則T?亦不連通，不妨設(shè)此邊為b。

,/a",，boa。又{a}中的任一邊都不在匕與V2之間,

T「{a}中的任一邊都不為任b打。

將b加入T「{a}中，于