湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題11

《湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題11》由會(huì)員分享，可在線閱讀，更多相關(guān)《湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題11（7頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、習(xí) 題 十 一1設(shè)，證明任何階圖與總有一個(gè)是不可平面圖。分析： 與是兩個(gè)互補(bǔ)的圖，根據(jù)互補(bǔ)的定義，互補(bǔ)的圖有相同的頂點(diǎn)數(shù)，且G的邊數(shù)與的邊數(shù)之和等于完全圖的邊數(shù)p(p-1)/2；而由推論11.2.2，有任何簡(jiǎn)單平面圖G，其頂點(diǎn)數(shù)p和邊數(shù)q滿足：q3p-6。 證明. 若與均是可平面圖，則 （1） （2）但 （3）將（3）代入（2）有 整理后得 又由（1）有 即 也即 . 得 得此與矛盾。因此任何階圖與不可能兩個(gè)都是可平面圖，從而與總有一個(gè)是不可平面圖。2證明或否定：兩個(gè)階極大簡(jiǎn)單平面圖必同構(gòu)分析：極大平面圖是指添加任何一條邊以后不構(gòu)成平面圖的平面圖；兩個(gè)階極大簡(jiǎn)單平面圖不一定同構(gòu)。解：令，三個(gè)6

2、階極大簡(jiǎn)單平面圖如下：頂點(diǎn)上標(biāo)的數(shù)字表示該頂點(diǎn)的度，但顯然不同構(gòu).3找出一個(gè)8階簡(jiǎn)單平面，使得也是平面圖.分析：由第1題證明過程可知，當(dāng)p11時(shí)，和可以同時(shí)為平面圖。解：如下平面圖G，顯然其補(bǔ)圖也是平面圖。4證明或者否定：每個(gè)極大平面圖是圖.分析：極大平面圖是指添加任何一條邊以后不構(gòu)成平面圖的平面圖；而H圖是存在一個(gè)H回路的圖，即存在一條經(jīng)過圖中每一個(gè)頂點(diǎn)一次且僅一次的回路。由定理11.1.2知極大平面圖的每個(gè)面都是三角形，因此G中必存在回路，利用最長(zhǎng)回路的性質(zhì)使用反證法可證明每個(gè)極大平面圖都是圖。證明：設(shè)是極大平面而不是圖.顯然必連通且有回路.設(shè)是中最長(zhǎng)的回路，由假設(shè)，存在不在上且與上和構(gòu)成

3、一個(gè)三方形，于是 從而.矛盾，故是圖。5試證明：若平面圖的每個(gè)面都是三角形，則是極大平面圖。分析：極大平面圖是指添加任何一條邊以后不構(gòu)成平面圖的平面圖；利用這個(gè)定義使用反證法可證明本題。 證明：設(shè)平面圖的每個(gè)面都是，若不是極大平面圖.則中存在，使得，且仍為平面圖設(shè)是中兩個(gè)面和的公共邊界.于是，中與的面是一個(gè)面 ，顯然，由此與的每個(gè)面都是矛盾.6設(shè)是有個(gè)分支的平面圖，試證明： 分析：由歐拉公式任何簡(jiǎn)單連通平面圖均滿足,對(duì)G的k個(gè)連通利用歸納法使用該結(jié)論可證明本題。 證明：當(dāng)時(shí)，即歐拉公式，下設(shè)，有個(gè)分支. .由歐拉公式有pi-qi+ri=2;但 ，故 即 7證明：是平面圖，其中eE（K5）分析：

4、由于 的對(duì)稱性,只須考慮其中的一條邊e，驗(yàn)證是可平面圖即可.證明：任選的某條邊e，則如下圖所示，顯然這是一個(gè)平面圖。8證明：是平面圖，其中eE（K3，3）分析：仿照第7題，由于的對(duì)稱性，因此也只須考慮其中的一條邊e，驗(yàn)證是可平面圖即可.證明：任選的某條邊e，則如下圖所示，顯然是一個(gè)平面圖。9一個(gè)圖的圍長(zhǎng)是圖中最短回路之長(zhǎng)度，若圖中無回路，則圍長(zhǎng)定義為無窮大。證明：如果G(p,q,r)是連通平面圖，圍長(zhǎng)g3且有限，則 qg(p-2)/(g-2)分析：由定理11.1.1 對(duì)任何平面圖，滿足 ，又由于G是簡(jiǎn)單連通圖，因此還滿足歐拉公式。利用這兩個(gè)結(jié)論可證明本題。證明:由于G的圍長(zhǎng)為g,故d(fi)g

5、，由定理11.1.1知：可以得到將它代入Euler公式就可以得到qg(p-2)/(g-2)10利用題9證明Peterson圖是不可平面圖。分析：Petersen圖參看書上80頁的圖10.2.，由圖可知道，g=5.p=10,q=15比較q和g(p-2)/(g-2)，將會(huì)發(fā)現(xiàn)不滿足條件qg(p-2)/(g-2)，因此Peterson圖是不可平面圖。證明：Petersen圖中頂點(diǎn)數(shù)p=10，邊數(shù)q=15，圍長(zhǎng)g=5g(p-2)/(g-2)=5*（10-2）/（5-2）=40/35時(shí)，由于Kn包含一個(gè)K5的剖分，所以Kn也不是平面圖，這與G*為平面圖矛盾。 15證明：在平面上畫有限個(gè)圓所得的地圖是兩色

6、的，即有一個(gè)正常2面著色。分析：本題的證明主要用到了歐拉圖的概念和13題的結(jié)論，即圖G是歐拉圖當(dāng)且僅當(dāng)G無奇數(shù)度的頂點(diǎn)以及G是歐拉圖當(dāng)且僅當(dāng)。證明：在平面上畫有限個(gè)圓所得的地圖G顯然是一個(gè)歐拉圖，由13題結(jié)論有，即G是兩色的。16設(shè)G是平面圖，證明：若G是二分圖，則G*是歐拉圖，又若一個(gè)平面圖的對(duì)偶圖是歐拉圖，則此平面圖是二分圖。分析：該題的證明主要用到了二分圖的定義、歐拉圖的判定定理及圖G的對(duì)偶圖G*中的頂點(diǎn)的度與G中對(duì)應(yīng)面的次數(shù)的關(guān)系。即圖G是二分圖當(dāng)且僅當(dāng)G中無奇數(shù)長(zhǎng)度的回路，而圖G是歐拉圖當(dāng)且僅當(dāng)G無奇數(shù)度的頂點(diǎn)。而G*的頂點(diǎn)的度等于圖G對(duì)應(yīng)面的次數(shù)之和。證明：設(shè)G*是G的對(duì)偶圖，則G

7、*是連通的，若G是二分圖，則G中無奇數(shù)長(zhǎng)度的回路，因此G*中所有頂點(diǎn)的度數(shù)均為偶數(shù)，所以G*是歐拉圖。 若G*是歐拉圖，所以G*中每個(gè)頂點(diǎn)的度數(shù)都為偶數(shù)，所以G中無奇數(shù)長(zhǎng)度的回路，因此G為二分圖。17若一個(gè)平面圖與它的對(duì)偶圖同構(gòu)，則稱此圖是自對(duì)偶的，試證明：若G（p,q）是自對(duì)偶的，則q=2p-2分析：由對(duì)偶圖及同構(gòu)的定義有：如G（p,q,r）是一個(gè)自對(duì)偶圖，圖G*(p*,q*,r*)是它的對(duì)偶圖，則有p*=r ，q*=q，p=p*,q=q*,r=r*；又因?yàn)镚是平面圖，因此滿足歐拉公式p-q+r=2。最后可得q=2p-2。證明：設(shè)G（p,q,r）是一個(gè)自對(duì)偶圖,圖G*(p*,q*,r*)是G

8、的對(duì)偶圖。則由對(duì)偶圖的定義有：p*=r q*=q有G與G*同構(gòu)，因此有p=p*,q=q*,r=r*又G是一個(gè)平面圖，所以p-q+r=2于是有：2p-q=2 即q=2p-218畫一個(gè)非簡(jiǎn)單圖的自對(duì)偶圖。分析：一個(gè)圖G的對(duì)偶圖是按如下方式構(gòu)造出來的： 在G的每個(gè)面f內(nèi)放上一個(gè)頂點(diǎn)f*，這些頂點(diǎn)就構(gòu)成了G*的頂點(diǎn)集V(G*)，若G的兩個(gè)面f和g有一條公共邊e，則畫一條以f*和g*為端點(diǎn)的邊e*僅穿過e一次；對(duì)于G中屬于一個(gè)面的割邊e，則畫一條以f*為端點(diǎn)的環(huán)僅穿過e一次。非簡(jiǎn)單圖是有環(huán)或重邊的圖。按照第17題有自對(duì)偶圖是圖G與它的對(duì)偶圖G*同構(gòu)的圖。由這幾方面的定義，可構(gòu)造如下非簡(jiǎn)單圖的自對(duì)偶圖。 解：非簡(jiǎn)單圖的自對(duì)偶圖如下圖所示。GG*