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

1、習(xí) 題 十 一 1．設(shè)，證明任何階圖與總有一個是不可平面圖。 分析： 與是兩個互補的圖，根據(jù)互補的定義，互補的圖有相同的頂點數(shù)，且G的邊數(shù)與的邊數(shù)之和等于完全圖的邊數(shù)p(p-1)/2；而由推論11.2.2，有任何簡單平面圖G，其頂點數(shù)p和邊數(shù)q滿足：q≤3p-6。 證明. 若與均是可平面圖，則 （1） （2） 但 （3） 將（3）代

2、入（2）有 整理后得 又由（1）有 即 也即 . 得 得 此與矛盾。 因此任何階圖與不可能兩個都是可平面圖，從而與總有一個是不可平面圖。 2．證明或否定：兩個階極大簡單平面圖必同構(gòu) 分析：極大平面圖是指添加任何一條邊以后不構(gòu)成平面圖的平面圖；兩個階極大簡單平面圖不一定同構(gòu)。 解：令，三個6階極大簡單平面圖如下： 頂點上標的數(shù)字表示該頂點的度，但顯然不同構(gòu). 3．找出一個8階簡單平面，使得也是平面圖.

3、 分析：由第1題證明過程可知，當p<11時，和可以同時為平面圖。 解：如下平面圖G，顯然其補圖也是平面圖。 4．證明或者否定：每個極大平面圖是圖. 分析：極大平面圖是指添加任何一條邊以后不構(gòu)成平面圖的平面圖；而H圖是存在一個H回路的圖，即存在一條經(jīng)過圖中每一個頂點一次且僅一次的回路。由定理11.1.2知極大平面圖的每個面都是三角形，因此G中必存在回路，利用最長回路的性質(zhì)使用反證法可證明每個極大平面圖都是圖。 證明：設(shè)是極大平面而不是圖.顯然必連通且有回路. 設(shè)是中最長的回路，由假設(shè)， 存在不在上且與上和構(gòu) 成一個三方形，于是 從而.矛盾，故是圖。

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

5、 7．證明：是平面圖，其中e∈E（K5） 分析：由于 的對稱性,只須考慮其中的一條邊e，驗證是可平面圖即可. 證明：任選的某條邊e，則如下圖所示，顯然這是一個平面圖。 8．證明：是平面圖，其中e∈E（K3，3） 分析：仿照第7題，由于的對稱性，因此也只須考慮其中的一條邊e，驗證是可平面圖即可. 證明：任選的某條邊e，則如下圖所示，顯然是一個平面圖。 9．一個圖的圍長是圖中最短回路之長度，若圖中無回路，則圍長定義為無窮大。證明：如果G(p,q,r)是連通平面圖，圍長g≥3且有限，則

6、 q≤g(p-2)/(g-2) 分析：由定理11.1.1 對任何平面圖，滿足 ，又由于G是簡單連通圖，因此還滿足歐拉公式。利用這兩個結(jié)論可證明本題。 證明:由于G的圍長為g,故d(fi)≥g，由定理11.1.1知： 可以得到 將它代入Euler公式就可以得到q≤g(p-2)/(g-2) 10．利用題9證明Peterson圖是不可平面圖。 分析：Petersen圖參看書上80頁的圖10.2.，由圖可知道，g=5.p=10,q=15比較q和g(p-2)/(g-2)， 將會發(fā)現(xiàn)不滿足條件q≥g(p-2)/(g-2)，因此Peterson圖是不可

7、平面圖。 證明： Petersen圖中頂點數(shù)p=10，邊數(shù)q=15，圍長g=5 g(p-2)/(g-2)=5*（10-2）/（5-2）=40/3<15=q 不滿足9題的結(jié)論,所以Peterson圖是不可平面圖. 11．圖11-11是可平面圖嗎？若是，則請給出平面嵌入，否則說明它是一個包含K5或K3，3的剖分圖。 (a） (b） (c） (d） 圖11-11 分析：存在一個平面嵌入的圖是可平面圖，因此利用這個定義如果能找到G的一個平面嵌入，則可以判斷這個圖是可平面圖。再由定理11.3.1一個圖是可平面圖的充分必要條件是該圖不包含一個K5或K3，3的剖分圖，利用這個定

8、理如果能找到一個圖的K5或K3，3的剖分圖，則該圖不是可平面圖。 解：這四個圖均是平面圖，其平面嵌入分別如下所示： (a） (b） (c） (d） 圖11-11 12．平面M上有n條直線將平面M分成若干區(qū)域，為了使相互鄰接的區(qū)域著不同的顏色，最少需要幾種顏色？ 分析：先將r個區(qū)域編成號（如圖12-1所示）。 將直線的交點看做圖的頂點，所有無限區(qū)域的兩條無限邊都交于一頂點v（等價于所有直線的兩端均在無窮遠點相交），所得圖的示意圖為圖12-2所示。顯然12-2所示的面數(shù)與12-1的區(qū)域數(shù)相同，并且12-1中所示圖是區(qū)域2-可著色的，當且僅當12-2中所示的圖是面2-可著色

9、的。可是12-2是無環(huán)的E平面圖，利用13題結(jié)論可知12-2是面2-可著色的，從而12-1所示的圖是區(qū)域2-可著色的。 解：最少需要兩種顏色。 7 5 3 1 2 4 6 7 5 3 1 2 4 6 圖12-1 圖12-2 13．設(shè)G是一個連通的平面地圖，證明當且僅當G是歐拉圖。 分析：本題的證明利用了圖G和其對偶圖G*的關(guān)系以及第16題的結(jié)論：G是二分圖當且僅當G*是歐拉圖。 又G是點2-可著色的當且僅當G是二分圖。因為若G是點2-可著色的，則G中的所有頂點可按著的顏色劃分為兩個集合，顯然著相同顏色的頂點互不鄰接，因此這兩個集合中的

10、任意兩個頂點不鄰接，因此G是二分圖；反過來，如G是二分圖，則G中的所有頂點可劃分為兩個集合，且每個集合中任意兩個頂點不鄰接，因此按G的這兩個集合將G中所有頂點著兩種不同的顏色，是G的正常2著色，因此。 證明：設(shè)G是一連通的平面地圖，則G是一無割邊的連通平面圖，設(shè)G*是G的對偶圖，則G*是無環(huán)的連通的平面圖，因此G是面2-可著色的當且僅當G*是點2-可著色的，而G*是點2-可著色的當且僅當G*是二分圖，由題16結(jié)論有G*是二分圖當且僅當G是歐拉圖。 14．將平面分成r個區(qū)域，使任意兩個區(qū)域都相鄰，問r最大為多少？ 分析：顯然當r=1，2，3，4時，可以構(gòu)造出滿足條件的圖，如下圖是當r

11、=4時滿足條件的平面圖 f2 f1 f0 f3 因此如果能證明不存在具有5個或5個以上面的平面圖，其每兩個面都共享一條邊。則滿足條件的r最大為4。 解：r最大為4。 證明：假設(shè)存在這樣的平面G，設(shè)G的對偶圖為G*，則G*也是平面圖。由于G至少有5個面，所有G*至少具有5個頂點。設(shè)v*為G*的任一頂點，設(shè)它位于G的面R中，由于R與其余至少4個面均有公共邊，所有v*與其余面中的頂點均相鄰，于是d(v*)≥4，而且G*為簡單圖，于是G*必為Kn(n≥5)，當n=5時，顯然K5為非平面圖，當n>5時，由于Kn包含一個K5的剖分，所以Kn也不是平面圖，這與G*為平面圖矛盾。

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

13、而G*的頂點的度等于圖G對應(yīng)面的次數(shù)之和。 證明：設(shè)G*是G的對偶圖，則G*是連通的，若G是二分圖，則G中無奇數(shù)長度的回路，因此G*中所有頂點的度數(shù)均為偶數(shù)，所以G*是歐拉圖。 若G*是歐拉圖，所以G*中每個頂點的度數(shù)都為偶數(shù)，所以G中無奇數(shù)長度的回路，因此G為二分圖。 17．若一個平面圖與它的對偶圖同構(gòu)，則稱此圖是自對偶的，試證明：若G（p,q）是自對偶的，則q=2p-2 分析：由對偶圖及同構(gòu)的定義有：如G（p,q,r）是一個自對偶圖，圖G*(p*,q*,r*)是它的對偶圖，則有p*=r ，q*=q，p=p*,q=q*,r=r*；又因為G是平面圖，因此滿足歐拉公式p-

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