《湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題8》由會(huì)員分享，可在線閱讀，更多相關(guān)《湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題8（6頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 習(xí)題8 1、圖中8.10中哪些是E圖？哪些是半E圖？ ４ ０ １ ２ ５ ３ ０ ５ １ ４ ３ ２ ６ 分析：根據(jù)歐拉定理及其推論，E圖是不含任何奇點(diǎn)的圖，半E圖是最多含兩個(gè)奇點(diǎn)的圖。 解： (a) 半E 圖 。（b）E 圖。 （c）非半E 圖 和 E 圖 2、試作出一個(gè)E圖G(p,q),使得p與q均為奇數(shù)。能否作出一個(gè)E圖G(p,q)，使得p為偶數(shù)，而q為奇數(shù)？如果是p為奇數(shù)，q為偶數(shù)呢？ 解：以下 E 圖中， p與 q 的奇偶如下表 p q G1 奇數(shù) 奇

2、數(shù) G2 偶數(shù) 奇數(shù) G3 奇數(shù) 偶數(shù) 3、求證：若G 是 E 圖，則 G 的每個(gè)塊也是 E 圖。 分析：一個(gè)圖如果含有E回路，則該圖是E圖；另一方面一個(gè)塊是G中不含割點(diǎn)的極大連通不可分子圖，且非割點(diǎn)不可能屬于兩個(gè)或兩個(gè)以上的塊。這樣沿G中的一條E回路遍歷G的所有邊時(shí)，從一個(gè)塊到達(dá)另一個(gè)塊時(shí)，只能經(jīng)過(guò)割點(diǎn)才能實(shí)現(xiàn)。 證明：設(shè)B是G的塊，任取G中一條E回路C，由B中的某一點(diǎn)v出發(fā)，沿C前進(jìn)，C只有經(jīng)過(guò)G的割點(diǎn)才能離開(kāi)B，也就是說(shuō)只有經(jīng)過(guò)同一個(gè)割點(diǎn)才能回到B中，注意到這個(gè)事實(shí)后，我們將C中屬于B外的一個(gè)個(gè)閉筆回路除去，最后回到v時(shí)，我們得到的就是B上的一個(gè)E回路，所以B

3、也是E圖。 4、求證：若G無(wú)奇點(diǎn)，則G中存在邊互不重的回路 ，使得 分析：G中無(wú)奇點(diǎn)，則除了孤立點(diǎn)后其他所有點(diǎn)的度至少為2，而孤立點(diǎn)不與任何邊關(guān)聯(lián)，因此在分析由邊構(gòu)成的回路時(shí)可以不加考慮；而如果一個(gè)圖所有的頂點(diǎn)的度至少為2，則由第五章習(xí)題18知該圖必含回路。 證明：將G中孤立點(diǎn)去掉以后得到圖G1，顯然G1也是一個(gè)無(wú)奇點(diǎn)的E圖，且。由第五章習(xí)題18知，G1必含有回路C1；在圖G1-C1中去掉孤立點(diǎn)，得圖G2，顯然G2仍然是一個(gè)無(wú)奇點(diǎn)的圖，且，于是G2中也必含回路C2，…如此直到Gm中有回路Cm，且Gm-Cm全為孤立點(diǎn)為止，于是有： 5、求證：若G有2k>

4、0個(gè)奇點(diǎn)，則G中存在k個(gè)邊互不重的鏈 ,使得： 分析：一個(gè)圖的E回路去掉一條邊以后，將得到一條E鏈。 證明：設(shè) 為 G 中的奇數(shù)度頂點(diǎn)，k≥1在Vi和Vi+k 之間用新邊ei連接，ⅰ=1，2….k,所得之圖記為G*，易知G*的每個(gè)頂點(diǎn)均為偶數(shù)，從而G*存在 E 閉鏈C* 。現(xiàn)從C*中刪去ei （ⅰ=1，2….k），則C*被分解成 k 條不相交的鏈Q(jìng)i(ⅰ=1，2….k),顯然有: 6、 證明：如果 （1）G不是2—連

5、通圖，或者（2）G是二分圖,且X≠Y,則 G 不是 H 圖。 分析：G不是2—連通圖，說(shuō)明，于是或，如果，則說(shuō)明G不連通，如G不連通，顯然G不是H圖，如則G中存在孤立點(diǎn)，因此有ω(G-v)≥2，由定理8.2.1G不是H圖。若G是二分圖，則X或Y中的任意兩個(gè)頂點(diǎn)不鄰接，因此G-X剩下的是Y中的點(diǎn)，這些點(diǎn)都是孤立點(diǎn)；同樣G-Y剩下的是X中的點(diǎn)，這些點(diǎn)也是孤立點(diǎn)；即有，如果X≠Y，則有成立。無(wú)論哪個(gè)結(jié)論成立，根據(jù)定理8.2.1都有G不是H圖。 證明：若（1）成立則G不連通或者是G有割點(diǎn)u，若G不連通,則G不是H圖，若G有割點(diǎn)u，取S={u},于是ω(G-u)> S因此 G不是

6、H圖. 因此 G不是H圖. 7、證明：若 G 是半 H 圖,則對(duì)于V(G)的每一個(gè)真子集S，有: 分析：圖G的權(quán)與它的生成子圖 的連通分支數(shù)滿足： ，因?yàn)橐粋€(gè)圖的生成子圖是在該圖的基礎(chǔ)上去掉若干邊得到的，顯然去掉邊以后只能使該圖的連通分支增加。 對(duì)于圖G的一條H通路C，滿足任取, 證明:設(shè)C是G的一條H通路，任取, 易知 而 C-S是 G-S 的生成子圖. 8、試述 H 圖與 E 圖之間的關(guān)系。 分析：H圖是指存在一條從某個(gè)點(diǎn)出

7、發(fā)經(jīng)過(guò)其他頂點(diǎn)有且僅有一次的回路；而E圖是指從某點(diǎn)出發(fā)通過(guò)圖中所有的邊一次且僅有一次的回路。從定義可看出，這兩者之間沒(méi)有充分或必要的關(guān)系。 解 ： 考慮如下四個(gè)圖: 易知G1是E圖，但非H圖; G2是H圖，但非E圖; G3既非E圖，又非H圖；G4既是E圖，也是H圖。 9、作一個(gè)圖，它的閉包不是完全圖 分析：一個(gè)p階圖的閉包是指對(duì)G中滿足d(u)+d(v)≥p的頂點(diǎn)u,v，若uvE(G)，則將邊uv加到G中，得到G+uv，如此反復(fù)加邊，直到滿足d(u)+d(v)≥p的所有頂點(diǎn)均鄰接。由閉包的定義，如果一個(gè)圖本身不存在任何一對(duì)頂點(diǎn)u,v，滿足d(u)+d(v)≥

8、p，則它的閉包就是其自身。顯然可找到滿足這種條件的非完全圖。 10、若 G 的任何兩個(gè)頂點(diǎn)均由一條 H 通路連接著，則稱G 是H連通的。 （2）對(duì)于p≧4，構(gòu)造一個(gè)具有 的H連通圖G。 分析：根據(jù)定理5.3.1有，因此 而，所以q≥p*δ(G)/2，因此如果能判斷δ(G)≥3，則有 下面的證明關(guān)鍵是判斷δ(G)≥3。 證明：（1）任取w∈V(G),由于G是連通的，所以d(w)≥1。 若d(w)=1,則與w鄰接的頂點(diǎn)u與w之間不可能有一條H 通

9、路連接它們，否則因?yàn)閜≥4，所以G中除了u與w外還有其他頂點(diǎn)，因此，如果u與w之間有一條H通路的話，這條H通路與u與w的連線就構(gòu)成了一個(gè)回路，這樣與d(w)=1矛盾，所以d(w)≠1； 同樣的道理，若d(w)=2，則與w鄰接的頂點(diǎn)u與v之間不存在H通路。 因此δ(G) ≥3。 從而 2q=∑d(u)≥3p, 即：2q≥3p,也即q ≥ 3p/2 (ⅰ) 若p為奇數(shù)，于是 (ⅱ) 若p為偶數(shù)，則3p為偶數(shù)，于是 綜合以上各種情況 ，有： （2）(ⅰ)當(dāng)p=偶數(shù)時(shí)，q=3p/2，滿足條件的圖如下圖(a);

10、 (ⅱ) 當(dāng)p=奇數(shù)時(shí)， 滿足條件的圖如下圖(b); … … 圖(a) … … 圖(b)

11、 11、證明：若G是一個(gè)具有 p≧2δ的連通簡(jiǎn)單圖，則 G 有一條長(zhǎng)度至少是2δ的通路。 分析：使用反證法，假設(shè)G 中沒(méi)有一條長(zhǎng)度大于或等于2δ的通路。先找到圖G的一條最長(zhǎng)通路P，設(shè)其長(zhǎng)度為m，由假設(shè)m<2δ。再在P的基礎(chǔ)上構(gòu)造一條長(zhǎng)度為m+1的回路C，顯然C中包含的頂點(diǎn)數(shù)小<2δ，由于p≧2δ，所以圖G至少還有一個(gè)頂點(diǎn)v不在該圈中，又由于G是連通的，所以v到C上有一條通路P’。于是P’+C的長(zhǎng)度等于通路P的長(zhǎng)度的通路構(gòu)成了一條比P更長(zhǎng)的通路，這與P是G的一條最長(zhǎng)通路矛盾。從而本題可得到證明。 證明：(用反證法)設(shè)

12、 是G的最長(zhǎng)通路,其長(zhǎng)度為m，假設(shè)m<2δ。 由P是G的最長(zhǎng)通路，則V1,Vm+1只能與 P中的頂點(diǎn)相鄰，注意到 G 是簡(jiǎn)單圖 分析：由定理8.2.4，如果p（≥3）階簡(jiǎn)單圖G的各頂點(diǎn)度數(shù)序列 下面的證明就是利用這個(gè)定理來(lái)判斷當(dāng)m

m。從而G是H圖。 13、在圖8-8中，如果分別去掉v3，v4和v5，則相應(yīng)得到的旅行推銷員問(wèn)題的解分別取什么下界估計(jì)值？ 分析：利用Kruskal算法可給出一個(gè)關(guān)于旅行推銷員問(wèn)題的的下界估計(jì)式：

13、 任選賦權(quán)完全圖Kn的一個(gè)頂點(diǎn)v，用Kruskal算法求出Kn-v的最優(yōu)樹(shù)T，設(shè)C是最優(yōu)的H回路，于是有C-v也是Kn-v的一個(gè)生成樹(shù)，因此有：w(T)≤w(C-v) 設(shè)e1和e2是Kn中與v關(guān)聯(lián)的邊中權(quán)最小的兩條邊，于是：w(T)+w(e1)+w(e2)≤w(C) 上式左邊的表達(dá)式即是w(C)的下界估計(jì)式。 解：（1）去掉v3后的最優(yōu)數(shù)T3的權(quán)為w(T3)=5+5+1+7=18,而與v3關(guān)聯(lián)的5條邊中權(quán)最小的兩條之權(quán)為w(e1)=8,w(e2)=9,因此下界估計(jì)值為w(C3)=18+8+9=35, ( 2 )去掉v4后，仿上有w(T4)=20, w(C4)=20+7+8

14、=35; （3）去掉v5后, 有w(T5)=26, w(C5)=26+1+5=32. 14、設(shè)G是一種賦權(quán)完全圖，其中對(duì)任意x,y,z∈V(G),都滿足 ： 證明：G中最優(yōu)H回路最多具有權(quán) 其中T是G中的一棵最優(yōu)樹(shù)。 分析：H回路是指從圖中某點(diǎn)出發(fā)，經(jīng)過(guò)圖中每個(gè)頂點(diǎn)有且僅有一次，最后回到出發(fā)點(diǎn)的一條回路。由于G是一種賦權(quán)完全圖，所以從任意頂點(diǎn)出發(fā)包括了G的其他所有頂點(diǎn)有且僅有一次再回到原點(diǎn)的回路都構(gòu)成了G的一條H回路，且最優(yōu)H回路C的權(quán)滿足 。因此只需證明G中存在一條H回路，其權(quán)

15、 即可，因此證明本題的關(guān)鍵是找到滿足這個(gè)結(jié)論的H回路。 證明：設(shè)T是G中的一棵最優(yōu)樹(shù)，將T的每邊加倍得到圖，則的每個(gè)頂點(diǎn)的度數(shù)均為偶數(shù)。所以有一歐拉回路Q，設(shè)，(n≥|v(G)|)，Q中某些頂點(diǎn)可能有重復(fù)，且 。 在Q中，從v3開(kāi)始，凡前面出現(xiàn)過(guò)的頂點(diǎn)全部刪去，得到G的|v(G)|個(gè)頂點(diǎn)的一個(gè)排列π。由于G是完全的，所以π可以看作G中的一個(gè)H回路。在π中任意邊(u,v)，在T中對(duì)應(yīng)存在唯一的(u,v)-通路P，由權(quán)的三角不等式有 。由于將π中的邊(u,v)用T中的P來(lái)代替時(shí)，就得到Q，因而 。故G中的最優(yōu)H回路C的權(quán)