《湘潭大學 劉任任版 離散數(shù)學課后習題答案 習題8》由會員分享，可在線閱讀，更多相關(guān)《湘潭大學 劉任任版 離散數(shù)學課后習題答案 習題8（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、 習題81、圖中8.10中哪些是E圖？哪些是半E圖？分析：根據(jù)歐拉定理及其推論，E圖是不含任何奇點的圖，半E圖是最多含兩個奇點的圖。解： (a) 半E 圖 。（b）E 圖。 （c）非半E 圖 和 E 圖 2、試作出一個E圖G(p,q),使得p與q均為奇數(shù)。能否作出一個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 的每個塊也是 E 圖。 分析：一個圖如果含有E回路，則該圖是E圖；另一方面一個塊是G中不含割點的極大連通不可分子圖，且非割點不可能屬于兩個
2、或兩個以上的塊。這樣沿G中的一條E回路遍歷G的所有邊時，從一個塊到達另一個塊時，只能經(jīng)過割點才能實現(xiàn)。證明：設(shè)B是G的塊，任取G中一條E回路C，由B中的某一點v出發(fā)，沿C前進，C只有經(jīng)過G的割點才能離開B，也就是說只有經(jīng)過同一個割點才能回到B中，注意到這個事實后，我們將C中屬于B外的一個個閉筆回路除去，最后回到v時，我們得到的就是B上的一個E回路，所以B也是E圖。4、求證：若G無奇點，則G中存在邊互不重的回路 ，使得分析：G中無奇點，則除了孤立點后其他所有點的度至少為2，而孤立點不與任何邊關(guān)聯(lián)，因此在分析由邊構(gòu)成的回路時可以不加考慮；而如果一個圖所有的頂點的度至少為2，則由第五章習題18知該圖
3、必含回路。證明：將G中孤立點去掉以后得到圖G1，顯然G1也是一個無奇點的E圖，且。由第五章習題18知，G1必含有回路C1；在圖G1-C1中去掉孤立點，得圖G2，顯然G2仍然是一個無奇點的圖，且，于是G2中也必含回路C2，如此直到Gm中有回路Cm，且Gm-Cm全為孤立點為止，于是有：5、求證：若G有2k0個奇點，則G中存在k個邊互不重的鏈 ,使得：分析：一個圖的E回路去掉一條邊以后，將得到一條E鏈。證明：設(shè) 為 G 中的奇數(shù)度頂點，k1在Vi和Vi+k 之間用新邊ei連接，=1，2.k,所得之圖記為G*，易知G*的每個頂點均為偶數(shù)，從而G*存在 E 閉鏈C* ?，F(xiàn)從C*中刪去ei （=1，2.k
4、），則C*被分解成 k 條不相交的鏈Qi(=1，2.k),顯然有: 6、 證明：如果 （1）G不是2連通圖，或者（2）G是二分圖,且XY,則 G 不是 H 圖。分析：G不是2連通圖，說明，于是或，如果，則說明G不連通，如G不連通，顯然G不是H圖，如則G中存在孤立點，因此有(G-v)2，由定理8.2.1G不是H圖。若G是二分圖，則X或Y中的任意兩個頂點不鄰接，因此G-X剩下的是Y中的點，這些點都是孤立點；同樣G-Y剩下的是X中的點，這些點也是孤立點；即有，如果XY，則有成立。無論哪個結(jié)論成立，根據(jù)定理8.2.1都有G不是H圖。證明：若（1）成立則G不連通或者是G有割點u，若G不連通,則G不是H圖
5、，若G有割點u，取S=u,于是(G-u) S因此 G不是H圖.因此 G不是H圖.7、證明：若 G 是半 H 圖,則對于V(G)的每一個真子集S，有: 分析：圖G的權(quán)與它的生成子圖 的連通分支數(shù)滿足： ，因為一個圖的生成子圖是在該圖的基礎(chǔ)上去掉若干邊得到的，顯然去掉邊以后只能使該圖的連通分支增加。對于圖G的一條H通路C，滿足任取, 證明:設(shè)C是G的一條H通路，任取, 易知而 C-S是 G-S 的生成子圖. 8、試述 H 圖與 E 圖之間的關(guān)系。 分析：H圖是指存在一條從某個點出發(fā)經(jīng)過其他頂點有且僅有一次的回路；而E圖是指從某點出發(fā)通過圖中所有的邊一次且僅有一次的回路。從定義可看出，這兩者之間沒有
6、充分或必要的關(guān)系。解 ： 考慮如下四個圖:易知G1是E圖，但非H圖; G2是H圖，但非E圖; G3既非E圖，又非H圖；G4既是E圖，也是H圖。 9、作一個圖，它的閉包不是完全圖分析：一個p階圖的閉包是指對G中滿足d(u)+d(v)p的頂點u,v，若uvE(G)，則將邊uv加到G中，得到G+uv，如此反復(fù)加邊，直到滿足d(u)+d(v)p的所有頂點均鄰接。由閉包的定義，如果一個圖本身不存在任何一對頂點u,v，滿足d(u)+d(v)p，則它的閉包就是其自身。顯然可找到滿足這種條件的非完全圖。10、若 G 的任何兩個頂點均由一條 H 通路連接著，則稱G 是H連通的。 （2）對于p4，構(gòu)造一個具有 的
7、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鄰接的頂點u與w之間不可能有一條H 通路連接它們，否則因為p4，所以G中除了u與w外還有其他頂點，因此，如果u與w之間有一條H通路的話，這條H通路與u與w的連線就構(gòu)成了一個回路，這樣與d(w)=1矛盾，所以d(w)1；同樣的道理，若d(w)=2，則與w鄰接的頂點u與v之間不存在H通路。因此(G) 3。從而 2q=d(u)3p, 即：2q3p,也即q 3p/2() 若p為奇數(shù)，于是()
8、若p為偶數(shù)，則3p為偶數(shù)，于是綜合以上各種情況 ，有： （2）()當p=偶數(shù)時，q=3p/2，滿足條件的圖如下圖(a); () 當p=奇數(shù)時， 滿足條件的圖如下圖(b); 圖(a) 圖(b) 11、證明：若G是一個具有 p2的連通簡單圖，則 G 有一條長度至少是2的通路。 分析：使用反證法，假設(shè)G 中沒有一條長度大于或等于2的通路。先找到圖G的一條最長通路P，設(shè)其長度為m，由假設(shè)m2。再在P的基礎(chǔ)上構(gòu)造一條長度為m+1的回路C，顯然C中包含的頂點數(shù)小2，由于p2，所以圖G至少還有一個頂點v不在該圈中，又由于G是連通的，所以v到C上有一條通路P。于是P+C的長度等于通路P的長度的通路構(gòu)成了一條比
9、P更長的通路，這與P是G的一條最長通路矛盾。從而本題可得到證明。證明：(用反證法)設(shè) 是G的最長通路,其長度為m，假設(shè)m2。由P是G的最長通路，則V1,Vm+1只能與 P中的頂點相鄰，注意到 G 是簡單圖分析：由定理8.2.4，如果p（3）階簡單圖G的各頂點度數(shù)序列下面的證明就是利用這個定理來判斷當mm。從而G是H圖。13、在圖8-8中，如果分別去掉v3，v4和v5，則相應(yīng)得到的旅行推銷員問題的解分別取什么下界估計值？ 分析：利用Kruskal算法可給出一個關(guān)于旅行推銷員問題的的下界估計式： 任選賦權(quán)完全圖Kn的一個頂點v，用Kruskal算法求出Kn-v的最優(yōu)樹T，設(shè)C是最優(yōu)的H回路，于是有
10、C-v也是Kn-v的一個生成樹，因此有：w(T)w(C-v)設(shè)e1和e2是Kn中與v關(guān)聯(lián)的邊中權(quán)最小的兩條邊，于是：w(T)+w(e1)+w(e2)w(C) 上式左邊的表達式即是w(C)的下界估計式。解：（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,因此下界估計值為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)完全圖，其中對任意x,y,zV
11、(G),都滿足 ： 證明：G中最優(yōu)H回路最多具有權(quán) 其中T是G中的一棵最優(yōu)樹。分析：H回路是指從圖中某點出發(fā)，經(jīng)過圖中每個頂點有且僅有一次，最后回到出發(fā)點的一條回路。由于G是一種賦權(quán)完全圖，所以從任意頂點出發(fā)包括了G的其他所有頂點有且僅有一次再回到原點的回路都構(gòu)成了G的一條H回路，且最優(yōu)H回路C的權(quán)滿足 。因此只需證明G中存在一條H回路，其權(quán) 即可，因此證明本題的關(guān)鍵是找到滿足這個結(jié)論的H回路。 證明：設(shè)T是G中的一棵最優(yōu)樹，將T的每邊加倍得到圖，則的每個頂點的度數(shù)均為偶數(shù)。所以有一歐拉回路Q，設(shè)，(n|v(G)|)，Q中某些頂點可能有重復(fù)，且 。 在Q中，從v3開始，凡前面出現(xiàn)過的頂點全部刪去，得到G的|v(G)|個頂點的一個排列。由于G是完全的，所以可以看作G中的一個H回路。在中任意邊(u,v)，在T中對應(yīng)存在唯一的(u,v)-通路P，由權(quán)的三角不等式有 。由于將中的邊(u,v)用T中的P來代替時，就得到Q，因而 。故G中的最優(yōu)H回路C的權(quán)
湘潭大學 劉任任版 離散數(shù)學課后習題答案 習題8
