2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩25頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、圖論—平面圖,離散數(shù)學(xué),平面圖,如果能把一個(gè)圖在平面上畫成除端點(diǎn)外,任何兩邊都不相交,則稱此圖為可平面的,或稱平面圖。,平面圖示例,平面圖示例,非平面圖示例,非平面圖示例,區(qū)域,平面圖的邊把平面圖劃分成的塊例如平面圖將平面劃分成4個(gè)區(qū)域R1、R2、R3是有限區(qū)域R4是無限區(qū)域,歐拉公式,設(shè)圖G是無向連通平面圖,它具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域,則 n - m + r = 2,歐拉公式證明,用歸納法,對(duì)邊數(shù)進(jìn)行歸納

2、。當(dāng)圖中僅有一條邊時(shí),有兩種結(jié)構(gòu), 一是有兩個(gè)鄰接點(diǎn)和一條關(guān)聯(lián)這兩頂點(diǎn)的邊, 易知n=2,m=1,r=1(僅有一個(gè)無限區(qū)域),所以歐拉公式n-m+r=2成立; 另一種是由一條自由回路構(gòu)成的圖,這時(shí)n=1,m=1,r=2,所以歐拉公式成立。,歐拉公式證明(續(xù)),設(shè)當(dāng)連通平面圖具有m條邊時(shí),歐拉公式成立。一個(gè)具有m+1條邊的連通平面圖,刪去一條邊后,仍然是平面圖。把具有m+1條邊的連通平面圖看作是由含m條邊的連通平面圖添加

3、一條邊后構(gòu)成的。,歐拉公式證明(續(xù)),可能有三種不同的結(jié)構(gòu)。,歐拉公式證明(續(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ū)域的連通平面圖記作G(n,m,r)。在G(n,m,r)中原有的兩點(diǎn)中添加一條邊,增加一個(gè)區(qū)域構(gòu)成圖G(n,m+1,r+1),歐拉公式

4、成立,歐拉公式證明(續(xù)),把具有n個(gè)頂點(diǎn),m條邊和r個(gè)區(qū)域的連通平面圖記作G(n,m,r)。在G(n,m,r)中添加一條邊后,增加了一個(gè)頂點(diǎn)但沒增加區(qū)域數(shù)構(gòu)成圖G(n+1,m+1,r),歐拉公式仍然成立證畢。,歐拉公式推論,設(shè)圖G是具有n(≥3)個(gè)頂點(diǎn)、m條邊的無向連通平面圖,則3n- 6≥m,推論證明,由于G是簡(jiǎn)單圖,因此G中每一個(gè)區(qū)域至少由3條邊圍成,若G中有r個(gè)區(qū)域,圍成r個(gè)區(qū)域總邊數(shù)為2m(因?yàn)槊織l邊都作為兩個(gè)

5、相鄰區(qū)域的公共邊,被計(jì)算了兩次)。所以有2m≥3r 或 r ≤ 2m/3代入歐拉公式后得    n - m+ 2m/3 ≥ 2 從而得到 3n-6≥m,示例1,證明K3,3是非平面圖證明 由于K3,3是完全二部圖,因此每條回路由偶數(shù)條邊組成, 而K3,3又是簡(jiǎn)單圖,所以如果K3,3是平面圖,其每一個(gè)區(qū)域至少由4條邊圍成, 于是有 2m≥4r 或 r≤m/2 。 代入歐拉公式后可得 2n-4≥m。

6、 K3,3中,n=6,m=9,不滿足上述不等式, 所以K3,3不是平面圖。,證明,證明具有5個(gè)頂點(diǎn)的無向完全圖K5是非平面圖 證明 因?yàn)樵贙5中頂點(diǎn)數(shù)n=5,邊數(shù)m=10,3n – 6 = 9<m,不滿足平面圖的必要條件,所以K5是非平面圖。,平面圖例1,設(shè)G是至少有11個(gè)頂點(diǎn)的無向簡(jiǎn)單連通平面圖,證明G的補(bǔ)圖~G一定是非平面圖。證明 設(shè)圖G有n個(gè)頂點(diǎn)(n≥11),m條邊,顯然其補(bǔ)圖~G 有n個(gè)頂點(diǎn)、(n-1)n/2

7、-m條邊。 用反證法,設(shè)補(bǔ)圖~G也是平面圖, 則有3n – 6 ≥ (n-1)n/2-m 圖G是連通簡(jiǎn)單平面圖,所以有3n – 6 ≥ m,證明(續(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矛盾,證畢。,二度同構(gòu),如果兩個(gè)圖是由同一個(gè)圖的邊

8、上插入一些新的頂點(diǎn)(它一定是2度點(diǎn))而得到的,則稱這兩個(gè)圖是二度同構(gòu)的。,二度同構(gòu),庫拉托夫斯基定理,一個(gè)圖是平面圖的充分必要條件是 該圖不包含二度同構(gòu)于K5或K3,3的子圖。,非平面圖證明例2,證明所示圖是非平面圖。證明 把圖中的邊ED刪去后,所得的子圖就是K3,3 ,所以此圖是非平面圖。,非平面圖證明例3,證明彼得遜圖是非平面圖。,非平面圖證明例3,證明 把DE和FH刪去, 與K3,3是二度同構(gòu)的, 所以彼得遜圖是非

溫馨提示

  • 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. 眾賞文庫僅提供信息存儲(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)論