電子科大圖論答案

1、圖論第三次作業(yè)一、第六章2.證明：根據(jù)歐拉公式的推論，有ml*(n-2)/(l-2),(1)若deg(f)4,則m4*(n-2)/2=2n-4;(2)若deg(f)5,則m5*(n-2)/3,即：3m5n-10;(3)若deg(f)6,則m6*(n-2)/4,即：2m3n-6.3.證明：G是簡單連通圖，根據(jù)歐拉公式推論，m3n-6;又，根據(jù)歐拉公式：n-m+=2,=2-n+m2-n+3n-6=2n-4.4.證明：(1)G是極大平面圖，每個面的次數(shù)為3，由次數(shù)公式：2m=3,由歐拉公式：=2-n+m,m=2-n+m,即：m=3n-6.(2)又m=n+-2,=2n-4.(3)對于的極大可平面圖的的

2、每個頂點，有，即對任一一點或者子圖，至少有三個鄰點與之相連，要使這個點或子圖與圖G不連通，必須把與之相連的點去掉，所以至少需要去掉三個點才能使，由點連通度的定義知。5.證明：假設(shè)圖G不是極大可平面圖，那么G不然至少還有兩點之間可以添加一條邊e，使G+e仍為可平面圖，由于圖G滿足，那么對圖G+e有，而平面圖的必要條件為，兩者矛盾，所以圖G是極大可平面圖。6.證明：(1)由知當n=5時，圖G為，而為不可平面圖，所以，（由和握手定理有，再由極大可平面圖的性質(zhì)，即可得）對于可平面圖有，而，所以至少有6個點的度數(shù)不超過5.(2)由和握手定理有，再由極大可平面圖的性質(zhì)，即可得，對于可平面圖有，而，所以至少

3、有12個點的度數(shù)不超過5.二、第七章2.證明：設(shè)n=2k+1,G是正則單圖，且>0,m(G)=>k,由定理5可知(G)=(G)+1.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)用歸納法來

4、證明。當m=1時，直接計算Pk(G)=km-km-1,得km-1系數(shù)為-1，且Pk(G)中具有非零系數(shù)的k的最小次數(shù)為1即G分支數(shù)，故m=1時命題成立；設(shè)對于少于m條邊的一切n階單圖命題均成立，考慮單圖G=(n,m),由遞推公式：Pk(G)=Pk(G-e)-Pk(G·e),由假設(shè)可令：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)中具有非零系

5、數(shù)的k的最小次數(shù)為n-2即為G的分支數(shù)。(2)一個多項式，若是某個圖的色多項式，那么也是該圖對應(yīng)的底圖的色多項式。故我們僅需對單圖來證明。若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)

6、=k,命題成立。若n<m時，命題均成立。設(shè)G是樹，且n(G)=m.可知，存在懸掛邊eE(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連通，設(shè)T是G的生成樹，逐次用上述導(dǎo)出的公式將余數(shù)T的邊從G中除去，于是最后有Pk(G)Pk(T),由(a)，Pk(T)=k(k-

7、1)m-1,所以，Pk(G)k(k-1)m-1.若連通圖G的Pk(G)=k(k-1)m-1時，則n=m-1,所以G是一棵樹。即當且僅當G是樹時等號才成立。三、第九章1. 解：每條邊有2種定向方式，所以一個簡單圖共有2m(G)種定向。2.證明：不失一般性，設(shè)G是連通圖。G中奇度頂點個數(shù)必然為偶數(shù)個，將偶數(shù)個奇度頂點配對，然后在每一對配對頂點間連一條邊得到歐拉圖G1，在G1中用Fluery算法求出G的一歐拉環(huán)游C，然后順次在C上標上方向，由此得到C的定向圖C1.在C1中，去掉添加的邊后，得到G的定向圖D，顯然：對vV(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。11.證明：設(shè)該樹有i個分支點，由定理：(m-1