第8章習題解答1.（1）有歐拉回路（2）（3）（6）沒有歐拉回路，沒有歐拉通路（4）（5）有歐拉通路2.構造歐拉圖使滿足條件：(1)m和n奇偶性相同；(2)m和n奇偶性相反。解：mm和n奇偶性相同m和n奇偶性相反3、n為何值時，無向完全圖Kn是歐拉圖？n為何值時，無向完全圖Kn僅存在歐拉通路而不存在歐拉回路？解：當n為大于2的奇數時，無向完全圖Kn是歐拉圖，因為每個節點的度數為偶數。當n為2時，K2，是唯一存在兩個奇度點的完全圖，因此此圖只存在歐拉通路4.（1）有歐拉回路（3）沒有歐拉回路，沒有歐拉通路（2）有歐拉通路5.（1）（2）（4）（5）有哈密頓回路（3）沒有哈密頓回路，沒有哈密頓通路（6）有哈密頓通路6.(1)畫一個有一條歐拉回路和一條漢密頓爾回路的圖.(2)畫一個有一條歐拉回路但沒有一條漢密頓爾回路的圖.(3)畫一個沒有一條歐拉回路,但有一條漢密頓爾回路的圖.7.能8.是，不是9.(1)是哈密爾頓圖。一條哈密爾頓回路為：abcihgfeda。(2)不是哈密爾頓圖。10.可能11.是12.設G為n(n>=3)階無向簡單圖,邊數m=(1/2)(n-1)(n-2)+2，證明G是哈密爾頓圖。證明:反證法：假設存在不相鄰的結點vi，vj∈V，有dev(vi)+dev(vj)≤n-1。另V1={vi，vj}，G1=G-V1，則G1是（n-2）階簡單圖，它的邊數m1滿足m1=(1/2)(n-1)(n-2)+2-(dev(vi)+dev(vj))≥(1/2)(n-1)(n-2)+2-(n-1)=(1/2)(n-2)(n-3)+1這與G1是(n-2)階的簡單圖矛盾（注：(n-2)階的簡單圖的最大邊數為(1/2)(n-2)(n-3)）所以G中任何兩個不相鄰的結點度數之和均大于等于n。再根據定理：設G=（V，E）是n階（n≥3）無向簡單圖，若對于任意的不相鄰的結點vi，vj∈V，有dev(vi)+dev(vj)≥n，則G是哈密爾頓圖。所以G是哈密爾頓圖。13.設G是無向連通圖，證明，若G中有橋或割點，則G不是哈密頓圖。證明：反證法，假設存在有割點v的圖是哈密頓圖，那么此圖存在哈密頓回路。在此回路中刪除割點v，那么剩下的節點依然連通。這和割點的定義相矛盾，所以G中有割點，則G不是哈密頓圖。另外，若G中有橋，橋的端點就是割點，所以題設命題成立。14.假定在n個人的團體中,任何2人合起來認識其余的n-2個人。證明:(1)這n個人可以排成一排,使得站在中間的每個人的兩旁都是自己認識的人,站在兩端的人旁邊各有1個認識的人； (2)當n≥4時,這n個人可以圍成一個圓圈,使得每個人兩旁都是自己所認識的人證明：（證：如果任意兩個人加起來認識其余的ｎ－２個人，那么每個人至少認識n-2個人。）將n個人看成圖的結點，相互認識則在相關兩個結點間有一條邊，構成一個簡單無向圖G。設u和v是兩個互相不認識的人，對除u和v外的任意一個人t，如果u和ｖ不認識t，則u和ｖ合起來認識n-3個人，和題意矛盾，因此ｕ和v都至少認識n-2個人。所以在此圖中，不相鄰的任意兩個結點滿足：d(u)+d(v)≥2(n-2)。當ｎ≥3時，任何兩個結點的點度之和d(u)+d(v)≥2(n-2)≥n-1,因此存在哈密頓道路，即這n個人可以排成一排,使得站在中間的每個人的兩旁都是自己認識的人,站在兩端的人旁邊各有1個認識的人；當n≥4,任何兩個結點的點度之和d(u)+d(v)≥2(n-2)≥n,因此圖中存在哈密頓回路，即這n個人可以圍成一個圓圈,使得每個人兩旁都是自己所認識的人。15.求圖中結點a到其他所有結點的最短路徑和距離解:由Dijkstra算法可得:(1)初始P={a} D(a)=0,D(b)=4,D(c)=3,D(d)=∞,D(e)=∞,D(f)=∞,D(g)=∞,D(z)=∞(2)P={a,c} D(b)=min{4,2+3}=4,D(d)=∞,D(e)=min{∞,3+8}=11,D(f)=∞,D(g)=∞ D(z)=∞(3)P={a,b,c} D(d)=min{∞,4+3}=7,D(e)=min{11,4+∞}=11,D(f)=∞,D(g)=∞,D(z)=∞(4)P={a,b,c,d} D(e)=min{11,7+1}=8,D(f)=min{∞,7+5}=12,D(g)=∞,D(z)=∞(5)P={a,b,c,d,e} D(f)=min{12,8+3}=11,D(g)=min{∞,8+5}=13,D(z)=∞(6)P={a,b,c,d,e,f} D(g)=min{13,11+2}=13,D(z)=min{∞,11+4}=15(7)P={a,b,c,d,e,f,g} D(z)=min{15,13+3}=15故a到其他所有結點的最短路徑和距離如下: 最短距離 最短路徑a-b 4 {a,b}a-c 3 {a,c}a-d 7 {a,b,d}a-e 8 {a,b,d,e}a-f 11 {a,b,d,e,f}a-g 13 {a,b,d,e,f,g}or{a,b,d,e,g}a-z 15 {a,b,d,e,f,z}16.求圖中A到其余各結點的最短路徑和距離。解:由Dijkstra算法可得:(1)初始P={A} D(A)=0,D(B)=1,D(C)=∞,D(D)=∞,D(E)=4,D(F)=∞(2)P={A,B} D(C)=min{∞,8}=8,D(D)=∞,D(E)=min{1+2,4}=3,D(F)=min{∞,6}=6 (3)P={A,B,E} D(C)=min{8,3+1+3}=7,D(D)=∞,D(F)=min{6,3+1}=4(4)P={A,B,E,F} D(C)=7,D(D)=min{∞,4+6}=10(5)P={A,B,E,F,C} D(D)=min{10,7+2}=9故a到其他所有結點的最短路徑和距離如下: 最短距離 最短路徑A-B 1 {A,B}A-C 7 {A,B,E,F,C}A-D 9 {A,B,E,F,C,D}A-E 3 {A,B,E}A-F4{A,B,E,F}17.（1）（4）是二分圖，（2）（3）不是二分圖18.（1）n=2（2）n為偶數（3）n為任何數都不是（4）n不等于0的整數19.證明:如果簡單圖G是二分圖,有n個結點m條邊,則m<=n2/4證明:設G=<X,E,Y>為二部圖,則|X|=n1,<Y>=n-n1當G為完全二分圖時,其邊數m最大,為n1*(n-n1),即是說,m滿足:m<=n1*(n-n1)=n2/4-(n1-n/2)2<=n2/4即m<=n2/4得證20.可以21.（1）（3）是，（2）不是22.（1）6，（2）223、證明：少于30條邊的簡單平面圖至少有一個頂點的度不大于4。證明：假設圖Ｇ（ｎ，ｍ）的每個結點的點度都大于等于５，根據握手定理及平面圖的判定定理有： ５ｎ≤２ｍ＜６０ （１）握手定理 ｍ≤３ｎ－６ （２）根據（１）得到：ｎ<１２結合（１）（２）得到：５ｎ／２≤３ｎ－６，所以ｎ≥１２，矛盾。因此假設不成立，題設結論成立■24.證明:每個面至少有4條邊的任何連通簡單平面圖中,m≤2n-4,其中n為結點數,m為邊數.證明：設這個圖的面數為r，由歐拉公式n－m+r=2得r=m-n+2。因為對于每個面R,有deg(R)≥4，所以2m=∑deg(R)≥4(m-n+2)，解得m≤2n－4證明：設G的面數為f,所有面的度數之和為2m.因為G的每個面至少由k條邊圍成，所以2m≥k?f。再由歐拉公式的推廣，有f=p+1+m?n。由上兩式消去f26、證明：在6個結點12條邊的連通平面簡單圖中，每個面的面度都是3。證：n=6,m=12歐拉公式n-m+f=2知f=2-n+m=2-6-12=8由圖論基本定理知：，而，所以必有，即每個面用3條邊圍成。27、(設G是簡單圖，若階數不小于11，證明：G或G中至少有一個是非平面圖。證明：假設G和G都是平面圖，因為ｍＧ＋ｍＧ＝ｎ（ｎ－１）２，所以至少有一個圖的邊數，設ｍＧ≥ｎ（ｎ－１）4，又因為是平面圖，所以有３ｎ?27、設G是簡單圖，若結點數n<8，則G和G至少有一個是平面圖。證明：假設G和~G都是非平面圖，因為ｍＧ＋ｍ~Ｇ?＝ｎ（ｎ－１）/２，所以至少有一個圖的邊數≤?ｎ（ｎ－１）/4?，設ｍＧ≤?ｎ（ｎ－１）/4?，又因為是非平面圖，所以有３ｎ?６≤ｍＧ≤?ｎ（ｎ－１）/4?，求解得ｎ>11．與題設G是階數小于8的圖矛盾，因此G或(~G

)?中至少有一個是平面圖.證明：當結點數n<5時，G和G都是平面圖。當節點數5≤n<8時，若G為非平面圖，則G包含有子圖K5（1）若G包含有子圖K5，則G中有5個節點的度數大于等于4，這時G中有5個節點度數小于等于2，其余最多2個節點度數小于等于6。G中不會包含K5或K3,3子圖，（2）若G有6個結點且包含有子圖K3,3，則G中有6個結點度數至少為3度，則補圖中的這6個結點至多為2度，不包含K3,3和K5，G是平面圖。若G有7個結點且包含有子圖K3,3，該子圖K3,3的兩個結點集V1和V2，在補圖G中的V1中