歐拉公式證明用歸納法

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

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

3、一條邊后構(gòu)成的。,歐拉公式證明（續(xù)）,可能有三種不同的結(jié)構(gòu)。,歐拉公式證明（續(xù)）,把具有n個頂點，m條邊和r個區(qū)域的連通平面圖記作G(n,m,r)。在G(n,m,r)中原有的兩點中添加一條邊，增加一個區(qū)域構(gòu)成圖G(n,m+1,r+1),歐拉公式成立,歐拉公式證明（續(xù)）,把具有n個頂點，m條邊和r個區(qū)域的連通平面圖記作G(n,m,r)。在G(n,m,r)中原有的兩點中添加一條邊，增加一個區(qū)域構(gòu)成圖G(n,m+1,r+1),歐拉公式

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

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

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

7、-m條邊。 用反證法，設(shè)補圖~G也是平面圖， 則有3n – 6 ≥ (n-1)n/2-m 圖G是連通簡單平面圖，所以有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),如果兩個圖是由同一個圖的邊

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