歐拉公式證明課件

圖論—平面圖離散數(shù)學圖論—平面圖離散數(shù)學1平面圖如果能把一個圖在平面上畫成除端點外，任何兩邊都不相交，則稱此圖為可平面的，或稱平面圖。平面圖如果能把一個圖在平面上畫成除端點外，任何兩邊都不相交，2平面圖示例平面圖示例3平面圖示例平面圖示例4非平面圖示例非平面圖示例5非平面圖示例非平面圖示例6區(qū)域平面圖的邊把平面圖劃分成的塊例如平面圖將平面劃分成4個區(qū)域R1、R2、R3是有限區(qū)域R4是無限區(qū)域R1R2R3R4區(qū)域平面圖的邊把平面圖劃分成的塊R1R2R3R47歐拉公式設圖G是無向連通平面圖，它具有n個頂點，m條邊和r個區(qū)域，則

n-m+r=2歐拉公式設圖G是無向連通平面圖，8歐拉公式證明用歸納法，對邊數(shù)進行歸納。當圖中僅有一條邊時，有兩種結(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，所以歐拉公式成立。歐拉公式證明用歸納法，對邊數(shù)進行歸納。9歐拉公式證明（續(xù)）設當連通平面圖具有m條邊時，歐拉公式成立。一個具有m+1條邊的連通平面圖，刪去一條邊后，仍然是平面圖。把具有m+1條邊的連通平面圖看作是由含m條邊的連通平面圖添加一條邊后構(gòu)成的。歐拉公式證明（續(xù)）設當連通平面圖具有m條邊時，歐拉公式成立。10歐拉公式證明（續(xù)）可能有三種不同的結(jié)構(gòu)。歐拉公式證明（續(xù)）可能有三種不同的結(jié)構(gòu)。11歐拉公式證明（續(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ū)域的連通平面12歐拉公式證明（續(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ū)域的連通平面13歐拉公式證明（續(xù)）把具有n個頂點，m條邊和r個區(qū)域的連通平面圖記作G(n,m,r)。在G(n,m,r)中添加一條邊后，增加了一個頂點但沒增加區(qū)域數(shù)構(gòu)成圖G(n+1,m+1,r)，歐拉公式仍然成立證畢。歐拉公式證明（續(xù)）把具有n個頂點，m條邊和r個區(qū)域的連通平面14歐拉公式推論設圖G是具有n(≥3)個頂點、m條邊的無向連通平面圖，則 3n-6≥m歐拉公式推論設圖G是具有n(≥3)個頂點、m條邊的無向連通平15推論證明由于G是簡單圖，因此G中每一個區(qū)域至少由3條邊圍成，若G中有r個區(qū)域，圍成r個區(qū)域總邊數(shù)為2m(因為每條邊都作為兩個相鄰區(qū)域的公共邊，被計算了兩次)。所以有 2m≥3r或r≤2m/3代入歐拉公式后得n-m+2m/3≥2從而得到3n－6≥m推論證明由于G是簡單圖，因此G中每一個區(qū)域至少由3條邊圍成，16示例1證明K3,3是非平面圖證明由于K3,3是完全二部圖，因此每條回路由偶數(shù)條邊組成，而K3,3又是簡單圖，所以如果K3,3是平面圖，其每一個區(qū)域至少由4條邊圍成，于是有2m≥4r或r≤m/2。代入歐拉公式后可得2n－4≥m。K3,3中，n=6，m=9，不滿足上述不等式，所以K3,3不是平面圖。示例1證明K3,3是非平面圖17證明證明具有5個頂點的無向完全圖K5是非平面圖證明因為在K5中頂點數(shù)n=5，邊數(shù)m=10，3n–6=9<m，不滿足平面圖的必要條件，所以K5是非平面圖。證明證明具有5個頂點的無向完全圖K5是非平面圖18平面圖例1設G是至少有11個頂點的無向簡單連通平面圖，證明G的補圖~G一定是非平面圖。證明設圖G有n個頂點(n≥11)，m條邊，顯然其補圖~G有n個頂點、(n-1)n/2-m條邊。用反證法，設補圖~G也是平面圖，則有 3n–6≥(n-1)n/2-m圖G是連通簡單平面圖，所以有 3n–6≥m平面圖例1設G是至少有11個頂點的無向簡單連通平面圖，證明G19證明（續(xù)）由此可得 6n－12≥(n-1)n/2

整理后得 n2-13n+24≤0或 n2-13n+22≤0 (n

-11)(n

-2)<0由此可得n<11，這和假設n≥11矛盾，證畢。證明（續(xù)）由此可得20二度同構(gòu)如果兩個圖是由同一個圖的邊上插入一些新的頂點(它一定是2度點)而得到的，則稱這兩個圖是二度同構(gòu)的。二度同構(gòu)如果兩個圖是由同一個圖的邊上插入一些新的頂點(它一定21二度同構(gòu)二度同構(gòu)22庫拉托夫斯基定理一個圖是平面圖的充分必要條件是該圖不包含二度同構(gòu)于K5或K3,3的子圖。庫拉托夫斯基定理一個圖是平面圖的充分必要條件是23非平面圖證明例2證明所示圖是非平面圖。證明把圖中的邊ED刪去后，所得的子圖就是K3,3，所以此圖是非平面圖。ABCDEFABCDEF非平面圖證明例2證明所示圖是非平面圖。ABCDEFABCDE24非平面圖證明例3證明彼得遜圖是非平面圖。DCIABFHEGJ非平面圖證明例3證明彼得遜圖是非平面圖。DCIABFHEG25非平