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

《湘潭大學 劉任任版 離散數(shù)學課后習題答案 習題8》由會員分享，可在線閱讀，更多相關《湘潭大學 劉任任版 離散數(shù)學課后習題答案 習題8（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 習題8 1、圖中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 的奇偶如下表 p q G1 奇數(shù) 奇

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

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

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

5、通圖，或者（2）G是二分圖,且X≠Y,則 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中的點，這些點也是孤立點；即有，如果X≠Y，則有成立。無論哪個結論成立，根據(jù)定理8.2.1都有G不是H圖。 證明：若（1）成立則G不連通或者是G有割點u，若G不連通,則G不是H圖，若G有割點u，取S={u},于是ω(G-u)> S因此 G不是

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

7、發(fā)經(jīng)過其他頂點有且僅有一次的回路；而E圖是指從某點出發(fā)通過圖中所有的邊一次且僅有一次的回路。從定義可看出，這兩者之間沒有充分或必要的關系。 解 ： 考慮如下四個圖: 易知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，如此反復加邊，直到滿足d(u)+d(v)≥p的所有頂點均鄰接。由閉包的定義，如果一個圖本身不存在任何一對頂點u,v，滿足d(u)+d(v)≥

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

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

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

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

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

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

13、 任選賦權完全圖Kn的一個頂點v，用Kruskal算法求出Kn-v的最優(yōu)樹T，設C是最優(yōu)的H回路，于是有C-v也是Kn-v的一個生成樹，因此有：w(T)≤w(C-v) 設e1和e2是Kn中與v關聯(lián)的邊中權最小的兩條邊，于是：w(T)+w(e1)+w(e2)≤w(C) 上式左邊的表達式即是w(C)的下界估計式。 解：（1）去掉v3后的最優(yōu)數(shù)T3的權為w(T3)=5+5+1+7=18,而與v3關聯(lián)的5條邊中權最小的兩條之權為w(e1)=8,w(e2)=9,因此下界估計值為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、設G是一種賦權完全圖，其中對任意x,y,z∈V(G),都滿足 ： 證明：G中最優(yōu)H回路最多具有權 其中T是G中的一棵最優(yōu)樹。 分析：H回路是指從圖中某點出發(fā)，經(jīng)過圖中每個頂點有且僅有一次，最后回到出發(fā)點的一條回路。由于G是一種賦權完全圖，所以從任意頂點出發(fā)包括了G的其他所有頂點有且僅有一次再回到原點的回路都構成了G的一條H回路，且最優(yōu)H回路C的權滿足 。因此只需證明G中存在一條H回路，其權

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