習題參考解答(圖論部分)

1、習題十1. 設G是一個(n，m)簡單圖。證明：，等號成立當且僅當G是完全圖。證明：（1）先證結論： 因為G是簡單圖，所以G的結點度上限 max(d(v) n-1, G圖的總點度上限為 max(d(v) nmax(d(v) n(n-1) 。根據握手定理，G圖邊的上限為 max(m) n(n-1)/2,所以。（2） =G是完全圖因為G具有上限邊數，假設有結點的點度小于n-1,那么G的總度數就小于上限值，邊數就小于上限值，與條件矛盾。所以，G的每個結點的點度都為n-1，G為完全圖。G是完全圖 =因為G是完全圖，所以每個結點的點度為n-1, 總度數為n(n-1)，根據握手定理，圖G的邊數 。2. 設G

2、是一個（n，n+1）的無向圖，證明G中存在頂點u，d（u）3。證明：反證法，假設,則G的總點度上限為max(d(u) 2 n，根據握手定理，圖邊的上限為max(m) 2n/2=n。與題設m = n+1，矛盾。因此，G中存在頂點u，d（u）3。3確定下面的序列中哪些是圖的序列，若是圖的序列，畫出一個對應的圖來: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）解：除序列（1）不是圖序列外，其余的都是圖序列。因為在（1）中，總和為奇數，不滿足圖總度數為偶數的握手定理?？梢园慈缦路椒嬙鞚M足要求的圖：序列中每個數字ai對應

3、一個點，如果序列數字是偶數，那么就在對應的點上畫ai/2個環(huán)，如果序列是奇數，那么在對應的點上畫(ai-1)/2個環(huán)。最后，將奇數序列對應的點兩兩一組，添加連線即可。下面以（2）為例說明： (6 , 3, 3, 2, 2 ) 對應圖G的點集合V= v1,v2,v3,v4,v5v1v5v33v4v2每個結點對應的環(huán)數(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)v1v5v33v4v2將奇數3，3 對應的結點v2,v3一組，畫一條連線v1v5v33v4v2其他序列可以類式作圖，當然大家也可以畫圖其它不同的圖形。4證明：在（n，m）圖中。證明：圖的點度數

4、是一組非負整數d(v1),d(v2)d(vn)，那么這組數的算術平均值一定大于等于其中的最小值，同時小于等于其中的最大值。對應到圖的術語及為：最大值為，最小值為，平均值 = (d(v1)+d(v2)+d(vn)/n = 2m/n,所以。5證明定理10.2?！径ɡ?0.2】對于任何（n,m）有向圖G =（V，E），證明：有向圖中,每條有向邊為圖貢獻一度出度，同時貢獻一度出度，所以總出度和總入度相等，并和邊數相等。因此，上述關系等式成立。6設G是（n，m）簡單二部圖，證明：。證明：本題目，我們是需要說明n階的簡單二部圖的邊數的最大值 = 即可。設n階的簡單二部圖，其兩部分結點集合分別為V1，V2,

5、那么|V1| + |V2| = n。此種情況下，當G為完全二部圖時，有最多的邊數，即max(m) = |V1|V2|,變形為，max(m) =( n-|V2|)|V2|.此函數的最大值及為n階二部圖的邊的上限值，其上限值為當|V2|=n/2 時取得。及max(max(m) = ,所以n階二部圖(n,m), 7. 無向圖G有21條邊，12個3度數結點，其余結點的度數均為2，求G的階數n。解：根據握手定理有： 21 =( 312 + 2(n-12)/2, 解此方程得n = 158證明：完全圖的點誘導子圖也是完全圖。證明：方法1為證明此結論，我們先證兩個引論：引論1：設G(V,E)為母圖，,則G的任

6、意子圖G(V,E)是G關于V的點誘導子圖G(V,E)的子圖。引論2：引論1中G(V,E)的任意點誘導子圖，也是G圖的點誘導子圖。證明：略，請讀者證明。設有完全圖Kn( n1),現根據其p階點誘導子圖作歸納證明。Kn的1階點誘導子圖，顯然是完全圖，且都是K1圖。當n2，Kn的2階點誘導子圖，顯然是完全圖，且都是K2圖假設Kn的p(np2)階點誘導子圖，為Kp圖，那么對任意的p+1階點誘導子圖G，根據引理2結論，G的任意p階點誘導子圖G為Kn的p階點誘導子圖，且為Kp圖。因此，G必為Kp+1圖。根據以上論證可得原命題成立方法2因為完全圖的任意兩個頂點均鄰接，所以點導出子圖任意兩個頂點也鄰接，為完全

7、圖。9若，稱G是自補圖。確定一個圖為自補圖的最低條件；畫出一個自補圖來。解：設G為(n,m)圖，為(n,m)圖， 根據補圖的定義有，至少應該滿足m+m=n(n-1)/2 (1) 根據同構的定義有，至少應該滿足m=m(2)(1),(2)聯立求解得：m=n(n-1)/4, 及一個圖為自補圖，最低條件為結點數為4的倍數或為4的倍數加1。圖示略10判斷圖10.29中的兩個圖是否同構，并說明理由。圖10.29解：題中兩個圖不同構，因為左邊圖的唯一3度點有2個1度點為其鄰接點，而右圖唯一的3度點只有1個1度點為其鄰接點。因此這兩個圖不可能同構11證明： 圖10.30中的兩個圖是同構的。圖10.30解：略1

8、2. 求具有4個結點完全圖K4的所有非同構的生成子圖。解：我們可以把生成子圖按總度數不同進行分類，不同總度數的子圖類決不同構。總度數相同的子圖類中，再去找出不同購的子圖。因此求解如下：d(v) = 0: (0,0,0,0) =2: (1,1,0,0) =4: (2,1,1,0) (1,1,1,1) =6: (3,1,1,1) (2,2,1,1)(2,2,2,0) =8: (2,2,2,2) (3,2,2,1) =10: (3,3,2,2) =12: (3,3,3,3)總共10個不同構生成子圖13. 設有向圖D=如下圖10.31所示。(1) 在圖中找出所有長度分別為1，2，3，4的圈 (至少用一

9、種表示法寫出它們，并以子圖形式畫出它們)。(2) 在圖中找出所有長度分別為3，4，5，6的回路，并以子圖形式畫出它們。解：(1) C=AA C=ADA C=Ae4Be7Ce5A C=Ae4Be8Ce5A C=Ae4Be7Ce6De2A C=Ae4Be8Ce6De2A(2)子圖略長度為三的回路：Ae1Ae1Ae1A,Ae1Ae3De2A,Ae4Be7Ce5A,Ae4Be8Ce5A長度為四的回路：AAAAA，AAADA，AABe7CA,AABe8CA,ABe7CDA,ABe8CDA長度為五的回路：AAAAAA,AAAADA,AAABe7CA,AAABe8CA,AABe7CDA,AABe8CDA,

10、AADADA,AAAe4Be7Ce5A,AAAe4Be8Ce5A, ADAe4Be7Ce5A,ADAe4Be8Ce5A14. 試證明在任意6個人的組里，存在3個人相互認識，或者存在3個人相互不認識。證明：設A為6人中的任一人，那么A要么至少與3人認識，要么至少與3人不認識，二者必居其一。假設A與B，C，D三人認識，如果B，C，D三人互不認識，結論成立如果B，C，D三人中，至少有兩人相互認識，則它們和A一起，構成相互認識的3人，結論成立。同理，A至少與3人不認識，結論也成立。因此，題設結論成立15. 若u和v是圖G中僅有的兩個奇數度結點,證明u和v必是連通的。證明：反證法，假設u和v不連通，那么

11、他們必然分布于此圖的兩個連通分支中。那么它們將分別是各連通分支中唯一的奇數度結點。根據握手定理，一個圖中奇度點的個數為偶數。而兩個連通分支中，奇度點的個數為奇數。矛盾。矛盾的產生，是由于假設不連通導致的，因此，題設結論成立16. 證明:G是二部圖當且僅當G的回路都是偶長回路。證明：設二部圖G，頂點分為兩個集合V1 ，V2 充分性：先證明在二部圖中，奇長路的道路的兩個端節(jié)點一定分別在兩個頂點集合中，對道路長度使用歸納法，（1） 當道路長度為1是，根據二部圖的定義，每條邊的兩個頂點分別在兩個點集合中，結論成立（2） 假設道路長度為2n-1 ( n2)時結論成立（3） 當道路長度為2n+1時，設P=

12、v1v2v2n-1v2nv2n+1,在此路徑上刪除最后兩個結點，那么道路P將變?yōu)殚L度為2n-1的奇長道路，根據假設，v1,v2n-1分別在兩個頂點集合中，那么v2n和v1在同一頂點集合中，而v2n+1和v1在不同頂點集合，結論成立因為G中的任何回路，寫成道路的形式，起點和終點時一個結點，當然在同一個頂點集合中，因此長度必為偶數；必要性：（僅對連通分支證明）在圖中任意取一點著色為白色，將和此點最短距離為奇數的點著色為黑點，為偶數的著色為白點，那么將結點分為白色和黑色連個點集，任何同色點之間沒有邊相連。否則將形成奇數長度的回路，例如同色結點v1，v2 相鄰，那么從初始著色點v開始通過最短路徑可以形

13、成如下回路vv1v2v,因為vv1,v2v長度和為偶數，那么回路vv1v2v長度為奇數，與題設矛盾。所以是二部圖17.設(n, m)簡單圖G滿足,證明G必是連通圖。構造一個的非連通簡單圖。證明：假設G不連通，分支G1，G2，那么他們的邊數的最大值（）（）（）（）（）（）（）（），所以，只有當k=1時，才能滿足題設要求，G是連通圖。如果將頂點集合分成兩個點集，|V1|=1，|V2|=n-1,構成如下的有兩個分支的非連通簡單圖，G1=（1，0），G2=Kn-1,滿足題設條件18. 設G是階數不小于3的連通圖。證明下面四條命題相互等價:(1）G無割邊；(2) G中任何兩個結點位于同一回路中；(3)

14、G中任何一結點和任何一邊都位于同一回路中；(4) G中任何兩邊都在同一回路中。證明：（1）=（2）因為G連通，且G無割邊，所以任意兩個結點u,v，都存在簡單道路p=uwv.又因為G無割邊，所以，刪除邊wv后，子圖依然連通，即w,v存在簡單道路p,以此類推，可以找到一條核p每條邊都不相同的p=vu,這樣p和p就構成了一條回路。（2）=（3）因為G中任意兩個結點都位于同一回路中，所以任意結點u,和任意邊e的兩個端點v1,v2都分別在兩個回路C1，C2中，如果C1=C2=uv1v2u,那么將回路中v1v2,用v1v2=e替換，就得到新的新的回路，并滿足要求。如果C1C2，C1=uv1u,C2=uv2

15、u,那么構成新的道路P=uv1uv2u,在其中將重復邊剔出掉，得到新的回路C3，其中包含v1,v2結點，可以將回路中v1v2用v1v2=e替換，就得到新的新的回路，并滿足要求.（3）=（4）對任意兩條邊e1,e2其端點分別為u1,u2,v1,v2。根據（3）存在回路C1 = u1v1v2u1,C2=u2v1v2u2。那么可以形成新的閉道路P=u1v1v2u2v1v2u1,在其中將重復邊剔出到，得到新的回路C3，其中包含e2和u1,u2結點，可以將回路中u1u2用u1u2=e1替換，就得到新的新的回路，包含e1,e2,滿足要求.(4)=(1)因為任意兩條邊都在同一回路中，所以不存在割邊。假設邊e

16、是割邊，那么刪除此邊，圖不連通，分支中的任何一對不在同一分支中的邊，不能構成回路，與條件矛盾。所以，G中無割邊19. 設G=(V,E)是點度均為偶數的連通圖。證明:對任何。證明：G-v最多產生d(v)個奇數度點，又因為每個連通分支中奇數度點的個數是偶數，即G-v的連通分支最少有兩條邊和v相連，所以總連通分支數小于等于d(v)/2hong(1).2.20. 證明:圖中距離滿足歐幾里德距離的三條公理。證明：（1）d(u,v)0,即任何兩個結點之間的最短路長度大于等于0顯然，結點與自己之間的距離為，而和其他結點之間的最短距離不為。（）（，）（，），兩個結點之間的最短距離相等顯然，如果長度為的最短道路

17、p=uv ，即使u到v的最短道路，也是v到u的最短道路。（3） d(u,v)+d(v,w)d(u,w)假設d(u,v)+d(v,w)d(u,w)，那么最短道路P=uw ,就不是最短道路，因為另一條道路p=uvw其長度小于，與最短道路相矛盾，因此原結論存立21. 證明:在非平凡連通圖G中,e為割邊的充要條件是它不包含于G的任何圈中。證明：1） e為割邊 =e不包含于G的任何圈中假設e包含在某一圈Ci中，那么刪除此邊，但邊關聯的兩個鄰接點依然連通，所以沒有破壞原圖的連通性。因此不是割邊，矛盾。所以假設不成立，既e不包含于G的任何圈中； 2）e不包含于G的任何圈中 =e為割邊假設e為割邊，那么刪除此

18、邊，生成子圖依然連通。e關聯的兩個鄰接點有基本道路存在，此基本道路連同e構成一個圈。與題設矛盾。所以假設不成立，既e為割邊。根據1），2)可知，題設結論成立22. 證明:若G是3度正則的簡單圖,則。（請馮老師幫助解答下）證明：23. 證明:在具有n（n2）個結點的簡單無向圖G中，至少有兩個結點的度數相同。 證明：此題可用鴿籠原理，因為n個結點的簡單無向圖G中，結點的度數只可能是0，1，2n-1這n個數，又因為如果有結點的度數為0，那么就不可能有結點的度為n-1，反之也然。所以n 個結點，最多有n-1種度數，其中必有至少兩個結點的度數相同24. 設G是的簡單圖。證明:G中必有長度至少為的圈。證明

19、：設是滿足題設要求圖中的最長基本道路，那么（），（）都應該大于等于。那么，u,v的鄰接點都應該在道路p 上，否則此道路可以延長，與其是最長路假設矛盾。如果u，v是鄰結點，那么可以構成一個圈c= uvu，其長度。如果，不是鄰結點，那么從的終點開始刪除點，直到其為的鄰結點為止，得到道路,可知道路p，依然保持的所有鄰結點都在上的性質，所以可構成一個圈，其長度，證畢25. 證明:G是單向連通圖當且僅當存在一條包含G中全部結點的有向道路。證明：假設不存在包含全部結點的有向道路，那么設是中最長的有向道路，且結點不包含在此有向道路中。和此道路中任何中間結點都不可能雙向可達，且不能到達，且也不能到達，否則，此

20、最長路可擴充。那么由于道路上的每個結點和都單向可達，所以此最長路和之間的可達關系必然如下圖所示：為偶數為奇數當為偶數時，道路可擴充為v1vk/2uvk/2+1vk,而當為奇數時，不管與之間是如何單向可達的，都可以構造出更長的有向道路，矛盾，所以中一定存在包含所有結點的有向道路26. 無向圖G如圖10.32所示，先將此圖頂點和邊標出，然后求圖中的全部割點和割邊。圖10.32解：標注如下所示：根據標記后的圖，可求得割點分別為：，割邊分別為：，27. 求圖10.33的全部強分圖和單向分圖。圖10.33解：將圖重新標記如下：那么此圖的鄰接矩陣為，通過計算可求得其強分圖矩陣為：因此，此圖有兩個強分圖，一

21、個包含一個結點，一個包含其它的個節(jié)點。由于兩個強分圖之間存在有向道路，因此全部個結點，構成了單向分圖28. 證明：一個連同無向簡單圖中，任意兩條最長路至少有一個公共頂點。證明：假設兩條最長路，沒有公共點，那么兩條道路上的點集之間就有道路相連，否則就不是連通圖了。設此道路起點是上點，終點是上的點可根據如下情況進行調論：（），是，的中間結點，那么可構成新道路，此路至少比長1，矛盾。（2）假設m和w不能均分p1,p2,那么可以將兩個長路段和m,w之間的道路進行拼接，那么可得到比p1長的道路，與，是最長路矛盾。因此任意兩條最長路至少有一個公共頂點29. 證明：若G是n階無向簡單圖，G中每一對不相鄰的頂

22、點的度數之和至少是n-1，則G是連通圖。證明：假設G不是連通圖，G1，G2 是G的兩個連通分支，分別為n1,n2階連通無向簡單子圖，則n1+n2n。對G1中任意結點v1,和G2中任意結點v2而言，v1的最大點度為n1-1,v2的最大結點度為n2-1;則v1,v2的點度之和，最大為n1+n2-2n-21,則vi1的所有鄰接點(v1,v2,vl)都在P中，那么在T中可以找到一個回路,那么截取道路P, 得到回路C= vi1 vl vi1 .與T中無回路矛盾。對于d(vik)1時同理。因此，假設不成立，即最長道路P的起點和終點都是T的葉節(jié)點3. n（n3）階無向樹T的最大度至少為幾？最多為幾？解：當T

23、中只有一個枝點時， = n-1,為最大值。 當T構成一條鏈時，只有兩個葉結點，其余結點都為2度點，此時 = 2，為最小值，因此至少為2 ，最大為n-14. n（n3）階無向樹T的最大度=2，則T中最長的簡單道路為幾？解：根據第3題結論，當無向樹T的最大度=2時 ，T構成一條鏈，以此最長的簡單道路包含所有的節(jié)點，道路長度L=n-15. 證明：任何無向樹都是二部圖。證明：以樹中任意結點為起點，將與最短距離為偶數的結點放入結點集合，將與最短距離為奇數的結點放入結點集合，那么這兩個結點集合中，顯然不存在公共點，同時兩個結點集合組成了樹的全部結點，因此是數的結點集合的一個分化。假設在集合中存在兩個結點，

24、是鄰結點，那么就存在如下道路：，其中代表到的最短路徑，代表到的最短路徑，且邊不在最短路徑上，否則他們的最短路徑不是同奇偶的；因此，中包含圈，這與樹中無圈相矛盾，所以中的邊，只能存在于兩個點集合之間，所以是二部圖6. 證明：如果T是樹且k，則T中至少有k個葉結點。證明：當T為非平凡樹時，根據T的定義，T中每個枝點都是割點，當刪除d(v)= 的節(jié)點時，（T-v）= ，每個分支都是數，如果分支都是平凡樹，則這些節(jié)點都是T的葉，葉節(jié)點數為。如果分支有非平凡數，那么至少有兩個葉節(jié)點，其中至少一個是刪除v時就存在的，因此總的葉節(jié)點個數k。因此中至少有個葉結點7. 設G為n（n3）階簡單圖，證明G或中必含圈

25、。（有誤，4,p223）證明：反證法，假設G和中都不含圈，那么G和的所有分支都是樹。則G所包含的最大邊數|E(G)|=n-1, 則所包含的最大邊數|E()|=n-1. 因為G及的邊數總和|E(G)|+ |E()| = n(n-1)/2, 但根據假設條件，max|E(G)|+max |E()|=2(n-1) n(n-1)/2, 矛盾.因此，G或中必含圈8證明：恰好有兩個頂點的度為1的樹必為一道路P。證明：因為此樹僅有2個葉結點，因此 m = n-k15. 證明: 簡單連通無向圖G的任何一條邊，都是G的某一棵生成樹的邊。證明：簡單連通無向圖G的任何一條邊，要么是割邊，要么是非割邊。如果是割邊，那么

26、此邊是所有生成樹的樹邊；如果不是割邊，設邊為，那么G-e連通，可以求出生存樹，此也是的生存數，且不包含，那么是的樹補邊。則+e,有唯一一個圈，刪除圈上任意一條非邊，便得到一顆包含邊的樹16. 證明:在完全二又樹中,邊的數目等于2(t -1)，式中t是葉的數目。證明：設中的結點數為，枝點數為；根據完全二叉樹的定義，有下面的等式成立。n=i+t,m=2i,m=n-1.解方程組，得到m=2(t-1) 17. 決定一個m叉樹中內部道路長度之和與外部道路長度之和的關系。解：根據完全二叉樹的內部道路長度之和與外部道路長度之和的關系猜測m叉樹中內部道路長度之和與外部道路長度之和的關系為：（）其中表示各葉結點

27、的道路長度之和，表示各分支點道路長度之和，表示分支結點數。下面對分支結點數進行歸納：時，故（）成立假設是結論成立當是，設在完全叉樹中，是一個道路長度為的分支點且其個兒子，都為葉結點，那么，是含個分支點的完全叉樹。由歸納假設有（），比較和，（）（），所以（）（）（）（）18. 給出公式的根樹表示。解：將標示符號看成葉結點，邏輯連接詞作為分支結點，按公式的先后順序構造根樹如下：PQPRPQ19. 給定權1,4,9,1,2,6,4,6,8,10,構造一個最優(yōu)二叉樹。解：根據帶權最優(yōu)二叉樹定理構造過程如下：1 4 9 1 2 6 4 6 8 101 1 2 4 4 6 6 8 9 10 重新排序= 2

28、 2 4 4 6 6 8 9 10 = 4 4 4 6 6 8 9 10 = 8 4 6 6 8 9 10 = 8 10 6 8 9 10 = 8 10 14 9 10 8 9 14 10 10 交換10，9 = 17 14 10 10 = 17 14 20 = 31 20 = 511110249866420. 把圖11.14的有序林變換成一個二叉樹。解：STEP1:將每棵有序樹采用中間格式表達出來SETP2：再用一條有向道路把各分支的根從左到右連接起來SETP3：轉換為二叉樹。具體過程略21. 證明:正則二叉樹必有奇數個結點，且樹葉數t與結點數n之間有：t=（n-1）/2。證明：因為正則二叉

29、樹的邊數與分支點數的關系為：，又因為是樹，因此結點數滿足：，必為奇數。葉結點數和枝點數之和為，即：，因此t=（n-1）/222. 遍歷一棵樹是指訪問這個樹的每個結點一次且僅一次。遍歷二叉樹有如下三種方式: (1)前序遍歷:訪問根, 遍歷左子樹,然后遍歷右子樹。（2)中序遍歷: 遍歷左子樹,訪問根,然后遍歷左子樹。（3)后序遍歷: 遍歷左子樹, 遍歷右子樹,然后訪問根。根據三種不同遍歷形式,分別寫出圖11.15中各結點被訪問的順序。圖11.15解：（） 前序遍歷結果：abdfjglmcehi（） 中序遍歷結果：jfdlgmbachei（） 后序遍歷結果：jflmgdbhieca23. 設英文字母

30、b，d，g，o，y，e出現的頻率分別是0.014，0.038，0.02，0.08，0.131,構造一個與它們對應的前綴碼,并寫出符號串dogbybed對應的編碼。解：構造最優(yōu)樹如下：0.038(d)0.014，0.038，0.02，0.08，0.02，0.1310.014，0.02， 0.02，0.038，0.08，0.1310.034 0.02，0.038，0.08，0.1310.02 0.038，0.08，0.1310. 0.08，0.131 0.2830.1311110.08(o)0.131(e)0.014(b)0.02(g)01000010.0(y)因此獲得相應的前綴碼：b=00000

31、,g=00001,y=0001,d=001,o=01,e=1所以dogbybed的編碼為：完成題目 1，2，3,4，6，7，8，,14，,16，,18，19，20，22,23勘誤：題，頻率分別是0.014，0.038，0.02，0.08，0.131改為頻率分別是0.014，0.038，0.02，0.08，0.02，0.1317題， 設G為n（n3）階簡單圖，證明G或中必含圈改為設G為n（n）階簡單圖，證明G或中必含圈p223第十三題未證明習題十二1證明下面3個圖都是平面圖。證明：因為所給圖都可以平面圖的方式畫出來，如下：2下面3個圖都是平面圖，先給圖中各邊標定順序，然后求出圖中各面的邊界和面度

32、。解：略3. 設G是階數不小于11的圖。證明：G或中至少有一個是非平面圖。證明：假設G和都是平面圖，因為，所以至少有一個圖的邊數，設，有因為是平面圖，所以有，求解得與題設G是階數不小于11的圖矛盾，因此G或中至少有一個是非平面圖4. 證明：具有6個結點、12條邊的簡單連通平面圖，它的面的度數都是3。證明：因為是簡單連通平面圖，因此根據歐拉公式有，所以有個面。根據面度和與邊的關系有，（）；因為要在平面上圍成一個面，至少需要邊，所以個面，（）。因此，不存在面度大于的面，所有面的度數都是5. 證明：少于30條邊的簡單平面圖至少有一個頂點的度不大于4。證明：假設圖（，）的每個結點的點度都大于等于，根據

33、握手定理及平面圖的判定定理有：（）握手定理（）根據（）得到：0)個奇數度結點的連通圖。證明:G中必存在k條邊不相重的簡單道路P1,P2,Pk,使得E = E(P1)E(P2) E(Pk)。證明：只要將這2k個奇度點分成兩個集合V1 =v1,v2vk，V2=u1,u2uk,然后添加k條邊（vi，ui），將G圖變換成歐拉圖G。求出G 的歐拉回路C，將C中的添加的k 條邊刪除，得到k條簡單道路，這k 段簡單道路包含了G中的全部邊，結論得證3. 設G = (V,E)是不含奇度結點的非平凡圖。證明:G中必有k個邊不相重的回路C1,C2,Ck,使得E = E ( C1) E ( C2 ) E( Ck)。證

34、明：由題設可知，圖G的每個分支是歐拉圖，因此可求出每個分支歐拉回路Ci，且這些歐拉回路沒有重復邊，結論得證4. 設計一個由9個a,9個b,9個C組成的環(huán)形排列,使得由a,b,c組成的字長為3的27字中的每一個在排列中恰好出現一次。解：由a,b,c組成的字長為3的串，一共有27個，分別為：aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,caa,cab,cac,cba,cbb,cbc,cca,ccb,cccc,題意為，將9個a,9個b,9個c組成環(huán)形排列，在這個環(huán)形排列中，任意不同的排列在一起的三個字母按相同的順序寫出來，都不

35、相同。我們可以將a,b,c組成的字長為2的串aa,ab,ac,ba,bb,bc,ca,cb,cc作為有向圖的節(jié)點，每個節(jié)點將有三條出邊，出邊分別表示在2字串上添加上a,b,c之母，并形成3字串。三條出邊的匯入節(jié)點，分別是3字串的后兩個字母所代表的2字節(jié)點，畫出此圖如下：aabbccabbccaacbacbaaaaaaaaabbbbbbbbbccccccccc由圖可知，這是一個歐拉圖，因為每個節(jié)點有3條出邊，3條入邊。找出一條歐拉回路，并將邊上的字母寫出及得到合乎要求的環(huán)排列：aaababcccaacbcabbcbbacaccb 5. 在圖13.10中求中國郵遞員問題的解。解：略，請參考書中解法

36、6. 設G是有兩個奇度點的連通圖,設計一個構造G的歐拉道路的算法。解：step1: 添加連接兩個奇度點的邊Step2: 調用一般的歐拉回路的算法Step3:在回路中刪除添加的邊7. n為何值時，無向完全圖Kn是歐拉圖？n為何值時，無向完全圖Kn僅存在歐拉道路而不存在歐拉回路？解：當n為大于2的奇數時，無向完全圖Kn是歐拉圖，因為每個節(jié)點的度數為偶數。當n為2時，K2，是唯一存在兩個奇度點的完全圖，因此此圖只存在歐拉道路8. n（n2）個結點的有向完全圖中，哪些是歐拉圖？解：n（n2）個結點的有向完全圖中，每個都是歐拉圖，因為每個節(jié)點都有相同的入度和出度，可以找到有向歐拉回路9. 證明:凡有割點

37、的圖都不是哈密頓圖。證明：反證法，假設存在有割點v的圖是哈密頓圖，那么此圖存在哈密頓圈。在此圈中刪除割點v，那么剩下的節(jié)點依然連通。這和割點的定義相矛盾，所以題設命題成立10. 證明: 4k+l階的所有2k正則簡單圖都是哈密頓圖。證明：因為圖是的正則簡單圖，因此對任意的u，vV, 有d(u) + d(v) = 4k. 根據定理13.4，存在哈密頓道路P= v1v2v4k+1. 1）如果 v1v4k+1E, 則v1v2v4k+1v1構成一個H圈；2）如果v1v4k+1E，則是v1的鄰接點，那么必為v4k+1的鄰接點。否則，v4k+1點度為4k-1-2k=2k-1,與題設矛盾。假設vit-1v4k+1E，那么可構造H圈如下：v1vit-1v4k+1 v4kvitv1因此，此圖為哈密頓圖11在無向完全圖Kn中有多少條沒有公共邊的哈密爾頓回路？解：1) 設n=2k+1,將節(jié)點編號為0,1,22k,并作如下圖示，1234kK+1K+202k2k-12k-2K+3在上圖中先取一條哈密頓回路為0,1,2,2k,3,2k-1,4,k+3,k,k+2,k+1,0,然后將圓周上的結點按逆時針方向依次轉動一個位置，然后可以得到另一條回路為：0,2,3,1,4