設(shè)n階無向完全圖的邊數(shù)為m

1、 第5章 圖論P 190: 31. 設(shè)n階無向完全圖的邊數(shù)為m，則圖中所有點的度數(shù)和為2m。 而n階無向完全圖的每個頂點都與其它頂點相鄰，故圖中每個點度數(shù)都為n-1， 進而所有點的度數(shù)和為n*(n-1)。 因此2m=n(n-1)，故m=n*(n-1)/2。2. 設(shè)n階有完全圖的邊數(shù)為m，則圖中所有點的度數(shù)和為2m。 而n階無向完全圖的每個頂點都與其它頂點都有兩條方向相反的邊相連，并且有自回路，故圖中每個點度數(shù)都為2(n-1)+2=2n， 進而所有點的度數(shù)和為2n*n=2n2。 因此2m=2n2，故m=n2。3. 需證：即證：又 由G的底圖為k正則可知：對所有i1,2,3,n，故 045同構(gòu)映射

2、g為：g(a)=a； g(b)=b； g(c)=c； g(d)=d； g(e)=e； g(f)= f；7（注意：同構(gòu)圖只列出其中一個）8由G是3正則可知：m=3n/2，由前提可知：3n/2=2n-4，故3n/22n-4，即n8。9競賽圖P203 作業(yè)：3、51、(a) 強連通；(b) 弱連通；(c) 單向連通；(d) 強連通圖；2、G的主子圖G-c不連通。3、4、假設(shè)一個包含兩個分支分的n階圖兩個分支的頂點數(shù)分別為x和y，則x+y=n。(1) 因為包含m個頂點的連通圖至少包含m-1條邊，故G1和G2各至少包含x-1和y-1條邊，所以該n階圖至少包含x-1+y-1x+y-2條邊，而x+y=n，故

3、該n階圖至少包含n-2條邊。(2) 當(dāng)n階圖的兩個分支都是無向完全圖時，兩個分支包含的邊數(shù)最多，設(shè)為m，則m = x(x-1)/2+y(y-1)/2=1/2(x+y)2-(x+y)-2xy)=1/2(n2-n-2xy)當(dāng)x=1，y=n-1或x=n-1,y=1時，xy取值最小，即m取最大值1/2(n2-3n+2) 故該n階圖的邊數(shù)最多為1/2(n2-3n+2)。5、bcdefghiz1063¥¥¥¥¥10611¥¥¥¥1011¥911¥911¥11¥111311161

4、31116121515a到z的最短路徑為：aedcfgz；邊權(quán)和為：14P：216：作業(yè)：4和81. 2. 題目所給的序列共有6個數(shù)，故序列對應(yīng)的圖應(yīng)該有6個結(jié)點。根據(jù)無向樹的性質(zhì)，6個結(jié)點的無向樹有5條邊。再根據(jù)握手定理，圖中所有結(jié)點的度數(shù)之和等于邊數(shù)的兩倍，因此6個結(jié)點的無向樹所有結(jié)點的度數(shù)之和為5*2=10。因此只有第(4)個序列滿足這個條件，并且第(4)個序列能對應(yīng)以下無向樹： 3. 證明：設(shè)無向樹T=<V,E>, 設(shè)|V|=n，則|E|=n-1 因為T是連通圖，因此，對于任意vÎV，有：d(v)³1。 根據(jù)握手定理，有：åvÎVd(

5、v)=2|E|=2n-2。 假設(shè)G中沒有葉子結(jié)點，則所有結(jié)點的度數(shù)至少為2，因此，åvÎVd(v)³2n，這與åvÎVd(v)=2n-2矛盾。故G中至少有一個葉子結(jié)點。 假設(shè)G中只有一個葉子結(jié)點t，即除去t，V中其他結(jié)點的度不小于1。 因此，有: åvÎVd(v)³2(n-1)+1=2n-1，這與åvÎVd(v)=2n-2矛盾。故G中至少有兩個葉子結(jié)點。4. 設(shè)T中共有x個5度點，則T總共有13+1+2+x=16+x個結(jié)點，因此共有16+x-1=15+x條邊。根據(jù)握手定理可知：所有結(jié)點度數(shù)之和等

6、于邊數(shù)的兩倍。故13+1´3+2´4+x´5=2´(15+x)，解得x=2。即T中有2個5度點。5. 設(shè)T中共有x個葉子結(jié)點。則T共有x+100+5+2+7=x+114個結(jié)點，因此共有x+114-1=x+113條邊。根據(jù)握手定理可知：x+100´2+5´3+2´4+7´5=2´(x+113)，解得：x=32。即T中包含32個葉子結(jié)點。6. 設(shè)T中共有x個葉子結(jié)點，則T中共有x+n2+nk個結(jié)點，因此共有x+n2+nk-1條邊。根據(jù)握手定理可知：x+å2£i£kini =2&#

7、180;(x+å2£i£kni)，解得：x=å2£i£kini-2å2£i£kni。7. 證明：假設(shè)T中存在一個結(jié)點v，滿足d(v)³k+1，則與v關(guān)聯(lián)的邊至少有k+1條。由樹的性質(zhì)可知：在樹中刪除任意一條邊，圖變?yōu)榉沁B通圖。因此，若刪除與v關(guān)聯(lián)的所有邊，則至少得到k+2個連通分支。其中一個分支是孤立點v。在其余k+1個分支中，若分支僅包含一個結(jié)點，則該結(jié)點在T中為葉子結(jié)點；若分支至少包含兩個結(jié)點，則由練習(xí)3的結(jié)論可知，該分支至少包含兩個葉子結(jié)點，其中一個葉子結(jié)點必為原樹T中的葉子結(jié)點。因此，T

8、至少包含k+1個葉子結(jié)點。這與T中有k片葉子矛盾。因此，T中任意結(jié)點v滿足：d(v)£k。8. 紅邊的導(dǎo)出子圖為最小生成樹9. 證明：由樹的性質(zhì)可知：二元樹的頂點數(shù)=m+1。在完全二元樹中，除去根結(jié)點，其它結(jié)點的度數(shù)都為3或1。因此，所有頂點的度數(shù)和為：t+1´2+3´(m+1-t-1)=3m-2t+2根據(jù)握手定理：2m=3m-2t+2。故m=2(t-1)。10. 在完全三元樹中，根結(jié)點的度數(shù)為3，除去根結(jié)點，設(shè)其它內(nèi)部結(jié)點的數(shù)目為x，則，這些結(jié)點的度數(shù)為4；葉子結(jié)點的度數(shù)為1，設(shè)有y個。則所有結(jié)點的度數(shù)和為3+4x+y，由握手定理可知：3+4x+y為偶數(shù)，故y必

9、須為奇數(shù)，即葉子結(jié)點數(shù)目必須為奇數(shù)。11. 12. 高度最大為：2n-1；最小高度為n13. 最多有nh片樹葉；最少有(h-1)(n-1)+n=h(n-1)+1片樹葉。14. 若有向圖的鄰接矩陣中有一列值全為0，其它每列中僅有一個元素值為1。則該鄰接矩陣所表示的圖為有向樹。值全0的列的表頭元素所代表的結(jié)點為根結(jié)點；行全為0的表頭元素所代表的結(jié)點為樹葉結(jié)點。P228：作業(yè)1、(a)、(e)是歐拉圖；(c)(d)是半歐拉圖；(b)不是歐拉圖。2、n為奇數(shù)3、將每個房間用圖上的一個結(jié)點表示，兩個房間之間若能通過一扇門連通，則在代表這兩個房間的結(jié)點之間用一條邊連接。則得到下圖，問題等價于是否存在起始于

10、x結(jié)點，終止于P結(jié)點的歐拉通路。X結(jié)點度數(shù)為偶數(shù)，P度數(shù)為奇數(shù)，故不存在起始于x結(jié)點，終止于P結(jié)點的歐拉通路。4、(并非一定是下面這些圖，只要滿足題目條件即可) K5 (1) (2) (3) (4) 5、本問題等價于在圖中增加權(quán)值和盡量少的邊，使得添加邊后的圖為歐拉圖。6、 (并非一定是下面這些圖，只要滿足題目條件即可) (1) (2) (3) (4)7、證明：任選n階無向完全圖G中兩點u和v。設(shè)被刪除的邊集為E，令G=G-E。 若u與v相鄰，則被刪除的n-3條邊中至多有一條邊同時關(guān)聯(lián)u與v，其余n-4條邊至多只關(guān)聯(lián)u與v中一個頂點。故dG(u)+ dG(v)³ dG(u)+ dG(

11、v)-(2+n-4)= dG(u)+ dG(v)-(n-2)。而由G是n階無向完全圖可知，dG(u)=dG(v)=n-1。因此，dG(u)+ dG(v)³2n-2-(n-2)=n。故G為哈密頓圖。89、證明：不失一般性，假設(shè)G中有n個頂點，分別為v0,v1,v2,vn。因為圖G是哈密頓圖，故G中存在一條恰好經(jīng)過G中每個頂點的回路，不妨設(shè)該回路為v0v1v2vnv0。給G中的邊vivi+1添加從vi-1到vi的方向，其中i=0,1,n-1。給邊vnv0。添加從vn到v0的方向，G中其他邊的方向任意指定。這樣得到的有向圖設(shè)為G，則G中存在一條有向回路v0,v1,v2,vn。因此，G是一個

12、強連通圖。命題得證。10、證明：任選G中兩點u與v。由n為偶數(shù)可知：若n/2£k£n-1，則dG(u)+dG(v)=2k³n，因此G是哈密頓圖。若0<k£n/2-1，則G的補圖中每個結(jié)點的度數(shù)為(n-1)-k，故因此，是哈密頓圖。故G和其補圖至少有一個是哈密頓圖。P243244，作業(yè)：2、101、(b)、(c)是二部圖；(a)、(d)都有奇圈，故不是二部圖。2、證明：不妨設(shè)|V1|=n1,|V2|=n2， 則n1+n2=n。顯然， m£Kn1,n2包含的邊數(shù)，即m£n1×n2；而n1+n2=n，故當(dāng)n1=n2時，n1&

13、#215;n2取值最大。即n1×n2£(n/2)2=n2/4，故m£ n2/4。3、證明：設(shè)該簡單連通平面圖有r個區(qū)域。由每個區(qū)域由k條邊圍成可知：所有區(qū)域的邊數(shù)為kr；而每條邊分隔兩個區(qū)域，即在計算所有區(qū)域的邊數(shù)時被計算了兩次，故kr=2m 由歐拉公式可知：n-m+r=2 由式消去r可得：m=k(n-1)/(k-2)4、證明：對任意一個簡單平面圖G，(1)若G連通，則與課本P241：引理證明類似可證結(jié)論成立。(2)若G不連通，任選G的一個連通分支，設(shè)為G1，則G1為簡單連通平面圖，則由課本P241：引理可知：G1中至少存在一個度數(shù)小于等于5的頂點。5、證明：設(shè)G

14、為G的一個連通分支，則G為簡單連通平面圖，設(shè)G的頂點數(shù)為n，邊數(shù)為m。假設(shè)G中每個頂點的度數(shù)都大于等于5。則，G中所有頂點的度數(shù)和³5n；而根據(jù)握手定理：G中所有頂點的度數(shù)和=2m；因此，2m³5n 而由G是簡單連通平面圖可知：3n-6³m 由式可知：2m/5³n；由式可知：n³(m+6)/3，故2m/5³(m+6)/3，即m³30，這與題目條件：G的邊數(shù)小于30矛盾。故G中必存在度數(shù)小于等于4的頂點，因此，G中必存在度數(shù)小于等于4的頂點。6、證明：假設(shè)G的補圖是平面圖。設(shè)G有n個頂點，則由n階無向完全圖的邊數(shù)為n(n-1)

15、/2可知：G的補圖的邊數(shù)=n(n-1)/2-27。(1)若G連通由G是簡單平面圖可知：2n-6³27，故n³11 不妨設(shè)G的補圖有k個連通分支，第i個連通分支的頂點數(shù)為ni，邊數(shù)為mi。而åmi=n(n-1)/2-27。由G的補圖是簡單平面圖可知：G的補圖的每個分支也是簡單平面圖。因此 3ni-6³mi，進而å1£i£k(3ni-6)³ åmi，即3n-6k³ n(n-1)/2-27，而由k³1可知：3n-6³ n(n-1)/2-27化簡可得：n2-7n-42£0

16、而當(dāng)n³11時，有：n2-7n-42>0恒成立，故式與式矛盾。故當(dāng)G連通時，G的補圖不是平面圖。(2) 若G不連通不妨設(shè)G有k個連通分支，第i個連通分支的頂點數(shù)為ni，邊數(shù)為mi。顯然，G的每個分支都是連通簡單平面圖，故3ni-6³mi，進而，å1£i£k(3ni-6)³ åmi=27。即3n-6k³27，由k³2可知：3n-6>27，因此：n³11 由G不連通可知：G的補圖連通。又因為G的補圖為簡單平面圖，故則3n-6³n(n-1)/2-27，化簡可得：n2-7n-42&

17、#163;0 而當(dāng)n³11時，有：n2-7n-42>0恒成立，故式與式矛盾。因此，故當(dāng)G不連通時，G的補圖不是平面圖。 綜上所證，G的補圖不是平面圖。7、證明：6個頂點的無向完全圖共有(6×5)/2=15條邊。而且G是簡單圖，故G是由K6中刪除兩條邊得到。不難看出，從K6中任意刪除兩條邊得到的圖一定是連通圖，故G連通。假設(shè)G是平面圖，則有3×66³13，顯然不成立。故G不是平面圖。設(shè)G是由K6刪除e1和e2兩條邊得到。由于e1和e2共為G中的點貢獻了4度，故任選G中兩個頂點u和v則有：d(u)+d(v)³55-4=6。故G是哈密頓圖。8、證明：(1) 證法一：(a)圖的邊數(shù)為13，頂點數(shù)為6，不滿足平面圖的必要條件3n6³13，故(a)不是平面圖。證法二：將(a)圖中的c點刪除，得到K5，故K5是(a)的子圖，即(a)不是平面圖。(2) 從圖(b)中刪除h結(jié)點，刪除邊：(d,c)、(d,e)、(a,c)、(e,g)可得一個二度同構(gòu)與K3,3的子圖，故(b)不是平面圖。9、根據(jù)自對偶圖的性質(zhì)，5個點的對偶圖G的邊數(shù)為2&#