湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題8

習(xí)題81、圖中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 的奇偶如下表 pqG1奇數(shù)奇數(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)過割點(diǎn)才能實(shí)現(xiàn)。證明：設(shè)B是G的塊，任取G中一條E回路C，由B中的某一點(diǎn)v出發(fā)，沿C前進(jìn)，C只有經(jīng)過G的割點(diǎn)才能離開B，也就是說只有經(jīng)過同一個(gè)割點(diǎn)才能回到B中，注意到這個(gè)事實(shí)后，我們將C中屬于B外的一個(gè)個(gè)閉筆回路除去，最后回到v時(shí)，我們得到的就是B上的一個(gè)E回路，所以B也是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>0個(gè)奇點(diǎn)，則G中存在k個(gè)邊互不重的鏈 ,使得：分析：一個(gè)圖的E回路去掉一條邊以后，將得到一條E鏈。證明：設(shè) 為 G 中的奇數(shù)度頂點(diǎn)，k1在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連通圖，或者（2）G是二分圖<X,Y>,且XY,則 G 不是 H 圖。分析：G不是2連通圖，說明，于是或，如果，則說明G不連通，如G不連通，顯然G不是H圖，如則G中存在孤立點(diǎn)，因此有(G-v)2，由定理8.2.1G不是H圖。若G是二分圖<X，Y>，則X或Y中的任意兩個(gè)頂點(diǎn)不鄰接，因此G-X剩下的是Y中的點(diǎn)，這些點(diǎn)都是孤立點(diǎn)；同樣G-Y剩下的是X中的點(diǎn)，這些點(diǎn)也是孤立點(diǎn)；即有，如果XY，則有成立。無(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不是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)出發(fā)經(jīng)過其他頂點(diǎn)有且僅有一次的回路；而E圖是指從某點(diǎn)出發(fā)通過圖中所有的邊一次且僅有一次的回路。從定義可看出，這兩者之間沒有充分或必要的關(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)p，則它的閉包就是其自身。顯然可找到滿足這種條件的非完全圖。10、若 G 的任何兩個(gè)頂點(diǎn)均由一條 H 通路連接著，則稱G 是H連通的。 （2）對(duì)于p4，構(gòu)造一個(gè)具有 的H連通圖G。分析：根據(jù)定理5.3.1有，因此而，所以qp*(G)/2，因此如果能判斷(G)3，則有 下面的證明關(guān)鍵是判斷(G)3。證明：（1）任取wV(G),由于G是連通的，所以d(w)1。若d(w)=1,則與w鄰接的頂點(diǎn)u與w之間不可能有一條H 通路連接它們，否則因?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, 即：2q3p,也即q 3p/2() 若p為奇數(shù)，于是() 若p為偶數(shù)，則3p為偶數(shù)，于是綜合以上各種情況 ，有： （2）()當(dāng)p=偶數(shù)時(shí)，q=3p/2，滿足條件的圖如下圖(a); () 當(dāng)p=奇數(shù)時(shí)， 滿足條件的圖如下圖(b); 圖(a) 圖(b) 11、證明：若G是一個(gè)具有 p2的連通簡(jiǎn)單圖，則 G 有一條長(zhǎng)度至少是2的通路。 分析：使用反證法，假設(shè)G 中沒有一條長(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，由于p2，所以圖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è) 是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<p/2時(shí)，dm滿足dm>m。從而G是H圖。13、在圖8-8中，如果分別去掉v3，v4和v5，則相應(yīng)得到的旅行推銷員問題的解分別取什么下界估計(jì)值？ 分析：利用Kruskal算法可給出一個(gè)關(guān)于旅行推銷員問題的的下界估計(jì)式： 任選賦權(quán)完全圖Kn的一個(gè)頂點(diǎn)v，用Kruskal算法求出Kn-v的最優(yōu)樹T，設(shè)C是最優(yōu)的H回路，于是有C-v也是Kn-v的一個(gè)生成樹，因此有：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=35; （3）去掉v5后, 有w(T5)=26, w(C5)=26+1+5=32.14、設(shè)G是一種賦權(quán)完全圖，其中對(duì)任意x,y,zV(G),都滿足 ： 證明：G中最優(yōu)H回路最多具有權(quán) 其中T是G中的一棵最優(yōu)樹。分析：H回路是指從圖中某點(diǎn)出發(fā)，經(jīng)過圖中每個(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) 即可，因此證明本題的關(guān)鍵是找到滿足這個(gè)結(jié)論的H回路。 證明：設(shè)T是G中的一棵最優(yōu)樹，將T的每邊加倍得到圖，則的每個(gè)頂點(diǎn)的度數(shù)均為偶數(shù)。所以有一歐拉回路Q，設(shè)，(n|v(G)|)，Q中某些頂點(diǎn)可能有重復(fù)，且 。 在Q中，從v3開始，凡前面出現(xiàn)過的頂點(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)