离散数学平面图省名师优质课赛课获奖课件市赛课一等奖课件

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

本章小结

习题

作业4/4717.1平面图基本概念一、关于平面图一些基本概念1、平面图定义定义17.1

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

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

设G

G，若G为平面图，则G

也是平面图。设G

G，若G

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

Kn(n

5)和K3,n(n

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

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

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

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

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

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

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

3)阶极大平面图中不可能有割点和桥。11/47定理17.5

设G为n(n

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

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

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

3。因为G为平面图，又为极大平面图。可证G不可能存在次数>3面。证实思绪12/47假设存在面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-113/47只有右边图为极大平面图。因为只有该图每个面次数都为3。14/47四、极小非平面图定义17.4若在非平面图G中任意删除一条边，所得图G

为平面图，则称G为极小非平面图。由定义不难看出：K5,K3,3都是极小非平面图。极小非平面图必为简单图。比如：以下各图均为极小非平面图。小节结束15/4717.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，结论显然成立。16/47(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'=217/47定理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。18/472、与欧拉公式相关定理定理17.8

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

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也不是平面图。20/47定理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可知证实21/47定理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。22/47二、一个意义重大定理定理17.12

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

(G)

5。若阶数n

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

7时，用反证法。假设

(G)

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

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

(G)

5。本定理在图着色理论中占主要地位。说明23/47一、为判断定理做准备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平面图判断24/472、图之间同胚若两个图G1与G2同构，或经过重复插入或消去2度顶点后是同构，则称G1与G2是同胚。上面两个图分别与K3,3,K5同胚。25/47二、两个判断定理定理17.13(库拉图斯基定理1)图G是平面图当且仅当G中既不含与K5同胚子图，也不含与K3,3同胚子图。定理17.14(库拉图斯基定理2)图G是平面图当且仅当G中既没有能够收缩到K5子图，也没有能够收缩到K3,3子图。26/47例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为非平面图。27/47例17.2对K5插入2度顶点，或在K5外放置一个顶点使其与K5上若干顶点相邻，共可产生多少个6阶简单连通非同构非平面图？用插入2度顶点方法只能产生一个非平面图，如图(1)所表示。解答在K5外放置一个顶点，使其与K5上1个到5个顶点相邻，得5个图，如图(2)到(6)所表示。它与K5同胚，所以是非平面图。它们都含K5为子图，由库拉图斯基定理可知，它们都是非平面图，而且也满足其它要求。28/47例17.3由K3,3加若干条边能生成多少个6阶连通简单非同构非平面图？对K3,3加1～6条边所得图都含K3,3为子图，由库拉图斯基定理可知，它们都是非平面图。在加2条、加3条、加4条边时又各产生两个非同构非平面图，连同K3,3本身共有10个满足要求非平面图。其中，绿线边表示后加新边。解答小节结束29/4717.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*)。30/47实线边图为平面图，虚线边图为其对偶图。31/47从定义不难看出G对偶图G*有以下性质：G*是平面图，而且是平面嵌入。G*是连通图。若边e为G中环，则G*与e对应边e*为桥，若e为桥，则G*中与e对应边e*为环。在多数情况下，G*为多重图（含平行边图）。同构平面图（平面嵌入）对偶图不一定是同构。32/47二、平面图与对偶图阶数、边数与面数之间关系。定理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)33/47(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)。证实34/47定理17.16

设G*是含有k（k

2）个连通分支平面图G对偶图，n*,m*,