歐拉公式證明課件_第1頁(yè)
歐拉公式證明課件_第2頁(yè)
歐拉公式證明課件_第3頁(yè)
歐拉公式證明課件_第4頁(yè)
歐拉公式證明課件_第5頁(yè)
已閱讀5頁(yè),還剩21頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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ì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論