電子科大圖論答案

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是簡(jiǎn)單連通圖，根據(jù)歐拉公式推論，m3n-6;又，根據(jù)歐拉公式：n-m+=2,=2-n+m2-n+3n-6=2n-4.4.證明：(1)G是極大平面圖，每個(gè)面的次數(shù)為3，由次數(shù)公式：2m=3,由歐拉公式：=2-n+m,m=2-n+m,即：m=3n-6.(2)又m=n+-2,=2n-4.(3)對(duì)于的極大可平面圖的的

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

3、有12個(gè)點(diǎn)的度數(shù)不超過(guò)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),所以，原圖色多項(xiàng)式為：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)的圖具有相同的色多項(xiàng)式，所以原圖色多項(xiàng)式為：k(k-1)(k-2)2(k2-5k+8)。31.證明：(1)用歸納法來(lái)

4、證明。當(dāng)m=1時(shí)，直接計(jì)算Pk(G)=km-km-1,得km-1系數(shù)為-1，且Pk(G)中具有非零系數(shù)的k的最小次數(shù)為1即G分支數(shù)，故m=1時(shí)命題成立；設(shè)對(duì)于少于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)一個(gè)多項(xiàng)式，若是某個(gè)圖的色多項(xiàng)式，那么也是該圖對(duì)應(yīng)的底圖的色多項(xiàng)式。故我們僅需對(duì)單圖來(lái)證明。若Pk(G)=k4-3k3+3k2是某個(gè)單圖G的色多項(xiàng)式，則由(1)可知，m(G)=3，從而(G)2,另一方面，P1=1，這說(shuō)明(G)1,與上面結(jié)論相矛盾，故Pk不可能是任何單圖的色多項(xiàng)式。32.證明：因?yàn)镚1和G2中分別有一個(gè)唯一的4度頂點(diǎn)：u1與v1.但是它們鄰點(diǎn)狀況不相同：u1有4個(gè)2度鄰點(diǎn)，而v1只有兩個(gè)2度頂點(diǎn)，所以G1與G2不同構(gòu)。利用直接計(jì)算方法可得：Pk(G1)=Pk(G2)=10k3+5k4+k5.33.證明：(1)當(dāng)n=1時(shí)，Pk(K1)

6、=k,命題成立。若n<m時(shí)，命題均成立。設(shè)G是樹(shù)，且n(G)=m.可知，存在懸掛邊eE(G),于是G-e是孤立點(diǎn)加上頂點(diǎn)數(shù)為m-1的樹(shù)，G·e是v(G·e)=m-1的樹(shù)。由歸納法可知，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的生成樹(shù)，逐次用上述導(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時(shí)，則n=m-1,所以G是一棵樹(shù)。即當(dāng)且僅當(dāng)G是樹(shù)時(shí)等號(hào)才成立。三、第九章1. 解：每條邊有2種定向方式，所以一個(gè)簡(jiǎn)單圖共有2m(G)種定向。2.證明：不失一般性，設(shè)G是連通圖。G中奇度頂點(diǎn)個(gè)數(shù)必然為偶數(shù)個(gè)，將偶數(shù)個(gè)奇度頂點(diǎn)配對(duì)，然后在每一對(duì)配對(duì)頂點(diǎn)間連一條邊得到歐拉圖G1，在G1中用Fluery算法求出G的一歐拉環(huán)游C，然后順次在C上標(biāo)上方向，由此得到C的定向圖C1.在C1中，去掉添加的邊后，得到G的定向圖D，顯然：對(duì)vV(D),有|d+(v)-d-(v)|1.7.解：強(qiáng)連通分支：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è)該樹(shù)有i個(gè)分支點(diǎn)，由定理：(m-1