歐拉公式證明課件

圖論—平面圖離散數(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是無限區(qū)域R1R2R3R4區(qū)域平面圖的邊把平面圖劃分成的塊R1R2R3R47歐拉公式設(shè)圖G是無向連通平面圖，它具有n個(gè)頂點(diǎn)，m條邊和r個(gè)區(qū)域，則

n-m+r=2歐拉公式設(shè)圖G是無向連通平面圖，8歐拉公式證明用歸納法，對邊數(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è)無限區(qū)域)，所以歐拉公式n-m+r=2成立；另一種是由一條自由回路構(gòu)成的圖，這時(shí)n=1，m=1，r=2，所以歐拉公式成立。歐拉公式證明用歸納法，對邊數(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)但沒增加區(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條邊的無向連通平面圖，則 3n-6≥m歐拉公式推論設(shè)圖G是具有n(≥3)個(gè)頂點(diǎn)、m條邊的無向連通平15推論證明由于G是簡單圖，因此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是簡單圖，因此G中每一個(gè)區(qū)域至少由3條邊圍成，16示例1證明K3,3是非平面圖證明由于K3,3是完全二部圖，因此每條回路由偶數(shù)條邊組成，而K3,3又是簡單圖，所以如果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)的無向完全圖K5是非平面圖證明因?yàn)樵贙5中頂點(diǎn)數(shù)n=5，邊數(shù)m=10，3n–6=9<m，不滿足平面圖的必要條件，所以K5是非平面圖。證明證明具有5個(gè)頂點(diǎn)的無向完全圖K5是非平面圖18平面圖例1設(shè)G是至少有11個(gè)頂點(diǎ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是連通簡單平面圖，所以有 3n–6≥m平面圖例1設(shè)G是至少有11個(gè)頂點(diǎ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庫拉托夫斯基定理一個(gè)圖是平面圖的充分必要條件是該圖不包含二度同構(gòu)于K5或K3,3的子圖。庫拉托夫斯基定理一個(gè)圖是平面圖的充分必要條件是23非平面圖證明例2證明所示圖是非平面圖。證明把圖中的邊ED刪去后，所得的子圖就是K3,3，所以此圖是非平面圖。ABCDEFABCDEF非平面圖證明例2證明所示圖是非平面圖。ABCDEFABCDE24非平面圖證明例3證明彼得遜圖是非平面圖。DCIABFHEGJ非平面圖證明例3證明彼得遜圖是非平面圖。DCIABFHEG25非平面圖證明例3證明把DE和FH刪去，與K3,3是二度同構(gòu)的，所以彼得遜圖是非平面圖。ABCDEFGHIJHAFIDCBEGJ非平面圖證明例3證明把DE和FH刪去，ABCDEFGHI26圖論—平面圖離散數(shù)學(xué)圖論—平面圖離散數(shù)學(xué)27平面圖如果能把一個(gè)圖在平面上畫成除端點(diǎn)外，任何兩邊都不相交，則稱此圖為可平面的，或稱平面圖。平面圖如果能把一個(gè)圖在平面上畫成除端點(diǎn)外，任何兩邊都不相交，28平面圖示例平面圖示例29平面圖示例平面圖示例30非平面圖示例非平面圖示例31非平面圖示例非平面圖示例32區(qū)域平面圖的邊把平面圖劃分成的塊例如平面圖將平面劃分成4個(gè)區(qū)域R1、R2、R3是有限區(qū)域R4是無限區(qū)域R1R2R3R4區(qū)域平面圖的邊把平面圖劃分成的塊R1R2R3R433歐拉公式設(shè)圖G是無向連通平面圖，它具有n個(gè)頂點(diǎn)，m條邊和r個(gè)區(qū)域，則

n-m+r=2歐拉公式設(shè)圖G是無向連通平面圖，34歐拉公式證明用歸納法，對邊數(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è)無限區(qū)域)，所以歐拉公式n-m+r=2成立；另一種是由一條自由回路構(gòu)成的圖，這時(shí)n=1，m=1，r=2，所以歐拉公式成立。歐拉公式證明用歸納法，對邊數(shù)進(jìn)行歸納。35歐拉公式證明（續(xù)）設(shè)當(dāng)連通平面圖具有m條邊時(shí)，歐拉公式成立。一個(gè)具有m+1條邊的連通平面圖，刪去一條邊后，仍然是平面圖。把具有m+1條邊的連通平面圖看作是由含m條邊的連通平面圖添加一條邊后構(gòu)成的。歐拉公式證明（續(xù)）設(shè)當(dāng)連通平面圖具有m條邊時(shí)，歐拉公式成立。36歐拉公式證明（續(xù)）可能有三種不同的結(jié)構(gòu)。歐拉公式證明（續(xù)）可能有三種不同的結(jié)構(gòu)。37歐拉公式證明（續(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ū)域的連通平面38歐拉公式證明（續(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ū)域的連通平面39歐拉公式證明（續(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)，歐拉公式仍然成立證畢。歐拉公式證明（續(xù)）把具有n個(gè)頂點(diǎn)，m條邊和r個(gè)區(qū)域的連通平面40歐拉公式推論設(shè)圖G是具有n(≥3)個(gè)頂點(diǎn)、m條邊的無向連通平面圖，則 3n-6≥m歐拉公式推論設(shè)圖G是具有n(≥3)個(gè)頂點(diǎn)、m條邊的無向連通平41推論證明由于G是簡單圖，因此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是簡單圖，因此G中每一個(gè)區(qū)域至少由3條邊圍成，42示例1證明K3,3是非平面圖證明由于K3,3是完全二部圖，因此每條回路由偶數(shù)條邊組成，而K3,3又是簡單圖，所以如果K3,3是平面圖，其每一個(gè)區(qū)域至少由4條邊圍成，于是有2m≥4r或r≤m/2。代入歐拉公式后可得2n－4≥m。K3,3中，n=6，m=9，不滿足上述不等式，所以K3,3不是平面圖。示例1證明K3,3是非平面圖43證明證明具有5個(gè)頂點(diǎn)的無向完全圖K5是非平面圖證明因?yàn)樵贙5中頂點(diǎn)數(shù)n=5，邊數(shù)m=10，3n–6=9<m，不滿足平面圖的必要條件，所以K5是非平面圖。證明證明具有5個(gè)頂點(diǎn)的無向完全圖K5是非平面圖44平面圖例1設(shè)G是至少有11個(gè)頂點(diǎ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是連通簡單平面圖，所以有 3n–6≥m平面圖例1設(shè)G是至少有11個(gè)頂點(diǎn)的無向簡單連通平面圖，證明G45證明（續(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ù)）由此可得46二度同構(gòu)如果兩個(gè)圖是由同一個(gè)圖的邊上插入一些新的頂點(diǎn)(它一定是2度點(diǎn))而得到的，則稱這兩個(gè)圖是二度同構(gòu)的。二度同構(gòu)如果兩個(gè)圖是由同一個(gè)圖的邊上插入一些新的頂點(diǎn)(它一定47二度同構(gòu)二度同構(gòu)48庫拉托夫斯基定理一個(gè)圖是平面圖的充分必要條件是該圖不包含二度同構(gòu)于K5或K3,3的子圖。庫拉托夫斯基定理一個(gè)圖是平面圖的充分必要條件是49非平面圖證明例2證明所示圖是非平面圖。證明把圖中的邊ED刪去后，所得的子圖就是K3,3，所以此圖是非平面圖。ABCDE