離散數(shù)學習題答案 （王慶先） 第6章 習題答案+代碼

第6章圖

6.4習題解析

1.畫出鄰接矩陣為4的無向圖G的圖形，其中

'01010、

11101

?!=01011

10101

、0111"

解鄰接矩陣為力的無向圖G的圖形如圖6.1所示。

圖6.1

2.畫出下列各圖的圖形，并判斷是有向圖、無向圖、混合圖、多重圖、線圖還是簡單圖。

(1)G\=<{a,b,c,d,^},{(a,b),(a,c),(d,e),{d,d),(b,c),(a,d),(b,a))>?

(2)G2—<{a,b,c,d,e},{<a,b>,<b,c>,<a,c>,<d,a>,<d,e>,<d,d>,<a,<?>}>?

(3)G?,=<{a,b,c,d,e},{{a,b),(a,c),<d,e>,<b,e>,<e,d>,<b,c>}>。

解(1)G］為無向多重圖，它的圖形如圖6.2(.)所示。

(2)G2為無向線圖，它的圖形如圖6.2g)所示。

(3)G3為混合簡單圖，它的圖形如圖6.2(c)所示。

3.設有向圖6=<-a，V={vi,V2，…，v,,},4=(劭)"X”為G的鄰接矩陣。

(1)如何利用A計算G中結點的出度、入度和度數(shù)？

(2)如何利用A計算G中所有結點的出度之和、入度之和和度數(shù)之和？

(3)如何利用A求G中長度為1的通路(含長度為1的回路)數(shù)？

解(1)G中結點憂的出度、入度和度數(shù)分別由下列式子計算

deg+(vi)=Eaik■deg-(vi)=Zaki-deg(Vi)=Z(aik+aG；

k=lk=lk=l

（2）G中所有結點的出度之和、入度之和和度數(shù)之和分別由下列式子計算

Zdeg+（v）=f￡X，^deg-（v）=XEaik,

veVi=lk=lvsVi=lk=l

a2a

Zdeg（v）=ZZSik+kj）=EEik

VGVi=lk=li=lk=l

（3）G中長度為1的通路（含長度為1的回路）數(shù)也就是G中的邊數(shù)，有握手定理得

|E|=；Zdeg（v）=；2支之ajk=之方an.

乙veV,i=lk=li=lk=l

4.設無向圖G有12條邊，已知G中度數(shù)為3的結點有6個，其余結點的度數(shù)均小于3。

問G中至少有多少個結點？為什么？

解由握手定理可知，G中所有結點的度數(shù)之和為24,去掉6個度數(shù)為3的結點的度數(shù)18

后,還有6度。而其余結點的度數(shù)均小于3,即其余結點的度數(shù)可為0、1、2,若其余

結點的度數(shù)均為2,則需3個結點來占用6度，所以G中至少有9個結點。

5.設G為9個結點的無向圖，每個結點的度數(shù)不是5就是6。試證明G中至少有5個度

數(shù)為6的結點或者至少有6個度數(shù)為5的結點。

證明由握手定理的推論可知，G中度數(shù)為5的結點只能是0、2、4、6、8個五種情況，

此時度數(shù)為6的結點分別為9、7、5、3、1個。以上五種情況都滿足至少有5個度數(shù)

為6的結點或者至少有6個度數(shù)為5的結點。

6.證明在具有〃個結點的簡單無向圖G中，至少有2個結點的度數(shù)相同（”》2）。

證明因為G是簡單圖，因此G中每個結點的度數(shù)均小于等于若G中所有結點的度

數(shù)均不相同，則”個結點的度數(shù)分別為0、1、2、3....止2、去掉G中孤立結點

得G的子圖Gy則Gi是具有小1個結點的簡單無向圖，其個結點的度數(shù)分別為

1、2、3....小2、n-\,即G］中有一個結點關聯(lián)"-1條邊，而中只有"-1個結點，從

而這”-1條至少有兩條為平行邊或至少有一條為自回路，故G］不是簡單圖，矛盾。

7.下面各圖中有多少個結點？

（1）16條邊，每個結點的度數(shù)均為2。

（2）21條邊，3個度數(shù)為4的結點，其余結點的度數(shù)均為3。

（3）24條邊，每個結點的度數(shù)均相同。

解設該圖的結點數(shù)為x,則由握手定理可知

(1)2xx=2xl6,x=16,故該圖有16個結點;

(2)3x4+3x(x-3)=2x21,x=13,故該有13個結點;

（3）假設每個結點的度數(shù)均為y,則有xy=2x24,它的正整數(shù)解（x,y）以下幾個

(1,48),(48,1)(2,24),(24,2),(3,16),(16,3),(4,12),(12,4),(6,8),(8,6),故該圖有

a）.2個（度數(shù)為24）結點;力.24個（度數(shù)為2）結點

c）.3個（度數(shù)為16）結點;16個（度數(shù)為3）結點

e）.4個（度數(shù)為12）結點;_/）.12個（度數(shù)為4）結點;

g）.6個（度數(shù)為8）結點；h）.8個（度數(shù)為6）結點。

i).1個(度數(shù)為48)結點;j).48個(度數(shù)為1)結點。

畫出圖6.3所示的圖的補圖。

圖6.3所示的圖的補圖如圖6.4所示。

試證明圖6.5中的兩個有向圖是同構的。

證明作｛“力?4為｝到｛1,2,3,4,5｝的映射/為人")=2,氏b)=3,心=4,火團=1,〃)=5。顯

然/是雙射,并且滿足對任意x,y,當＜x,y＞是(a)中的邊當且僅當勺(x),尸(y)＞是S)中的邊，

它們的重數(shù)也相同。

10.試證明圖6.6中的兩個圖不是同構的。

證明(。)中的4個度數(shù)為3的結點中的每一個均與另外兩個度數(shù)為3的結點相鄰，而3)中

每個度數(shù)為3的結點只與另外一個度數(shù)為3的結點相鄰，故它們不是同構的。

11.一個無向圖如果同構于它的補圖，則稱該圖為自補圖。

(1)給出所有具有4個結點的自補圖。

(2)給出所有具有5個結點的自補圖。

(3)證明一個自補圖一定有4Z或必+1(&GN)個結點。

解(1)圖6.7(0與它的補圖同構，所以它是具有4個結點的自補圖，此外再也沒有與它不

同構的具有4個結點的自補圖了；

(2)具有5個結點的非同構的自補圖只有兩個，它們分別是圖6.7(力和6.7(c)；

(3)若具有H個結點無向圖G是自補圖，則因G空G',因而G與G'邊數(shù)相同，設它

們的邊數(shù)為，蛇又因為G與G'的邊數(shù)之和為K“的邊數(shù)(小1),所以(〃一l)=2m,

22

即〃(〃-1)=4皿，因而〃為4的倍數(shù)，即〃=4公或者為4的倍數(shù)，即〃=4什1。

(b)

圖6.7

12.求完全圖K4的所有非同構的生成子圖。

解圖6.8中的11個圖是的所有非同構的生成子圖。

13.設無向圖G=(〃,/?)中每個結點的度數(shù)均為3,且滿足2〃-3=機，問在同構的意義下G

是唯一的嗎？

解G中每個結點的度數(shù)均為3,由握手定理可知，2加=3〃，將2”-3=加代入得方程3〃=

4m-6,于是得到"=6,%=9。在同構的意義下，G不是唯一的。因為6個結點9條邊

的圖可以有若干個非同構的圖。例如圖6.9所示的兩個圖均有6個結點9條邊，但它們

不同構。

14.給定圖G如圖6.10所示，求

Ao.

a

圖6.10

(1)從A到尸的所有簡單通路；

(2)從A到尸的所有基本通路；

(3)從A到尸的所有短程線和距離；

(4)G中的所有基本回路。

解(1)從A至F的所有簡單通路有ABEF,ABECF,ABCF,ABCEF,ADEF,ADECF,

ADEBCF,ADECBEF,ADEBCEF；

(2)從A至IJF的所有基本通路有ABEF,ABECF,ABCF,ABCEF,ADEF,ADECF,

ADEBCF；

(3)從A到尸的所有短程線有ABCF,ABEF,ADEF-,從A到尸的距離為3；

(4)G中的所有基本回路有ABCFEDA,ABCEDA,ABEDA,BCEB,BCFEB,CEFC。

15.求圖6.11所示的有向圖G的鄰接矩陣A,找出從H到以長度為2、3和4的所有通路,

用計算工、/和不來驗證結論。

圖6.11

解G中從打到V4長度為2的通路有叨叨丫4；叨丫3V4共2條。

G中從W到V4長度為3的通路有V1V1V1V4；V1V1V3V4；V1V4V1V4；丫"3丫"4共4條。

G中從打到丫4長度為4的通路有V1V1V1V1V4；V1V1V1V3V4；V1V1V4V1V4；V1V1V3V1V4；V1V3V4V1V4；

VIV3VIVIV4；V1V3V1V3V4；V1V4V1V3V4；V1V4V1V1V4；3V4共10條。

將G中結點按0V2V3V4排序，則G的鄰接矩陣為

U1ooj

'3112、’7234、'164710、

101131127234

A2=A3=A4=

2111512311357

k2011,<4123；J0346,

因此，*>=2,*)=4,*)=10,所以G中從W到W長度為2、3和4的通路分別

有2條、4條和10條。

16.(1)若無向圖G中只有兩個奇度數(shù)結點，則這兩個結點一定是相互可達的嗎？

(2)若有向圖G中只有兩個奇度數(shù)結點，則它們一定一個可達另一個或相互可達嗎？

解(1)設G中的兩個奇度數(shù)結點分別為"和辦若"與口不是相互可達的，即它們之間

無任何通路，則G至少有兩個連通分支Gi,G2,使得?與v分別屬于Gi和G2,于是Gi

和G2中各含有1個奇度數(shù)結點，這與握手定理的推論矛盾，因而"與V一定是相互可

達的。

(2)有向圖G中只有兩個奇度數(shù)結點"和也〃與v不一定相互可達，也不一定一個

可達另一個。例如G=<{“,v,w},中，結點"和v的度數(shù)均為1,w的

是為2,但〃不可達v,v也不可達人

17.分別用Dijkstra算法和Floyd算法求圖6.12所示無向賦權圖中也到次的最短通路。

圖6.12

解根據(jù)Dijkstra算法，有如圖6.13所示的求解過程。故vi到吟的最短通路為心3V2V5V7V9，

其長度為11。實際上，也求出了也到所有結點的最短通路，例如，％到也的最短通路

為也V3V2V5,其長度為6,等等。

圖6.13

根據(jù)FYoyd算法，有

’06320000000000、’0632000000008、

6020010000000060281CO000000

3202000000000032020000000000

200206100000002820610000000

(0,

D=001006010236,0⑴=001006010236

00000010100002000000001010000200

000000002000003000000002000003

0000000032000400000000320004

、800000060034產000000600340>

’063270000008、’053260000008、

60281000000005024100000000

32023000000003202300000000

28206100000002420510000000

那)=71360102366135010236

00oo0010100002000000001010000200

000000002000003000000002000003

0000000032000400000000320004

產00000060034產00000060034

'0532612000000、’05326128912、

50241140000005024111347

32023120000003202312569

242051000000024205107811

。⑷=6135010236,。⑸=6135010236

12141210100002CO1211121010012216

0000000020000038357212053

00000000320004946832504

產00000060034J2791161634

05326128911

5024111346

3202312568

24205107810

。⑹=。⑸6135010235

1211121010012215

8357212053

946832504

116810515340

'05326118911、

502416346

320238568

24205107810

/)=613505235，。(9)=。⑻

11681050726

835727053

946832504

J168105634

故V1到也的長度為11,其最短通路為V1V3V2WV7V9，其余類似。

18.設G是具有n個結點的簡單無向圖，如果G中每一對結點的度數(shù)之和均大于等于

止1,那么G是連通圖。

證明假設G不是連通圖，則G至少有兩個連通分支Gi,G2,設連通分支Gi中有m個結

點，G2中"2有個結點，分別從Gi和&中任取的一個結點"和小由于G

簡單圖,從而Gi和G2也是簡單圖,所以deg(“)W〃i-1,deg(v)<n2-1>故deg(u)+deg(v)

<n\-1+n2-1<n-2,與G中每對結點的度數(shù)之和大于等于〃-1矛盾。

19.〃個城市由上條公路連接(一條公路定義為兩個城市間的一條道路，不能經過任何中間

城市)。證明如果有

k>-(n-l)(n-2)

2

則人們總能通過連接城市的公路在任何兩個城市之間旅行。

證明將城市作為結點，將連接兩個城市的公路作為邊，則該問題等價于證明具有〃個結點

k條邊的簡單無向圖G是連通圖。當”=2時，結論顯然成立，下證〃>2時結論也成

-X-

假設G不連通，則可將G中的結點集V分為兩個子集修和匕，滿足匕=V,

v2=<p,并且■中的任何結點與L中的任何結點均不連通。設由口生成的G的

子圖G1中有m個結點ki條邊，由V2生成的G的子圖G1中n2有個結點k2條邊，則

n\+ti2=n,k\+kz=ko由于G是簡單無向圖，因此Gi和G?也是簡單無向圖，從而有女￡

11丁日

-ni(ni-l),左205〃2(改?1)，于7E

k=k\+k2=W—〃](，?]-1)H--〃2(〃2-l)

又由于

%>一(〃-l)(〃-2)=—。7]+相2-1)(〃1+〃2-2)

由于〃>2,因此川和〃2至少有一個大于等于2,不妨設2,由(2)得

111

k>一("|+"2-1)(〃1+"2-2)=-+〃2-2)H--(〃2-1)(〃I+"2-2)

>—nI(rtI-1)+—rt2(?2-1)

22

這與(1)式矛盾，故G是連通圖。

20.設“、w是無向連通圖G中的任意兩個結點，試證明若或"，卬)22,則存在結點也使

得d(u,v)+i/(v,vv)=</(?,w)。

證明由于G是連通圖，"，卬之間必存在短程線尸="必吃…味-1仍k>2,則4(“,w)=/,取v

為尸上除〃，卬外的任意一個結點都有

d(u,Vi)+d(vi,w)—d(u,w)=ko

事實上,〃用之間的短程線為P尸〃吸丫2…%,否則，若〃用之間存在比尸1短的短程線尸'|

—UU\U2...Vi，則P'—UU\U2...ViVi+\...Vk.lW比P短，這與P為U,W之間的短程線矛盾。同理可

證P2=ViVi+i...Vk.]W為環(huán)與W之間的短程線，因而d(",環(huán))+d(Vi,W)為P1的長度加上尸2的長

度，而Pl的長度加上尸2的長度為尸的長度，即為2,所以或〃,q)+d(w,w)=A=d(“,w)。

21.設無向圖G=<V,E>,|V]23,G是連通的簡單圖但不是完全圖，則G中存在三個不同

的結點〃、v>w,使得(〃,v)eE,(v,w)eE,而(〃,w)企E。

證明由于G是連通的簡單圖但不是完全圖，因此G中存在一個結點x,y,使得J(x,y)>2

(若對任意x,yCE,都有或x,y)=l,則G為完全圖)，設或x,y)=&,x,y之間的短程線

為尸=xw也…味-iy。下面證明X,V2之間的短程線為=*也也若不然，假設X,V2之間存在

比P1短的短程線P'1=XV2,則P=x也吟…3y比尸短，這與尸為x,y之間的短程線矛

盾。所以有(xm)GE,(也㈤GE,而(x,V2)諾及由于XM,V2是短程線上的結點,顯然它

們互不相同。

22.設e為無向圖6=<匕￡>中的一條邊，p(G)為G的連通分支數(shù)，G-e為從G中刪除邊

e后得到的圖。試證明p(G)Wp(G-e)Wp(G)+l。

證明設e屬于G的第i個連通分支G,(若G是連通圖，則Gi為G),e=(",v)。若e是G

中的某條基本回路“V…〃中的邊，則刪除e不會影響G的連通性，因而G的連通分支

數(shù)無變化，即p(G)=p(G-e)。若e不是Gi中的任何基本回路中的邊，則刪除e后，w與

n便不連通了，但原來與"之間存在不經過e的通路的結點之間仍然是連通的，原來與

v之間存在不經過e的通路的結點之間仍然是連通的，即Gi-e有且僅有兩個連通分支，

因而G-e比G多一個連通分支，即p(G-e)=p(G)+l。故有p(G)Wp(G-e)Wp(G)+l。

23.設有“、b、c、d、e、f、g七個人，他們分別會講如下語言a會講英語；人會講漢語和

英語；c會講英語、西班牙語和俄語；”會講日語和漢語；e會講德語和西班牙語；/會

講法語、日語和俄語；g會講法語和德語。試問這七個人中，是否任意兩個都能交談

（必要時可借助于其余五人組成的譯員鏈）？

解我們分別用結點表示將七個人和七種語言，若某人會講某種語言，則用一條無向邊將它

們連接起來，則上述問題就轉化為判斷圖6.14所示的無向圖是否為連通圖。顯然，該

為連通圖，故他們七個人中任意兩個都能交談。

圖6.14

24.在圖6=＜匕區(qū)＞中，對給定結點％若SUV中的每個結點都從v可達，而V-S中的

每個結點都從V不可達，則稱s為結點V的可達集，記為R（u）=s。集合r=UR（v）稱

veV'

為集合廿的可達集，記為R（"）=7,這里Vo對v,如果R（y）=v,并

且對任意ViCM,都有R（W）WV,則稱V1為圖G的結點基。在圖6.15中求R（w）、

R（V4）、R38）、/?（｛VI,V8｝）＞R（｛V7,內｝）、R（｛W,V8,V9,0O｝）和該圖的結點基。

Kio

解;?(V])=/?(V4)={V|,V2,V3,V4,V5,V6},

R(V8)={%,V7,V8}，

^({V|,V8})={V1,V2,V3,V4,V5,V6,V7,V8}>

R({V7,V9})={V6,V7,V9),

/?({V|,Vg,V9,V|0})={Vl,V2,V3,V4,V5,V6,V7,V8,V9,VI0})

該圖的結點基為{也，喙,V9,叫I)}、{V2,V8,V9,V|0}、(V3,V8,V9/10}、{%丫8/9田0}。

25.圖6.16所示的6個圖中，哪幾個是強連通圖？哪幾個是單向連通圖？哪幾個是連通圖

(弱連通圖)？

解圖6.16所示的六個圖中，（辦（e）、⑺是強連通圖；（辦（辦⑷、（e）、（/）是單向連通圖;

（辦3）、（c）、（辦（e）、⑺都是弱連通圖。

26.給圖6.17所示的彼得森圖的邊加方向，使其

（1）成為強連通圖；

（2）成為單向連通圖，但不是強連通圖。

圖6.17圖6.18圖6.19

解（1）給圖6.17加方向如圖6.18所示便成為強連通圖，事實上，圖6.18中存在一條回路

1,2,3,4,5,1,6,8,10,7,9,4,5,1,該回路經過圖中每個結點至少一次；

（2）給圖6.17加方向如圖6.19所示便成為單向連通圖，但不是強連通圖，事實上，圖

6.19中的結點2,3,4,5,6,7,8,9,10相互可達（有回路2,3,4,5,10,7,9,6,8』。,7,2）,結點1可達

其它所有結點，而其它所有結點都不可達1。

27.求圖6.20所示有向圖的所有強連通分支、單向連通分支和弱連通分支。

解由結點集合｛丫1,也,丫3,丫4｝、｛"5八｛"｝、｛叫｝、｛吸｝導出的子圖為該圖的所有強連通分支;

由結點集合｛0,也小3,丫4,”｝、｛V5,V6,V7）A｛口7,噸｝導出的子圖為該圖的所有單向連通分支；

由結點集合｛V1M,V3,V4,V5,V6,V7,V8｝導出的子圖（即該圖自身）為該圖的弱連通分支。

28.有向圖G如圖6.21所示。

（1）寫出G的鄰接矩陣4。

（2）G中長度為4的通路有多少條？其中有幾條為回路？

（3）利用布爾矩陣的運算求該圖的可達性矩陣P,并根據(jù)P來

判斷該圖是否為強連通圖或單向連通圖。

解（1）將G中結點按也，吸,3/4,打排序，則G的鄰接矩陣為

’01010、圖6.21

00001

A=01010

00001

J0100,

（2）為了求G中長度為4的連通數(shù)目，就要計算為此先計算屋和A?,

'00002、'20200、’04040、

101000202000004

A2=0000220200,A4=04040

101000202000004

、02020,、00004,、40400,

因tEX'=32,故G中長度為4的通路有32條。因屋的主對角元素均為o,G中

i=lj=l

無長度為4的回路。

(3)因為

'00001、’10100、

1010001010

A'"=A△A=000012=人人心=10100

1010001010

,010102、0000"

「01010、

00001

A")=AAA⑶01010

00001

<1010

所以G的可達性矩陣

’1111r

11111

P=IvAvA⑵八⑶vA")=11111

11111

,111

由于P中每個元素均為1,所以G是強連通圖，當然也是單向連通圖。

29.試利用矩陣方法判斷圖6.22所示的三個有向圖的連通性。

圖6.22

解以下寫鄰接矩陣和可達性矩陣時均將結點按V|,V2』3,V4排序。

(1)寫出圖7.9.20中圖Gi的鄰接矩陣A并根據(jù)A求出可達性矩陣P如下

’0011、‘1111、

10101111

A=