電子科技大學 圖論第三次作業(yè) 楊春

電子科技大學圖論第三次作業(yè)楊春電子科技大學圖論第三次作業(yè)楊春電子科技大學圖論第三次作業(yè)楊春電子科技大學圖論第三次作業(yè)楊春編制僅供參考審核批準生效日期地址：電話：傳真:郵編:圖論第三次作業(yè)第六章習題2.證明：根據(jù)歐拉公式的推論，有m≦l*(n-2)/(l-2),(1)若deg(f)≧4,則m≦4*(n-2)/2=2n-4;(2)若deg(f)≧5,則m≦5*(n-2)/3,即：3m≦5n-10;(3)若deg(f)≧6,則m≦6*(n-2)/4,即：2m≦3n-6.3.證明：∵G是簡單連通圖，∴根據(jù)歐拉公式推論，m≦3n-6;又，根據(jù)歐拉公式：n-m+φ=2,∴φ=2-n+m≦2-n+3n-6=2n-4.4.證明：(1)∵G是極大平面圖，∴每個面的次數(shù)為3，由次數(shù)公式：2m=f∈φdeg?由歐拉公式：φ=2-n+m,∴23(2)又∵m=n+φ-2,∴φ=2n-4.(3)對于的極大可平面圖的的每個頂點，有，即對任一一點或者子圖，至少有三個鄰點與之相連，要使這個點或子圖與圖G不連通，必須把與之相連的點去掉，所以至少需要去掉三個點才能使，由點連通度的定義知。5.證明：假設圖G不是極大可平面圖，那么G不然至少還有兩點之間可以添加一條邊e，使G+e仍為可平面圖，由于圖G滿足，那么對圖G+e有，而平面圖的必要條件為，兩者矛盾，所以圖G是極大可平面圖。6.證明：(1)由知當n=5時，圖G為，而為不可平面圖，所以，（由和握手定理有，再由極大可平面圖的性質(zhì)，即可得）對于可平面圖有，而，所以至少有6個點的度數(shù)不超過5.(2)由和握手定理有，再由極大可平面圖的性質(zhì)，即可得，對于可平面圖有，而，所以至少有12個點的度數(shù)不超過5.8.證明：(1)由握手定理和極大可平面圖的性質(zhì)，可得對恒成立，又，所以，即。(2)由定理5，對簡單可平面圖都有，又圖G是的簡單連通平面圖，所以G中至少有3個點的度數(shù)小于等于5.(3)由定理5，對簡單可平面圖都有，又圖G是的簡單連通平面圖，所以G中至少有4個點的度數(shù)小于等于5.17.證明：利用反證法，假設存在6連通可平面圖，設G是6連通圖，則：k(G)≧6由惠特尼定理可得：δ(G)≧k(G)≧6,∴m>3n-6,這與G是簡單平面圖相矛盾，因此假設不成立，不存在6連通可平面圖19.證明：假設不存在面f,使得deg(f)≦5,則：2m=f∈φdeg?(f)由歐拉公式得：φ=2-n+m≦m3,于是得：2m≦另一方面，由δ(G)≧3得：2m≧3n>3n-6與上面得到結(jié)果相矛盾，所以假設不成立，G至少存在一個面f,使得：deg(f)≦5.第七章作業(yè)2.證明：設n=2k+1,∵G是Δ正則單圖，且Δ>0,∴m(G)=nΔ2=(2k+1)Δ2>kΔ,由定理5可知χ28.解：(1)又：=k(k-1)(k-2)2(k-3)+k(k-1)2(k-2)=k(k-1)(k-2)(k2-4k+5)=k(k-1)(k-2)2(k-3),所以，原圖色多項式為：k(k-1)(k-2)2(k2-4k+5)-k(k-1)(k-2)2(k-3)=k(k-1)(k-2)2(k2-5k+8)(2)∵原圖與該圖同構(gòu)，又，同構(gòu)的圖具有相同的色多項式，所以原圖色多項式為：k(k-1)(k-2)2(k2-5k+8)。31.證明：(1)用歸納法來證明。當m=1時，直接計算Pk(G)=km-km-1,得km-1系數(shù)為-1，且Pk(G)中具有非零系數(shù)的k的最小次數(shù)為1即G分支數(shù)，故m=1時命題成立；設對于少于m條邊的一切n階單圖命題均成立，考慮單圖G=(n,m),由遞推公式：Pk(G)=Pk(G-e)-Pk(G·e),由假設可令：Pk(G-e)=kn+a1kn-1+…+an-1kn-1,且a1=-m+1;Pk(G·e)=kn-1+b1kn-2+…+bn-2kn-2,且b1=-m+1,∴Pk(G)=kn+(a1+1)kn-1+(a1+b1)kn-2+…+bn-2kn-2,∴Pk(G)中kn-1的系數(shù)a1+1=-m；Pk(G)中具有非零系數(shù)的k的最小次數(shù)為n-2即為G的分支數(shù)。(2)一個多項式，若是某個圖的色多項式，那么也是該圖對應的底圖的色多項式。故我們僅需對單圖來證明。若Pk(G)=k4-3k3+3k2是某個單圖G的色多項式，則由(1)可知，m(G)=3，從而χ(G)≧2,另一方面，P1=1，這說明χ(G)≦1,與上面結(jié)論相矛盾，故Pk不可能是任何單圖的色多項式。32.證明：因為G1和G2中分別有一個唯一的4度頂點：u1與v1.但是它們鄰點狀況不相同：u1有4個2度鄰點，而v1只有兩個2度頂點，所以G1與G2不同構(gòu)。利用直接計算方法可得：Pk(G1)=Pk(G2)=10k3+5k4+k5.33.證明：(1)當n=1時，Pk(K1)=k,命題成立。若n<m時，命題均成立。設G是樹，且n(G)=m.可知，存在懸掛邊e∈E(G),于是G-e是孤立點加上頂點數(shù)為m-1的樹，G·e是v(G·e)=m-1的樹。由歸納法可知，Pk(G)=Pk(G-e)-Pk(G·e)=k2(k-1)m-2-k(k-1)m-2=k(k-1)m-1,故命題成立。(2)∵Pk(G-e)=Pk(G)+Pk(G·e),Pk(G·e)≧0,所以Pk(G-e)≧Pk(G),另一方面由于G連通，設T是G的生成樹，逐次用上述導出的公式將余數(shù)T的邊從G中除去，于是最后有Pk(G)≦Pk(T),由(a)，Pk(T)=k(k-1)m-1,所以，Pk(G)≦k(k-1)m-1.若連通圖G的Pk(G)=k(k-1)m-1時，則n=m-1,所以G是一棵樹。即當且僅當G是樹時等號才成立。第九章習題解：∵每條邊有2種定向方式，所以一個簡單圖共有2m(G)種定向。

2.證明：不失一般性，設G是連通圖。G中奇度頂點個數(shù)必然為偶數(shù)個，將偶數(shù)個奇度頂點配對，然后在每一對配對頂點間連一條邊得到歐拉圖G1，在G1中用Fluery算法求出G的一歐拉環(huán)游C，然后順次在C上標上方向，由此得到C的定向圖C1.在C1中，去掉添加的邊后，得到G的定向圖D，顯然：對?v∈V(D),有|d+(v)-d-(v)|≦1.7.解：強連通分支：{1}、{2,3,5,6,7}、{4}、{9}、{8}；單向連通分支：{1,2,3,4,5,6,7}、{8,9}；弱連通分支：{1,2,3,4,5,6,7,8,9