圖論基礎(chǔ)習(xí)題及答案

離散數(shù)學(xué)

習(xí)題5

1.給定下面4個(gè)圖（前兩個(gè)為無(wú)向圖，后兩個(gè)為有向圖）地集合表示，畫出1

示。

L

G]VpE]，其中V1V”V12VpV,4V5,1（vpV,）,（v2,V3）,（v3）V4）,（v2,v3）

G2E2，其中V2V”2G，丫），2（v，￥），3（V,￥），46,￥），5（v,*）

%%E3，其中V3V;13v,yv，￥3，v,y2，V,Y夕V,Y,

I)2ypE4，其中V4V,,

E4VI,V2,y，Y,y,y,y,

解答：

◎

D、2

2先將圖1中各圖地頂點(diǎn)標(biāo)定順序,然后寫出各圖地集合表示。

圖1

解答:略。

111

第5章圖地基本理論

3.寫出圖1中各圖地度序列，對(duì)有向圖還要寫出出度列與入度列。

解答:圖1各圖地度序列分別為(4L232),(323,42),出度列(2Q21,0),入度列(2Q

2,1,0)。

4.設(shè)無(wú)向圖G有12條邊,3度與4度頂點(diǎn)各2個(gè)，其余頂點(diǎn)地度數(shù)均小于3,問(wèn)中至少

有幾個(gè)頂點(diǎn)？在最少頂點(diǎn)地情況下，寫出G地度序列，(G),G)。

解答:根據(jù)握手定理，21232423(n4),得8。

當(dāng)n=8時(shí)，上述式子取21232423311,因此度序列為(443,333

3,1)o(G)=4,(G)=1o

5.設(shè)無(wú)向圖中有7條邊3度與5度頂點(diǎn)各1個(gè)其余地都是2度頂點(diǎn)問(wèn)該圖有幾個(gè)頂點(diǎn)？

解答：由握手定理，有(273523個(gè)2度頂點(diǎn)。因此該圖有113=5個(gè)頂點(diǎn)。

6畫以(1,23,4)為度序列地簡(jiǎn)單圖與非簡(jiǎn)單圖各一個(gè)。

解答：

7.設(shè)9階無(wú)向圖G中，每個(gè)頂點(diǎn)地度數(shù)不是5就是6,證明中至少有5個(gè)6度頂點(diǎn)或至

少有6個(gè)5度頂點(diǎn)。

證明：假設(shè)G中至多有4個(gè)6度頂點(diǎn)且至多有5個(gè)5度頂點(diǎn)。而G地頂點(diǎn)為9,所有頂點(diǎn)

度只能是5或6,因此G恰好有4個(gè)6度頂點(diǎn)與5個(gè)5度頂點(diǎn)。由握手定理，

2|E(G)|465549,矛盾！因此，結(jié)論得證。

&最大度等于最小度且都等于2地6階無(wú)向圖有幾種非同構(gòu)地情況？其中有幾種是簡(jiǎn)

單圖？

解答:總共有以下11種非同構(gòu)地圖：6C,14C,C,23clC,32c.2C,22c.C

C.C,C,C,C3c2，CC.,2c3，C6。其中簡(jiǎn)單圖為2c3，C(其中,C

53(26o1

為一個(gè)帶自環(huán)地頂點(diǎn)所成地圖)

9.圖2所示地六個(gè)圖中哪幾個(gè)是強(qiáng)連通圖？哪幾個(gè)是單向連通圖？哪幾個(gè)是連通圖(弱連

112

離散數(shù)學(xué)

通圖)？

圖2

解答:第1,56圖為強(qiáng)連通圖,第2,4圖為單向連通圖，以上6個(gè)圖均為弱連通圖。

10.下面給出地兩個(gè)正整數(shù)列表示頂點(diǎn)地度數(shù)列，哪個(gè)是可圖化地？對(duì)于可圖化地?cái)?shù)列，試

給出3種非同構(gòu)地?zé)o向圖,其中至少有兩個(gè)圖是簡(jiǎn)單圖。

(1)2233,445<2)2222,3344

解答：⑴不可圖，因?yàn)槠娑葦?shù)頂點(diǎn)個(gè)數(shù)為奇數(shù)。

⑵可圖。以下給出3種非同構(gòu)地?zé)o向圖，其中后兩個(gè)圖是簡(jiǎn)單圖。

1L下列各數(shù)列中哪些是簡(jiǎn)單圖化地？對(duì)于可簡(jiǎn)單圖化地,試給出兩個(gè)非同構(gòu)地簡(jiǎn)單圖。

(1)(2,3,3,5,5,6,6)(2)(1,1,2,2,3,3,5,5)(3)(2,2,2,2,3,3)

解答：(1)(2,3,355,6,6)不可簡(jiǎn)單圖化(2)(1,1,2,2,3,355)可簡(jiǎn)單圖化(3)

(2,2,2,2,3,3)可簡(jiǎn)單圖化。

圖略。

12畫出無(wú)向完全圖K4地所有非同構(gòu)地子圖,指出哪些是生成子圖。

解答:生成子圖如下圖所示：

113

第5章圖地基本理論

13.已知n階無(wú)向簡(jiǎn)單圖G有m條邊，試求G地補(bǔ)圖G耳邊數(shù)m:

14.無(wú)向圖G如圖3所示，先標(biāo)定頂點(diǎn)與邊，然后

(1)求G地全部點(diǎn)割集與邊割集，并指出其中地割點(diǎn)與橋(割邊)。

⑵求G地點(diǎn)連通度G與邊連通度G.

解答：⑵G)=1,⑹=1。

15求圖4所示圖G地G,G,G.

解答：(G)=2,(G)=3,⑹=4。

16設(shè)n階無(wú)向簡(jiǎn)單圖為3-正則圖,且邊數(shù)m與n滿足2n3m,問(wèn)這樣地?zé)o向圖有幾種

非同構(gòu)地情況？

114

離散數(shù)學(xué)

2n3m

解答:頂點(diǎn)數(shù)與邊數(shù)地關(guān)系為2m3n，解得

17.n(nz3)階競(jìng)賽圖中至多有幾種非同構(gòu)地圈？

解答:至多有n-2種非同構(gòu)地圈。

1&畫出鄰接矩陣A地?zé)o向圖G地圖形，其中

01010

11001

A00011

10101

01111

解答：圖G如下:

19.有向圖D如圖5所示。

(1)D中看到長(zhǎng)度為1,234地通路各為幾條？

⑵D中看到%長(zhǎng)度為1,234地回路各為幾條？

⑶D中長(zhǎng)度為4地通路有幾條？其中長(zhǎng)度為4地回路為多少條？

(4)D中長(zhǎng)度小于或等于4地通路為多少條？其中有多少條為回路?

⑸寫出D地可達(dá)矩陣。

1‘2V3

115

第5章圖地基本理論

圖5

解答：

1210123112431264

0010?0001?00100001

AA

000100100001

001000010010°086P

因此，⑴D中v到v首度為1,234地通路分別為QL34條。

⑵D中％到%長(zhǎng)度為1,234地回路均為1條。

⑶D中長(zhǎng)度為4地通路有1+2+6+4+1+1+1=16條,其中長(zhǎng)度為4地回路為1+1+1=3條。

(4)D中長(zhǎng)度小于或等于4地通路為多少7+10+13+16=46條淇中有1+3+1+3=8條為回路。

⑸D地可達(dá)矩陣為

1111

0111O

P

0011

0011

20.有向圖D如圖6所示。求

(1)V2到V5長(zhǎng)度為1,234地通路數(shù).

⑵v5到內(nèi)長(zhǎng)度為L(zhǎng)234地回路數(shù)。

(3)D中長(zhǎng)度為4地通路數(shù)(含回路)。

(4)D中長(zhǎng)度小于或等于4地回路數(shù)。

⑸寫出D地可達(dá)矩陣。

解答:

116

離散數(shù)學(xué)

1011010120

1010010120

A00010A2A3A400000。

0000000000

0002000000

因此

(1)v2到V5長(zhǎng)度為1,234地通路數(shù)均為0o

⑵v5到v5長(zhǎng)度為L(zhǎng)234地回路數(shù)均為0。

⑶D中長(zhǎng)度為4地通路數(shù)(含回路)為8。

(4)D中長(zhǎng)度小于或等于4地