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

習(xí) 題 十 一1設(shè)，證明任何階圖與總有一個(gè)是不可平面圖。分析： 與是兩個(gè)互補(bǔ)的圖，根據(jù)互補(bǔ)的定義，互補(bǔ)的圖有相同的頂點(diǎn)數(shù)，且G的邊數(shù)與的邊數(shù)之和等于完全圖的邊數(shù)p(p-1)/2；而由推論11.2.2，有任何簡單平面圖G，其頂點(diǎn)數(shù)p和邊數(shù)q滿足：q3p-6。 證明. 若與均是可平面圖，則 （1） （2）但 （3）將（3）代入（2）有 整理后得 又由（1）有 即 也即 . 得 得此與矛盾。因此任何階圖與不可能兩個(gè)都是可平面圖，從而與總有一個(gè)是不可平面圖。2證明或否定：兩個(gè)階極大簡單平面圖必同構(gòu)分析：極大平面圖是指添加任何一條邊以后不構(gòu)成平面圖的平面圖；兩個(gè)階極大簡單平面圖不一定同構(gòu)。解：令，三個(gè)6階極大簡單平面圖如下：頂點(diǎn)上標(biāo)的數(shù)字表示該頂點(diǎn)的度，但顯然不同構(gòu).3找出一個(gè)8階簡單平面，使得也是平面圖.分析：由第1題證明過程可知，當(dāng)p<11時(shí)，和可以同時(shí)為平面圖。解：如下平面圖G，顯然其補(bǔ)圖也是平面圖。4證明或者否定：每個(gè)極大平面圖是圖.分析：極大平面圖是指添加任何一條邊以后不構(gòu)成平面圖的平面圖；而H圖是存在一個(gè)H回路的圖，即存在一條經(jīng)過圖中每一個(gè)頂點(diǎn)一次且僅一次的回路。由定理11.1.2知極大平面圖的每個(gè)面都是三角形，因此G中必存在回路，利用最長回路的性質(zhì)使用反證法可證明每個(gè)極大平面圖都是圖。證明：設(shè)是極大平面而不是圖.顯然必連通且有回路.設(shè)是中最長的回路，由假設(shè)，存在不在上且與上和構(gòu)成一個(gè)三方形，于是 從而.矛盾，故是圖。5試證明：若平面圖的每個(gè)面都是三角形，則是極大平面圖。分析：極大平面圖是指添加任何一條邊以后不構(gòu)成平面圖的平面圖；利用這個(gè)定義使用反證法可證明本題。 證明：設(shè)平面圖的每個(gè)面都是，若不是極大平面圖.則中存在，使得，且仍為平面圖設(shè)是中兩個(gè)面和的公共邊界.于是，中與的面是一個(gè)面 ，顯然，由此與的每個(gè)面都是矛盾.6設(shè)是有個(gè)分支的平面圖，試證明： 分析：由歐拉公式任何簡單連通平面圖均滿足,對(duì)G的k個(gè)連通利用歸納法使用該結(jié)論可證明本題。 證明：當(dāng)時(shí)，即歐拉公式，下設(shè)，有個(gè)分支. .由歐拉公式有pi-qi+ri=2;但 ，故 即 7證明：是平面圖，其中eE（K5）分析：由于 的對(duì)稱性,只須考慮其中的一條邊e，驗(yàn)證是可平面圖即可.證明：任選的某條邊e，則如下圖所示，顯然這是一個(gè)平面圖。8證明：是平面圖，其中eE（K3，3）分析：仿照第7題，由于的對(duì)稱性，因此也只須考慮其中的一條邊e，驗(yàn)證是可平面圖即可.證明：任選的某條邊e，則如下圖所示，顯然是一個(gè)平面圖。9一個(gè)圖的圍長是圖中最短回路之長度，若圖中無回路，則圍長定義為無窮大。證明：如果G(p,q,r)是連通平面圖，圍長g3且有限，則 qg(p-2)/(g-2)分析：由定理11.1.1 對(duì)任何平面圖，滿足 ，又由于G是簡單連通圖，因此還滿足歐拉公式。利用這兩個(gè)結(jié)論可證明本題。證明:由于G的圍長為g,故d(fi)g，由定理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，圍長g=5g(p-2)/(g-2)=5*（10-2）/（5-2）=40/3<15=q不滿足9題的結(jié)論,所以Peterson圖是不可平面圖.11圖11-11是可平面圖嗎？若是，則請(qǐng)給出平面嵌入，否則說明它是一個(gè)包含K5或K3，3的剖分圖。(a）(b）(c）(d）圖11-11分析：存在一個(gè)平面嵌入的圖是可平面圖，因此利用這個(gè)定義如果能找到G的一個(gè)平面嵌入，則可以判斷這個(gè)圖是可平面圖。再由定理11.3.1一個(gè)圖是可平面圖的充分必要條件是該圖不包含一個(gè)K5或K3，3的剖分圖，利用這個(gè)定理如果能找到一個(gè)圖的K5或K3，3的剖分圖，則該圖不是可平面圖。解：這四個(gè)圖均是平面圖，其平面嵌入分別如下所示：(a）(b）(c）(d）圖11-1112平面M上有n條直線將平面M分成若干區(qū)域，為了使相互鄰接的區(qū)域著不同的顏色，最少需要幾種顏色？分析：先將r個(gè)區(qū)域編成號(hào)（如圖12-1所示）。將直線的交點(diǎn)看做圖的頂點(diǎn)，所有無限區(qū)域的兩條無限邊都交于一頂點(diǎn)v（等價(jià)于所有直線的兩端均在無窮遠(yuǎn)點(diǎn)相交），所得圖的示意圖為圖12-2所示。顯然12-2所示的面數(shù)與12-1的區(qū)域數(shù)相同，并且12-1中所示圖是區(qū)域2-可著色的，當(dāng)且僅當(dāng)12-2中所示的圖是面2-可著色的?？墒?2-2是無環(huán)的E平面圖，利用13題結(jié)論可知12-2是面2-可著色的，從而12-1所示的圖是區(qū)域2-可著色的。解：最少需要兩種顏色。75312467531246圖12-1圖12-213設(shè)G是一個(gè)連通的平面地圖，證明當(dāng)且僅當(dāng)G是歐拉圖。分析：本題的證明利用了圖G和其對(duì)偶圖G*的關(guān)系以及第16題的結(jié)論：G是二分圖當(dāng)且僅當(dāng)G*是歐拉圖。 又G是點(diǎn)2-可著色的當(dāng)且僅當(dāng)G是二分圖。因?yàn)槿鬐是點(diǎn)2-可著色的，則G中的所有頂點(diǎn)可按著的顏色劃分為兩個(gè)集合，顯然著相同顏色的頂點(diǎn)互不鄰接，因此這兩個(gè)集合中的任意兩個(gè)頂點(diǎn)不鄰接，因此G是二分圖；反過來，如G是二分圖，則G中的所有頂點(diǎn)可劃分為兩個(gè)集合，且每個(gè)集合中任意兩個(gè)頂點(diǎn)不鄰接，因此按G的這兩個(gè)集合將G中所有頂點(diǎn)著兩種不同的顏色，是G的正常2著色，因此。證明：設(shè)G是一連通的平面地圖，則G是一無割邊的連通平面圖，設(shè)G*是G的對(duì)偶圖，則G*是無環(huán)的連通的平面圖，因此G是面2-可著色的當(dāng)且僅當(dāng)G*是點(diǎn)2-可著色的，而G*是點(diǎn)2-可著色的當(dāng)且僅當(dāng)G*是二分圖，由題16結(jié)論有G*是二分圖當(dāng)且僅當(dāng)G是歐拉圖。14將平面分成r個(gè)區(qū)域，使任意兩個(gè)區(qū)域都相鄰，問r最大為多少？ 分析：顯然當(dāng)r=1，2，3，4時(shí)，可以構(gòu)造出滿足條件的圖，如下圖是當(dāng)r=4時(shí)滿足條件的平面圖f2f1f0f3因此如果能證明不存在具有5個(gè)或5個(gè)以上面的平面圖，其每兩個(gè)面都共享一條邊。則滿足條件的r最大為4。解：r最大為4。證明：假設(shè)存在這樣的平面G，設(shè)G的對(duì)偶圖為G*，則G*也是平面圖。由于G至少有5個(gè)面，所有G*至少具有5個(gè)頂點(diǎn)。設(shè)v*為G*的任一頂點(diǎn)，設(shè)它位于G的面R中，由于R與其余至少4個(gè)面均有公共邊，所有v*與其余面中的頂點(diǎn)均相鄰，于是d(v*)4，而且G*為簡單圖，于是G*必為Kn(n5)，當(dāng)n=5時(shí)，顯然K5為非平面圖，當(dāng)n>5時(shí)，由于Kn包含一個(gè)K5的剖分，所以Kn也不是平面圖，這與G*為平面圖矛盾。 15證明：在平面上畫有限個(gè)圓所得的地圖是兩色的，即有一個(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ù)長度的回路，而圖G是歐拉圖當(dāng)且僅當(dāng)G無奇數(shù)度的頂點(diǎn)。而G*的頂點(diǎn)的度等于圖G對(duì)應(yīng)面的次數(shù)之和。證明：設(shè)G*是G的對(duì)偶圖，則G*是連通的，若G是二分圖，則G中無奇數(shù)長度的回路，因此G*中所有頂點(diǎn)的度數(shù)均為偶數(shù)，所以G*是歐拉圖。 若G*是歐拉圖，所以G*中每個(gè)頂點(diǎn)的度數(shù)都為偶數(shù)，所以G中無奇數(shù)長度的回路，因此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的對(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è)非簡單圖的自對(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一次。非簡單圖是有環(huán)或重邊的圖。按照第17題有自對(duì)偶圖是圖G與它的對(duì)偶圖G*同構(gòu)的圖。由這幾方面的定義，可構(gòu)造如下非簡單圖的自對(duì)偶圖。 解：非簡單圖的自對(duì)偶圖如下圖所示。GG*