平面图专业知识课件

第17章平面图离散数学中国地质大学本科生课程第1页本章说明本章主要内容平面图基本概念欧拉公式平面图判断平面图对偶图本章所包括到图均指无向图。第2页17.1平面图基本概念17.2欧拉公式17.3平面图判断17.4平面图对偶图

本章小结

习题

作业本章主要内容第3页17.1平面图基本概念一、有关平面图某些基本概念1、平面图定义定义17.1

G可嵌入曲面S——假如图G能以这样方式画在曲面S上，即除顶点处外无边相交。

G是可平面图或平面图——若G可嵌入平面。G平面嵌入——画出无边相交平面图。非平面图——无平面嵌入图。第4页（2）是（1）平面嵌入，（4）是（3）平面嵌入。17.1平面图基本概念第5页2、几点说明及某些简单结论一般所谈平面图不一定是指平面嵌入，但讨论某些性质时，一定是指平面嵌入。K5和K3,3都不是平面图。定理17.1

设G

G，若G为平面图，则G

也是平面图。设G

G，若G

为非平面图，则G也是非平面图。由定理可知，

Kn(n

5)和K3,n(n

3)都是非平面图。定理17.2

若G为平面图，则在G中加平行边或环所得图还是平面图。

即平行边和环不影响图平面性。17.1平面图基本概念第6页二、平面图面与次数（针对平面图平面嵌入）1、定义定义17.2设G是平面图，G面——由G边将G所在平面划提成每一种区域。无限面（外部面）——面积无限面，记作R0。有限面（内部面）——面积有限面，记作R1,R2,…,Rk。面Ri边界——包围面Ri所有边组成回路组。面Ri次数——Ri边界长度，记作deg(Ri)。17.1平面图基本概念第7页2、几点说明若平面图G有k个面，可笼统地用R1,R2,…,Rk表达，不需要指出外部面。回路组是指：边界也许是初级回路（圈），也许是简单回路，也也许是复杂回路。尤其地，还也许是非连通回路之并。平面图有4个面，deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8。R1R2R3R017.1平面图基本概念第8页定理17.3

平面图G中所有面次数之和等于边数m两倍，即本定理中所说平面图是指平面嵌入。

e∈E(G)，当e为面Ri和Rj(i≠j)公共边界上边时，在计算Ri和Rj次数时，e各提供1。

当e只在某一种面边界上出现时，则在计算该面次数时，e提供2。于是每条边在计算总次数时，都提供2，因而deg(Ri)=2m。证明17.1平面图基本概念第9页三、极大平面图1、定义定义17.3若在简单平面图G中任意两个不相邻顶点之间加一条新边所得图为非平面图，则称G为极大平面图。注意：若简单平面图G中已无不相邻顶点，G显然是极大平面图，如K1（平凡图）,K2,K3,K4都是极大平面图。2、极大平面图主要性质定理17.4

极大平面图是连通，并且n(n

3)阶极大平面图中不也许有割点和桥。17.1平面图基本概念第10页定理17.5

设G为n(n

3))阶简单连通平面图，G为极大平面图当且仅当G每个面次数均为3。本节只证明必要性，即设G为n(n

3))阶简单连通平面图，G为极大平面图，则G每个面次数均为3。由于n

3,又G必为简单平面图，可知，G每个面次数均

3。由于G为平面图，又为极大平面图。可证G不也许存在次数>3面。证明思绪17.1平面图基本概念第11页假设存在面Ri次数deg(Ri)=s≥4，如图所示。在G中，若v1与v3不相邻，在Ri内加边(v1,v3)不破坏平面性，这与G是极大平面图矛盾，因而v1与v3必相邻，由于Ri存在，边(v1,v3)必在Ri外。类似地，v2与v4也必相邻，且边(v2,v4)也必在Ri外部，于是必产生(v1,v3)与(v2,v4)相交于Ri外部，这又矛盾于G是平面图，因此必有s＝3，即G中不存在次数大于或等于4面，因此G每个面为3条边所围，也就是各面次数均为3。sS-117.1平面图基本概念第12页只有右边图为极大平面图。由于只有该图每个面次数都为3。17.1平面图基本概念第13页四、极小非平面图定义17.4若在非平面图G中任意删除一条边，所得图G

为平面图，则称G为极小非平面图。由定义不难看出：K5,K3,3都是极小非平面图。极小非平面图必为简单图。例如：下列各图均为极小非平面图。小节结束17.1平面图基本概念第14页17.2欧拉公式

一、欧拉公式有关定理1、

欧拉公式定理17.6

对于任意连通平面图G，有

n-m+r=2

其中，n、m、r分别为G顶点数、边数和面数。证明对边数m作归纳法。(1)m＝0时，由于G为连通图，因此G只能是由一种孤立顶点组成平凡图，即n=1，m=0，r=1，结论显然成立。(2)m＝1时，由于G为连通图，因此n=2，m=1，r=1，结论显然成立。第15页(3)设m＝k(k≥1)时成立，当m＝k+1时，对G进行如下讨论。若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'=2若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第16页定理17.7

对于具有k(k≥2)个连通分支平面图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。第17页2、与欧拉公式有关定理定理17.8

设G为连通平面图，且每个面次数最少为l(l3)，则G边数与顶点数有如下关系：由定理17.3（面次数之和等于边数2倍）及欧拉公式得证明解得17.2欧拉公式

第18页推论

K5,K3,3不是平面图。证明若K5是平面图，由于K5中无环和平行边，因此每个面次数均大于或等于l≥3，由定理17.8可知边数10应满足10≤(3/(3-2))(5-2)=9这是个矛盾，因此K5不是平面图。若K3,3是平面图，由于K3,3中最短圈长度为l≥4，于是边数9应满足9≤(4/(4-2))(6-2)=8这又是矛盾，因此K3,3也不是平面图。17.2欧拉公式

第19页定理17.9

设G是有k(k≥2)个连通分支平面图，各面次数最少为l(l≥3)，则边数m与顶点数n应有如下关系：

定理17.10

设G为n(n

3)阶m条边简单平面图，则m

3n

6。设G有k(k

1)个连通分支，若G为树或森林，当n

3时，m=n-k

3n

6为真。若G不是树也不是森林，则G中必含圈，又由于G是简单图，因此，每个面最少由l（l

3）条边围成，又在l=3达成最大值，由定理17.9可知证明17.2欧拉公式

第20页定理17.11

设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.2欧拉公式

第21页二、一种意义重大定理定理17.12

设G为简单平面图，则G最小度

(G)

5。若阶数n

6，结论显然成立。若阶数n

7时，用反证法。假设

(G)

6，由握手定理可知：证明因而m

3n，这与定理17.10矛盾。因此，假设不成立，即G最小度

(G)

5。本定理在图着色理论中占主要地位。说明17.2欧拉公式

第22页一、为判断定理做准备1、插入2度顶点和消去2度顶点定义17.5

设e=(u,v)为图G一条边，在G中删除e，增加新顶点w，使u、v均与w相邻，称为在G中插入2度顶点w。设w为G中一种2度顶点，w与u、v相邻，删除w，增加新边(u,v)，称为在G中消去2度顶点w。17.3平面图判断第23页2、图之间同胚若两个图G1与G2同构，或通过反复插入或消去2度顶点后是同构，则称G1与G2是同胚。上面两个图分别与K3,3,K5同胚。17.3平面图判断第24页二、两个判断定理定理17.13(库拉图斯基定理1)图G是平面图当且仅当G中既不含与K5同胚子图，也不含与K3,3同胚子图。定理17.14(库拉图斯基定理2)图G是平面图当且仅当G中既没有能够收缩到K5子图，也没有能够收缩到K3,3子图。17.3平面图判断第25页例17.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.3平面图判断第26页例17.2对K5插入2度顶点，或在K5外放置一种顶点使其与K5上若干顶点相邻，共可产生多少个6阶简单连通非同构非平面图？用插入2度顶点办法只能产生一种非平面图，如图(1)所示。解答在K5外放置一种顶点，使其与K5上1个到5个顶点相邻，得5个图，如图(2)到(6)所示。它与K5同胚，因此是非平面图。它们都含K5为子图，由库拉图斯基定理可知，它们都是非平面图，并且也满足其他要求。第27页例17.3由K3,3加若干条边能生成多少个6阶连通简单非同构非平面图？对K3,3加1～6条边所得图都含K3,3为子图，由库拉图斯基定理可知，它们都是非平面图。在加2条、加3条、加4条边时又各产生两个非同构非平面图，连同K3,3本身共有10个满足要求非平面图。其中，绿线边表达后加新边。解答小节结束第28页17.4平面图对偶图一、对偶图定义定义17.6

设G是某平面图某个平面嵌入，构造G对偶图G*如下：在G面Ri中放置G*顶点vi*。设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*)。第29页实线边图为平面图，虚线边图为其对偶图。17.4平面图对偶图第30页从定义不难看出G对偶图G*有下列性质：G*是平面图，并且是平面嵌入。G*是连通图。若边e为G中环，则G*与e对应边e*为桥，若e为桥，则G*中与e对应边e*为环。在多数情况下，G*为多重图（含平行边图）。同构平面图（平面嵌入）对偶图不一定是同构。17.4平面图对偶图第31页二、平面图与对偶图阶数、边数与面数之间关系。定理17.15

设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)17.4平面图对偶图第32页(1)、(2)由G*构造可知是显然。(3)由于G与G*都连通，因而满足欧拉公式:

n-m+r=2

n*-m*+r*=2 由(1)、(2))可知，r*=2+m*-n*=2+m-r=n(4)设G面Ri边界为Ci，设Ci中有k1(k1≥0)条桥，k2个非桥边，于是

Ci长度为k2+2k1，即deg(Ri)＝k2+2k1，k1条桥对应vi*处有k1个环，k2条非桥边对应从vi*处引出k2条边，因此dG*(vi*)＝k2+2k1＝deg(Ri)。证明第33页定理17.16

设G*是具有k（k

2）个连通分支平面图G对偶图，n*,m*,r*,n,m,r分别为G*和G顶点数、边数和面数，（1）n*=r（2）m*=m（3）r*