离散数学平面图课件

本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容平面图的基本概念平面图的基本概念欧拉公式欧拉公式平面图的判断平面图的判断平面图的对偶图平面图的对偶图本章所涉及到的图均指无向图。本章所涉及到的图均指无向图。q17.1 17.1 平面图的基本概念平面图的基本概念q17.2 17.2 欧拉公式欧拉公式q17.3 17.3 平面图的判断平面图的判断q17.4 17.4 平面图的对偶图平面图的对偶图q 本章小结本章小结q 习习 题题q 作作 业业17.1 17.1 平面图的基本概念平面图的基本概念平面图的基本概念平面图的基本概念一、关于平面图的一些基本概念一、关于平面图的一些基本概念1、平面图的定义平面图的定义定义定义17.117.1qG可可嵌嵌入入曲曲面面S如如果果图图G能能以以这这样样的的方方式式画画在在曲曲面面S上上，即除顶点处外无边相交。即除顶点处外无边相交。qG是可平面图或平面图是可平面图或平面图若若G可嵌入平面可嵌入平面。qG的平面嵌入的平面嵌入画出的无边相交的平面图。画出的无边相交的平面图。q非平面图非平面图无平面嵌入的图。无平面嵌入的图。（2）是（是（1）的平面嵌入，（）的平面嵌入，（4）是（）是（3）的平面嵌入。）的平面嵌入。2、几点说明及一些简单结论几点说明及一些简单结论q一一般般所所谈谈平平面面图图不不一一定定是是指指平平面面嵌嵌入入，但但讨讨论论某某些些性性质质时时，一定是指平面嵌入。一定是指平面嵌入。qK5和和K3,3都不是平面图。都不是平面图。q定理定理17.117.1 设设GG，若若G为平面图，则为平面图，则G 也是平面图。也是平面图。q设设GG，若若G 为非平面图，则为非平面图，则G也是非平面图。也是非平面图。q由定理可知，由定理可知，Kn(n 5)和和K3,n(n 3)都是非平面图。都是非平面图。q定理定理17.17.2 2 若若G为平面图，则在为平面图，则在G中加平行边或环所得图还是中加平行边或环所得图还是平面图。平面图。即平行边和环不影响图的平面性。即平行边和环不影响图的平面性。二、平面图的面与次数（针对平面图的平面嵌入）二、平面图的面与次数（针对平面图的平面嵌入）1、定义定义定义定义17.217.2设设G是平面图，是平面图，qG的面的面由由G的边将的边将G所在的平面划分成的每一个区域。所在的平面划分成的每一个区域。q无限面（外部面）无限面（外部面）面积无限的面，记作面积无限的面，记作R0。q有限面（内部面）有限面（内部面）面积有限的面面积有限的面，记作，记作R1,R2,Rk。q面面Ri的边界的边界包围面包围面Ri的所有边组成的回路组。的所有边组成的回路组。q面面Ri的次数的次数Ri边界的长度，记作边界的长度，记作deg(Ri)。2、几点说明、几点说明q若若平平面面图图G有有k个个面面，可可笼笼统统地地用用R1,R2,Rk表表示示，不不需需要指出外部面。要指出外部面。q回回路路组组是是指指：边边界界可可能能是是初初级级回回路路（圈圈），可可能能是是简简单单回回路路，也也可可能能是是复复杂杂回回路路。特特别别地地，还还可可能能是是非非连连通通的的回回路路之并。之并。平面图有平面图有4个面，个面，deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8。R1R2R3R0定理定理17.17.3 3平面图平面图G中所有面的次数之和等于边数中所有面的次数之和等于边数m的两倍，即的两倍，即本定理中所说平面图是指平面嵌入。本定理中所说平面图是指平面嵌入。eE(G)，当当e为面为面Ri和和Rj(ij)的公共边界上的边时，在计算的公共边界上的边时，在计算Ri和和Rj的次的次数时，数时，e各提供各提供1。当当e只在某一个面的边界上出现时，则在计算该面的次数时，只在某一个面的边界上出现时，则在计算该面的次数时，e提供提供2。于是每条边在计算总次数时，都提供于是每条边在计算总次数时，都提供2，因而，因而deg(Ri)=2m。证证明明三、极大平面图三、极大平面图1、定义定义定定义义17.317.3若若在在简简单单平平面面图图G中中的的任任意意两两个个不不相相邻邻的的顶顶点点之之间加一条新边所得图为非平面图，则称间加一条新边所得图为非平面图，则称G为极大平面图。为极大平面图。注注意意：若若简简单单平平面面图图G中中已已无无不不相相邻邻顶顶点点，G显显然然是是极极大大平平面图，如面图，如K1（平凡图）平凡图）,K2,K3,K4都是极大平面图。都是极大平面图。2、极大平面图的主要性质、极大平面图的主要性质定定理理17.17.4 4极极大大平平面面图图是是连连通通的的，并并且且n(n 3)阶阶极极大大平平面面图图中不可能有割点和桥。中不可能有割点和桥。定定理理17.17.5 5设设G为为n(n 3)阶阶简简单单连连通通的的平平面面图图，G为为极极大大平平面面图当且仅当图当且仅当G的每个面的次数均为的每个面的次数均为3。q本节只证明必要性，即本节只证明必要性，即设设G为为n(n 3)阶简单连通的平面图，阶简单连通的平面图，G为极大平面图，则为极大平面图，则G的每个面的次数均为的每个面的次数均为3。q由于由于n 3,又又G必为简单平面图，可知，必为简单平面图，可知，G每个面的次数均每个面的次数均 3。q因因为为G为为平平面面图图，又又为为极极大大平平面面图图。可可证证G不不可可能能存存在在次次数数3的面。的面。证证明明思思路路假设存在面假设存在面Ri的次数的次数deg(Ri)=s4，如图所示。如图所示。在在G中，若中，若v1与与v3不相邻，在不相邻，在Ri内加边内加边(v1,v3)不破坏平面性，这不破坏平面性，这与与G是极大平面图矛盾，因而是极大平面图矛盾，因而v1与与v3必相邻，由于必相邻，由于Ri的存在，边的存在，边(v1,v3)必在必在Ri外。外。类似地，类似地，v2与与v4也必相邻，且边也必相邻，且边(v2,v4)也必在也必在Ri外部，于是必外部，于是必产生产生(v1,v3)与与(v2,v4)相交于相交于Ri的外部，这又矛盾于的外部，这又矛盾于G是平面图，是平面图，所以必有所以必有s3，即即G中不存在次数大于或等于中不存在次数大于或等于4的面，所以的面，所以G的的每个面为每个面为3条边所围，也就是各面次数均为条边所围，也就是各面次数均为3。sS-1只有右边的图为极大平面图。只有右边的图为极大平面图。因为只有该图每个面的次数都为因为只有该图每个面的次数都为3。四、极小非平面图四、极小非平面图定定义义17.417.4若若在在非非平平面面图图G中中任任意意删删除除一一条条边边，所所得得图图G为为平平面面图，则称图，则称G为极小非平面图。为极小非平面图。由定义不难看出：由定义不难看出：qK5,K3,3都是极小非平面图。都是极小非平面图。q极小非平面图必为简单图。极小非平面图必为简单图。例如：例如：以下各图均为极小非平面图。以下各图均为极小非平面图。小节结束小节结束17.2 17.2 欧拉公式欧拉公式 一、欧拉公式相关定理一、欧拉公式相关定理1、欧拉公式欧拉公式定理定理17.17.6 6 对于任意的连通的平面图对于任意的连通的平面图G，有有n-m+r=2其中，其中，n、m、r分别为分别为G的顶点数、边数和面数。的顶点数、边数和面数。证明证明对边数对边数m作归纳法。作归纳法。(1)m0时，由于时，由于G为连通图，所以为连通图，所以G只能是由一个孤立顶只能是由一个孤立顶点组成的平凡图，即点组成的平凡图，即n=1，m=0，r=1，结论显然成立。结论显然成立。(2)m1时，由于时，由于G为连通图，所以为连通图，所以n=2，m=1，r=1，结结论显然成立。论显然成立。(3)设设mk(k1)时成立，当时成立，当mk+1时，对时，对G进行如下讨论。进行如下讨论。q若若G是树，则是树，则G是非平凡的，因而是非平凡的，因而G中至少有两片树叶。中至少有两片树叶。设设v为树叶，令为树叶，令G=G-v，则则G仍然是连通图，且仍然是连通图，且G的边数的边数m=m-1=k，n=n-1，r=r。由假设可知由假设可知n-m+r=2，式中式中n，m，r分别为分别为G的顶点数，的顶点数，边数和面数。边数和面数。于是于是n-m+r=(n+1)-(m+1)+r=n-m+r=2q若若G不是树，则不是树，则G中含圈。中含圈。设边设边e在在G中某个圈上，令中某个圈上，令G=G-e，则则G仍连通且仍连通且m=m-1=k，n=n，r=r-1。由假设有由假设有n-m+r=2。于是于是n-m+r=n-(m+1)-(r+1)=n-m+r=2定理定理17.17.7 7 对于具有对于具有k(k2)个连通分支的平面图个连通分支的平面图G，有有n-m+r=k+1其中其中n，m，r分别为分别为G的顶点数，边数和面数。的顶点数，边数和面数。证明证明设设G的连通分支分别为的连通分支分别为G1、G2、Gk，并设并设Gi的顶点数、边的顶点数、边数、面数分别为数、面数分别为ni、mi、ri、i=1，2，k。由欧拉公式可知由欧拉公式可知:ni-mi+ri=2，i=1，2，k(17.1)易知，易知，由于每个由于每个Gi有一个外部面，而有一个外部面，而G只有一个外部面，所以只有一个外部面，所以G的面数的面数于是，于是，对对(17.1)的两边同时求和得的两边同时求和得经整理得经整理得n-m+r=k+1。2、与欧拉公式有关的定理与欧拉公式有关的定理定定理理17.17.8 8设设G为为连连通通的的平平面面图图，且且每每个个面面的的次次数数至至少少为为l(l3)，则则G的边数与顶点数有如下关系：的边数与顶点数有如下关系：由定理由定理17.3（面的次数之和等于边数的（面的次数之和等于边数的2倍）及欧拉公式得倍）及欧拉公式得证明证明解得解得推论推论 K5,K3,3不是平面图。不是平面图。证明证明q若若K5是平面图，由于是平面图，由于K5中无环和平行边，所以每个面的次数中无环和平行边，所以每个面的次数均大于或等于均大于或等于l3，由由定理定理17.8可知边数可知边数10应满足应满足10(3/(3-2)(5-2)=9这是个矛盾，所以这是个矛盾，所以K5不是平面图。不是平面图。q若若K3,3是平面图，由于是平面图，由于K3,3中最短圈的长度为中最短圈的长度为l4，于是边数于是边数9应满足应满足9(4/(4-2)(6-2)=8这又是矛盾的，所以这又是矛盾的，所以K3,3也不是平面图。也不是平面图。定理定理17.17.9 9 设设G是有是有k(k2)个连通分支的平面图，各面的次数至个连通分支的平面图，各面的次数至少为少为l(l3)，则边数则边数m与顶点数与顶点数n应有如下关系：应有如下关系：定理定理17.117.10 0设设G为为n(n 3)阶阶m条边的简单平面图，则条边的简单平面图，则m 3n 6。设设G有有k(k 1)个连通分支，个连通分支，q若若G为树或森林，当为树或森林，当n 3时，时，m=n-k 3n 6为真。为真。q若若G不是树也不是森林，则不是树也不是森林，则G中必含圈，又因为中必含圈，又因为G是简单图，是简单图，所以，每个面至少由所以，每个面至少由l（l 3）条边围成，又在条边围成，又在l=3达到最大达到最大值，由定理值，由定理17.9可知可知证明证明定理定理17.117.11 1设设G为为n(n 3)阶阶m条边的极大平面图，则条边的极大平面图，则m=3n 6。证明证明由于极大平面图是连通图，由欧拉公式得由于极大平面图是连通图，由欧拉公式得:r=2+m-n(17.4)又因为又因为G是极大平面图，由定理是极大平面图，由定理17.7的必要性可知，的必要性可知，G的每个的每个面的次数均为面的次数均为3，所以：，所以：将将(17.4)代入代入(17.5)，整理后得，整理后得m=3n-6。二、一个意义重大的定理二、一个意义重大的定理 定理定理17.117.12 2设设G为简单平面图，则为简单平面图，则G的最小度的最小度(G)5。q若阶数若阶数n 6，结论显然成立。结论显然成立。q若阶数若阶数n 7时，用反证法。时，用反证法。假设假设(G)6，由握手定理可知：由握手定理可知：证明证明因而因而m 3n，这与定理这与定理17.10矛盾。矛盾。所以，假设不成立，即所以，假设不成立，即G的最小度的最小度(G)5。q本定理在图着色理论中占重要地位。本定理在图着色理论中占重要地位。说明说明一、为判断定理做准备一、为判断定理做准备1、插入插入2度顶点和消去度顶点和消去2度顶点度顶点定义定义17.517.5 q设设e=(u,v)为为图图G的的一一条条边边，在在G中中删删除除e，增增加加新新的的顶顶点点w，使使u、v均与均与w相邻，称为在相邻，称为在G中中插入插入2度顶点度顶点w。q设设w为为G中中一一个个2度度顶顶点点，w与与u、v相相邻邻，删删除除w，增增加加新新边边(u,v)，称为在称为在G中中消去消去2度顶点度顶点w。17.3 17.3 平面图的判断平面图的判断2、图之间的同胚、图之间的同胚若若两两个个图图G1与与G2同同构构，或或通通过过反反复复插插入入或或消消去去2度度顶顶点点后后是是同构的，则称同构的，则称G1与与G2是是同胚同胚的。的。上面两个图分别与上面两个图分别与K3,3,K5同胚同胚。二、两个判断定理二、两个判断定理定定理理17.117.13 3(库库拉拉图图斯斯基基定定理理1)图图G是是平平面面图图当当且且仅仅当当G中中既既不不含与含与K5同胚子图，也不含与同胚子图，也不含与K3,3同胚子图。同胚子图。定定理理17.117.14 4(库库拉拉图图斯斯基基定定理理2)图图G是是平平面面图图当当且且仅仅当当G中中既既没没有可以收缩到有可以收缩到K5的子图，也没有可以收缩到的子图，也没有可以收缩到K3,3的子图。的子图。例例17.117.1证明彼得松图不是平面图。证明彼得松图不是平面图。将彼得松图顶点标顺序，见图将彼得松图顶点标顺序，见图(1)所示。所示。证证明明还可以这样证明：还可以这样证明：用用G表示彼得松图，令表示彼得松图，令G=G-(j,g),(c,d)G如图如图(3)所示，易知它与所示，易知它与K3,3同胚，同胚，在图中将边在图中将边(a,f),(b,g),(c,h),(d,i),(e,j)收缩，收缩，所得图为图所得图为图(2)所示，它是所示，它是K5，由定理由定理17.16可知，彼得松图不是平面图。可知，彼得松图不是平面图。由定理由定理17.15可知，可知，G为非平面图。为非平面图。例例17.217.2对对K5插入插入2度顶点，或在度顶点，或在K5外放置一个顶点使其与外放置一个顶点使其与K5上的若上的若干顶点相邻，共可产生多少个干顶点相邻，共可产生多少个6阶简单连通非同构的非平面图？阶简单连通非同构的非平面图？用用插插入入2度度顶顶点点的的方方法法只只能能产产生生一个非平面图，如图一个非平面图，如图(1)所示。所示。解答解答在在K5外外放放置置一一个个顶顶点点，使使其其与与K5上上的的1个个到到5个个顶顶点点相相邻邻，得得5个图，如图个图，如图(2)到到(6)所示。所示。它与它与K5同胚，所以是非平面图。同胚，所以是非平面图。它它们们都都含含K5为为子子图图，由由库库拉拉图图斯斯基基定定理理可可知知，它它们们都都是是非非平平面图，并且也满足其它要求。面图，并且也满足其它要求。例例17.317.3由由K3,3加若干条边能生成多少个加若干条边能生成多少个6阶连通的简单的非同构的非阶连通的简单的非同构的非平面图？平面图？对对K3,3加加16条边所得图都含条边所得图都含K3,3为子图，由库拉图斯基定理可为子图，由库拉图斯基定理可知，它们都是非平面图。知，它们都是非平面图。在加在加2条、加条、加3条、加条、加4条边时又各产生两个非同构的非平面图，条边时又各产生两个非同构的非平面图，连同连同K3,3本身共有本身共有10个满足要求的非平面图。其中，绿线边表示个满足要求的非平面图。其中，绿线边表示后加的新边。后加的新边。解答解答小节结束小节结束17.4 17.4 平面图的对偶图平面图的对偶图一、对偶图的定义一、对偶图的定义定定义义17.17.6 6设设G是是某某平平面面图图的的某某个个平平面面嵌嵌入入，构构造造G的的对对偶偶图图G*如下：如下：q在在G的面的面Ri中放置中放置G*的顶点的顶点vi*。q设设e为为G的任意一条边，的任意一条边，若若e在在G的的面面Ri与与Rj的的公公共共边边界界上上，做做G*的的边边e*与与e相相交交，且且e*关关联联G*的的位位于于Ri与与Rj中中的的顶顶点点vi*与与vj*，即即e*=(vi*,vj*)，e*不与其它任何边相交。不与其它任何边相交。若若e为为G中的桥且在面中的桥且在面Ri的边界上，则的边界上，则e*是以是以Ri中中G*的顶点的顶点vi*为端点的环，即为端点的环，即e*=(vi*,vi*)。实线边图为平面图，虚线边图为其对偶图。实线边图为平面图，虚线边图为其对偶图。从定义不难看出从定义不难看出G的对偶图的对偶图G*有以下性质：有以下性质：qG*是平面图，而且是平面嵌入。是平面图，而且是平面嵌入。qG*是连通图。是连通图。q若若边边e为为G中中的的环环，则则G*与与e对对应应的的边边e*为为桥桥，若若e为为桥桥，则则G*中与中与e对应的边对应的边e*为环。为环。q在多数情况下，在多数情况下，G*为多重图（含平行边的图）。为多重图（含平行边的图）。q同构的平面图（平面嵌入）的对偶图不一定是同构的。同构的平面图（平面嵌入）的对偶图不一定是同构的。二、平面图与对偶图的阶数、边数与面数之间的关系。二、平面图与对偶图的阶数、边数与面数之间的关系。定定理理17.117.15 5设设G*是是连连通通平平面面图图G的的对对偶偶图图，n*、m*、r*和和n、m、r分别为分别为G*和和G的顶点数、边数和面数，则的顶点数、边数和面数，则（1）n*=r（2）m*=m（3）r*=n（4）设设G*的顶点的顶点v*i位于位于G的面的面Ri中，则中，则dG*(vi*)=deg(Ri)q(1)、(2)由由G*的构造可知是显然的。的构造可知是显然的。q(3)由于由于G与与G*都连通，因而满足欧拉公式都连通，因而满足欧拉公式:n-m+r=2n*-m*+r*=2由由(1)、(2)可知，可知，r*=2+m*-n*=2+m-r=nq(4)设设G的面的面Ri的边界为的边界为Ci，设设Ci中有中有k1(k10)条桥，条桥，k2个非桥边，个非桥边，于是于是Ci的长度为的长度为k2+2k1，即即deg(Ri)k2+2k1，k1条桥对应条桥对应vi*处有处有k1个环，个环，k2条非桥边对应从条非桥边对应从vi*处引出处引出k2条边，条边，所以所以dG*(vi*)k2+2k1deg(Ri)。证证明明定定理理17.117.16 6设设G*是是具具有有k（k 2）个个连连通通分分支支的的平平面面图图G的的对对偶偶图图，n*,m*,r*,n,m,r分分别别为为G*和和G的的顶顶点点数数、边边数数和面数，和面数，（1）n*=r（2）m*=m（3）r*=n k+1（4）设设G*的顶点的顶点v*i位于位于G的面的面Ri中，则中，则dG*(v*i)=deg(Ri)三、自对偶图三、自对偶图定定义义17.17.7 7设设G*是是平平面面图图G的的对对偶偶图图，若若G*G，则则称称G为为自自对对偶偶图。图。q在在n 1(n 4)边边形形Cn 1内内放放置置1个个顶顶点点，使使这这个个顶顶点点与与Cn 1上上的的所所有有的的顶顶点点均均相相邻邻，所所得得n阶阶简简单单图图称称为为n阶阶轮轮图图。记记为为Wn。qn为奇数的轮图称为为奇数的轮图称为奇阶轮图奇阶轮图。qn为偶数的轮图称为为偶数的轮图称为偶阶轮图偶阶轮图。q轮图都是自对偶图。轮图都是自对偶图。小节结束小节结束本章主本章主要内容要内容q平面图及平面嵌入。平面图及平面嵌入。q平面图的面与次数。平面图的面与次数。q极大平面图及性质。极大平面图及性质。q极小非平面图。极小非平面图。q欧拉公式及其推广。欧拉公式及其推广。q平面图的边数平面图的边数m与顶点数与顶点数n的关系。的关系。q简单平面图简单平面图G中，中，(G)5。q库拉图斯基的两个定理。库拉图斯基的两个定理。q平面图的对偶图。平面图的对偶图。本章学习要求本章学习要求q深深刻刻理理解解本本部部分分的的基基本本概概念念：平平面面图图、平平面面嵌嵌入入、平平面面图图的的面面、次次数数、极极大大平平面面图图、极极小小非非平平面面图图、平平面面图图的的对对偶偶图图、自自对对偶偶图等。图等。q熟练掌握极大平面的性质，特别是充分必要条件。熟练掌握极大平面的性质，特别是充分必要条件。q熟练掌握并会应用欧拉公式及其推广形式。熟练掌握并会应用欧拉公式及其推广形式。q掌握由欧拉公式及其推广形式所证明的平面的性质。掌握由欧拉公式及其推广形式所证明的平面的性质。q会用库拉图斯基定理证明某些图不是平面图。会用库拉图斯基定理证明某些图不是平面图。q掌握平面图与其对偶图某些关系的定理。掌握平面图与其对偶图某些关系的定理。解 证 证 作业作业习题十七习题十七：1 1、3 3、1515、2424、2626、2929结束结束