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

上傳人:沈*** 文檔編號(hào):140872380 上傳時(shí)間:2022-08-23 格式:DOC 頁數(shù):7 大?。?62.50KB
收藏 版權(quán)申訴 舉報(bào) 下載
湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題11_第1頁
第1頁 / 共7頁
湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題11_第2頁
第2頁 / 共7頁
湘潭大學(xué) 劉任任版 離散數(shù)學(xué)課后習(xí)題答案 習(xí)題11_第3頁
第3頁 / 共7頁

下載文檔到電腦,查找使用更方便

10 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《湘潭大學(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*

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!