版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
圖論—平面圖離散數(shù)學(xué)圖論—平面圖離散數(shù)學(xué)1平面圖如果能把一個(gè)圖在平面上畫成除端點(diǎn)外,任何兩邊都不相交,則稱此圖為可平面的,或稱平面圖。平面圖如果能把一個(gè)圖在平面上畫成除端點(diǎn)外,任何兩邊都不相交,2平面圖示例平面圖示例3平面圖示例平面圖示例4非平面圖示例非平面圖示例5非平面圖示例非平面圖示例6區(qū)域平面圖的邊把平面圖劃分成的塊例如平面圖將平面劃分成4個(gè)區(qū)域R1、R2、R3是有限區(qū)域R4是無(wú)限區(qū)域R1R2R3R4區(qū)域平面圖的邊把平面圖劃分成的塊R1R2R3R47歐拉公式設(shè)圖G是無(wú)向連通平面圖,它具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域,則
n-m+r=2歐拉公式設(shè)圖G是無(wú)向連通平面圖,8歐拉公式證明用歸納法,對(duì)邊數(shù)進(jìn)行歸納。當(dāng)圖中僅有一條邊時(shí),有兩種結(jié)構(gòu),一是有兩個(gè)鄰接點(diǎn)和一條關(guān)聯(lián)這兩頂點(diǎn)的邊,易知n=2,m=1,r=1(僅有一個(gè)無(wú)限區(qū)域),所以歐拉公式n-m+r=2成立;另一種是由一條自由回路構(gòu)成的圖,這時(shí)n=1,m=1,r=2,所以歐拉公式成立。歐拉公式證明用歸納法,對(duì)邊數(shù)進(jìn)行歸納。9歐拉公式證明(續(xù))設(shè)當(dāng)連通平面圖具有m條邊時(shí),歐拉公式成立。一個(gè)具有m+1條邊的連通平面圖,刪去一條邊后,仍然是平面圖。把具有m+1條邊的連通平面圖看作是由含m條邊的連通平面圖添加一條邊后構(gòu)成的。歐拉公式證明(續(xù))設(shè)當(dāng)連通平面圖具有m條邊時(shí),歐拉公式成立。10歐拉公式證明(續(xù))可能有三種不同的結(jié)構(gòu)。歐拉公式證明(續(xù))可能有三種不同的結(jié)構(gòu)。11歐拉公式證明(續(xù))把具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域的連通平面圖記作G(n,m,r)。在G(n,m,r)中原有的兩點(diǎn)中添加一條邊,增加一個(gè)區(qū)域構(gòu)成圖G(n,m+1,r+1),歐拉公式成立歐拉公式證明(續(xù))把具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域的連通平面12歐拉公式證明(續(xù))把具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域的連通平面圖記作G(n,m,r)。在G(n,m,r)中原有的兩點(diǎn)中添加一條邊,增加一個(gè)區(qū)域構(gòu)成圖G(n,m+1,r+1),歐拉公式成立歐拉公式證明(續(xù))把具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域的連通平面13歐拉公式證明(續(xù))把具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域的連通平面圖記作G(n,m,r)。在G(n,m,r)中添加一條邊后,增加了一個(gè)頂點(diǎn)但沒(méi)增加區(qū)域數(shù)構(gòu)成圖G(n+1,m+1,r),歐拉公式仍然成立證畢。歐拉公式證明(續(xù))把具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域的連通平面14歐拉公式推論設(shè)圖G是具有n(≥3)個(gè)頂點(diǎn)、m條邊的無(wú)向連通平面圖,則 3n-6≥m歐拉公式推論設(shè)圖G是具有n(≥3)個(gè)頂點(diǎn)、m條邊的無(wú)向連通平15推論證明由于G是簡(jiǎn)單圖,因此G中每一個(gè)區(qū)域至少由3條邊圍成,若G中有r個(gè)區(qū)域,圍成r個(gè)區(qū)域總邊數(shù)為2m(因?yàn)槊織l邊都作為兩個(gè)相鄰區(qū)域的公共邊,被計(jì)算了兩次)。所以有 2m≥3r或r≤2m/3代入歐拉公式后得n-m+2m/3≥2從而得到3n-6≥m推論證明由于G是簡(jiǎn)單圖,因此G中每一個(gè)區(qū)域至少由3條邊圍成,16示例1證明K3,3是非平面圖證明由于K3,3是完全二部圖,因此每條回路由偶數(shù)條邊組成,而K3,3又是簡(jiǎn)單圖,所以如果K3,3是平面圖,其每一個(gè)區(qū)域至少由4條邊圍成,于是有2m≥4r或r≤m/2。代入歐拉公式后可得2n-4≥m。K3,3中,n=6,m=9,不滿足上述不等式,所以K3,3不是平面圖。示例1證明K3,3是非平面圖17證明證明具有5個(gè)頂點(diǎn)的無(wú)向完全圖K5是非平面圖證明因?yàn)樵贙5中頂點(diǎn)數(shù)n=5,邊數(shù)m=10,3n–6=9<m,不滿足平面圖的必要條件,所以K5是非平面圖。證明證明具有5個(gè)頂點(diǎn)的無(wú)向完全圖K5是非平面圖18平面圖例1設(shè)G是至少有11個(gè)頂點(diǎn)的無(wú)向簡(jiǎn)單連通平面圖,證明G的補(bǔ)圖~G一定是非平面圖。證明設(shè)圖G有n個(gè)頂點(diǎn)(n≥11),m條邊,顯然其補(bǔ)圖~G有n個(gè)頂點(diǎn)、(n-1)n/2-m條邊。用反證法,設(shè)補(bǔ)圖~G也是平面圖,則有 3n–6≥(n-1)n/2-m圖G是連通簡(jiǎn)單平面圖,所以有 3n–6≥m平面圖例1設(shè)G是至少有11個(gè)頂點(diǎn)的無(wú)向簡(jiǎn)單連通平面圖,證明G19證明(續(xù))由此可得 6n-12≥(n-1)n/2
整理后得 n2-13n+24≤0或 n2-13n+22≤0 (n
-11)(n
-2)<0由此可得n<11,這和假設(shè)n≥11矛盾,證畢。證明(續(xù))由此可得20二度同構(gòu)如果兩個(gè)圖是由同一個(gè)圖的邊上插入一些新的頂點(diǎn)(它一定是2度點(diǎn))而得到的,則稱這兩個(gè)圖是二度同構(gòu)的。二度同構(gòu)如果兩個(gè)圖是由同一個(gè)圖的邊上插入一些新的頂點(diǎn)(它一定21二度同構(gòu)二度同構(gòu)22庫(kù)拉托夫斯基定理一個(gè)圖是平面圖的充分必要條件是該圖不包含二度同構(gòu)于K5或K3,3的子圖。庫(kù)拉托夫斯基定理一個(gè)圖是平面圖的充分必要條件是23非平面圖證明例2證明所示圖是非平面圖。證明把圖中的邊ED刪去后,所得的子圖就是K3,3,所以此圖是非平面圖。ABCDEFABCDEF非平面圖證明例2證明所示圖是非平面圖。ABCDEFABCDE24非平面圖證明例3證明彼得遜圖是非平面圖。DCIABFHEGJ非平面圖證明例3證明彼得遜圖是非平面圖。DCIABFHEG25非平
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年臨時(shí)搬運(yùn)合同
- 2024年度某新能源汽車制造技術(shù)許可合同
- 2024年度文化娛樂(lè)活動(dòng)策劃合同
- 2024年廣播劇配音委托合同
- 2024年建筑工程地面建設(shè)合同
- 企業(yè)普通員工年終個(gè)人工作總結(jié)
- 2024年度風(fēng)力發(fā)電設(shè)備安裝合同
- 節(jié)能宣傳課件教學(xué)課件
- 2024醫(yī)療機(jī)構(gòu)人力資源共享與培訓(xùn)合同
- 2024年度碎石料供需合同
- 護(hù)士與醫(yī)生的合作與溝通
- GB 42295-2022電動(dòng)自行車電氣安全要求
- 產(chǎn)品系統(tǒng)設(shè)計(jì)開(kāi)發(fā) 課件 第4、5章 產(chǎn)品系統(tǒng)設(shè)計(jì)類型、產(chǎn)品系統(tǒng)設(shè)計(jì)開(kāi)發(fā)綜合案例
- 1編譯原理及實(shí)現(xiàn)課后題及答案
- 焊接材料的質(zhì)量控制和追溯規(guī)范
- 讓閱讀成為習(xí)慣家長(zhǎng)會(huì)課件
- 家庭健康照護(hù)服務(wù)方案
- 施工方案 誰(shuí)編
- 滬教牛津版八上英語(yǔ)Unit-6-單元完整課件
- 新能源及多能互補(bǔ)互補(bǔ)技術(shù)
- 混凝土攪拌站安裝及拆除方案
評(píng)論
0/150
提交評(píng)論