17平面图及图的着色.docx
- 文档编号:16486606
- 上传时间:2023-07-14
- 格式:DOCX
- 页数:29
- 大小:168.38KB
17平面图及图的着色.docx
《17平面图及图的着色.docx》由会员分享,可在线阅读,更多相关《17平面图及图的着色.docx(29页珍藏版)》请在冰点文库上搜索。
17平面图及图的着色
17.1平面图的基本概念
一、平面图及平面嵌入
定义17.1如果图G能以这样的方式画在曲面S上,即除顶点处外无边相交,则称G可嵌入曲面S.若G可嵌入平面,则称G是可平面图或平面图。
画出的无边相交的图称为G的平面嵌入。
无平面嵌入的图称为非平面图。
K1(平凡图),K2,K3,K4都是平面图,其中,K1,K2,K3本身就已经是平面嵌入,K4的平面嵌入为图17.1中(4)所示。
K5-e(K5删除任意一条边)也是平面图,它的平面嵌入可表示为图17.1中(5).完全二部图K1,n(n≥1),K2,n(n≥2),也都是平面图,其中标准画法画出的K1,n已经是平面嵌入,K2,3的平面嵌入可由图17.1中(6)给出。
图17.1中
(1),
(2),(3)分别为K4,K5-e,K2,3的标准画法。
请观看演示动画:
(1)变(4)
(2)变(5) (3)变(6)
图17.1
下文中所谈平面图,有时是指平面嵌入,有时则不是,这要看是研究平面图什么性质而定,请读者根据上下文加以区分。
当然有时也特别指出平面嵌入。
现在就应该指出,在研究平面图理论中居重要地位的两个图,这就是完全图K5和完全二部图K3,3,它们都不是平面图(将由定理17.10的推论得到证明)。
还有两个非常显然的事实,用下面定理给出。
定理17.1若图G是平面图,则G的任何子图都是平面图。
由定理17.1立刻可知,Kn(n≤4)和K1,n(n≥1)的所有子图都是平面图。
定理17.2若图G是非平面图,则G的任何母图也都是非平面图。
推论Kn(n≥5)和K3,n(n≥3)都是非平面图。
本推论由K5,K3,3不是平面图及定理17.2得证。
还有一个明显的事实也用定理给出。
定理17.3设G是平面图,则在G中加平行边或环后所得图还是平面图。
本定理说明平行边和环不影响图的平面性,因而在研究一个图是否为平面图时可不考虑平行边和环。
二、平面图的面与次数
定义17.2设G是平面图(且已是平面嵌入),由G的边将G所在的平面划分成若干个区域,每个区域都称为G的一个面。
其中面积无限的面称为无限面或外部面,面积有限的面称为有限面或内部面。
包围每个面的所有边组成的回路组称为该面的边界,边界的长度称为该面的次数。
常记外部面为R0,内部面为R1,R2,…,Rk,面R的次数记为deg(R).
定义17.2中的回路组应该这样理解:
组中元素可能是圈,可能是简单回路,也可能是复杂回路,或以上元素之并。
图17.2所示图是某图的平面嵌入,它有5个面。
R1的边界为圈abdc,deg(R1)=4.R2的边界也是圈,此圈为efg,deg(R2)=3,R3的边界为环h,deg(R3)=1.R4的边界为圈kjl,deg(R4)=3.外部面R0的边界由一个简单回路abefgdc和一个复杂回路kjihil组成,deg(R0)=13.
图17.2
定理17.4平面图G中所有面的次数之和等于边数m的两倍,即
deg(Ri)=2m
其中r为G的面数。
证本定理中所说平面图当然是指平面嵌入。
e∈E(G),若e为面Ri和Rj(i≠j)的公共边界上的边时,在计算Ri和Rj的次数时,e各提供1.而当e只在某一个面的边界上出现时,如图17.2中的边i,则在计算该面的次数时,e提供2.于是每条边在计算总次数时,都提供2,因而
deg(Ri)=2m.
三、极大平面图及性质
定义17.3设G为简单平面图,若在G的任意不相邻的顶点u,v之间加边(u,v),所得图为非平面图,则称G为极大平面图。
从定义不难看出,K1,K2,K3,K4,,K5-e(K5删除任意一条边)都是极大平面图。
还可以容易地证明下面两个定理。
定理17.5极大平面图是连通的。
定理17.6设G是n(n≥3)阶极大平面图,则G中不可能存在割点和桥。
极大平面图的最大特点由下面定理给出。
定理17.7设G为n(n≥3)阶简单连通的平面图,G为极大平面图当且仅当G的每个面的次数均为3.
证本定理的充分性留在第二节的最后证明,下面只证必要性。
图17.3
因为G为简单平面图,所以G中无环和平行边。
由定理17.5和17.6可知,G中无割点和桥。
于是G中各面的次数大于或等于3,下面只需证明G各面的次数不可能大于3.假设面Ri的次数deg(Ri)=s≥4,见图17.3所示。
在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.
在图17.4所示的各平面图中,只有(3)是极大平面图。
图17.4
四、极小非平面图
定义17.4若在非平面图G中任意删除一条边,所得图为平面图,则称G为极小非平面图。
请读者验证,K5和K3,3都是极小非平面图。
17.2欧拉公式
一、欧拉公式及其推广
欧拉在研究多面体时发现,多面体的顶点数减去棱数加上面数等于2.后来发现,连通的平面图的阶数,边数,面数之间也有同样的关系。
定理17.8(欧拉公式)对于任意的连通的平面图G,有
n-m+r=2
其中,n,m,r分别为G的顶点数,边数和面数。
证对边数m作归纳法。
(1)m=0时,由于G为连通图,所以G只能是平凡图,结论显然成立。
(2)设m=k(k≥1)时成立,当m=k+1时,对G进行如下讨论。
若G是树,则G是非平凡的,因而G中至少有两片树叶,设v为树叶,令G'=G-v,则G'仍然是连通图,且G'的边数m'=m-1=k,由归纳假设可知
n'-m'+r'=2
式中n',m',r'分别为G'的顶点数,边数和面数。
而n'=n-1,r'=r,于是
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'-m'+r'=2
而n'=n,r'=r-1,于是
n-m+r=n'-(m'+1)-(r'+1)=n'-m'+r'=2
下一页
欧拉公式中,平面图G的连通性是不可少的。
对于非连通的平面图有下面定理成立。
定理17.9(欧拉公式的推广)对于具有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)
易知,m=
mi,n=
ni,由于每个Gi有一个外部面,而G只有一个外部面,所以G的面数r=
ri-k+1,于是,对(17.1)的两边同时求和得
2k=
(ni-mi+ri)
=
ni-
mi+
ri
=n-m+r+k-1
经过整理得
n-m+r=k+1
将定理17.9称为欧拉公式的推广。
由欧拉公式及其推广可以得到平面图的另外一些性质。
二、平面图的边数m与顶点数n的关系
定理17.10设G是连通的平面图,且每个面的次数至少为l(l≥3),则G的边数m与顶点数n有如下关系:
m≤
(n-2)
证由定理17.4可知:
2m=
deg(Ri)≥l·r (17.2)
由欧拉公式可知:
r=2+m-n (17.3)
将(17.3)代入(17.2)得
2m≥l(2+m-n)
经过整理得
m≤
(n-2)
推论K5与K3,3都不是平面图。
证若K5是平面图,由于K5中无环和平行边,所以每个面的次数均大于或等于l≥3,由定理17.10可知边数10应满足
10≤
(5-2)=9
这是个矛盾,所以K5不是平面图。
类似地,若K3,3是平面图,由于K3,3中最短圈的长度为l≥4,于是边数9应满足
9≤
(6-2)=8
这又是矛盾的,所以K3,3也不是平面图。
下一页
定理17.11设G是有k(k≥2)个连通分支的平面图,各面的次数至少为l(l≥3),则边数m与顶点数n应有如下关系:
m≤
(n-k-1)
利用欧拉公式的推广形式容易证明此定理。
定理17.12设G是n(n≥3)阶m条边的简单平面图,则
m≤3n-6
证设G有k(k≥1)个连通分支。
若G为树或森林,则m=n-k≤3n-6(n≥3).若G不是树也不是森林,则G中必含有圈。
又因为G为简单图,所以各圈的长度均大于或等于3,因各面次数至少为l(l≥3).又
=1+
在l=3时达到最大值3,由定理17.11可知
m≤
(n-k-1)≤3(n-2)=3n-6
定理17.13设G是n(n≥3)阶m条边的极大平面图,则
m=3n-6
证由于极大平面图是连通图,由欧拉公式得:
r=2+m-n (17.4)
又因为G是极大平面图,由定理17.7的必要性可知,G的每个面的次数均为3,所以:
2m=
deg(Ri)=3·r (17.5)
将(17.4)代入(17.5),整理后得m=3n-6.
三、简单平面图G中,δ(G)≤5
定理17.14设G是简单平面图,则G的最小度δ≤5.
证若G的阶数n≤6,结论显然成立。
因而仅就n≥7讨论。
若δ≥6,由握手定理可知
2m=
d(vi)≥6n
因而m≥3n,这与定理17.12相矛盾。
本定理在图着色理论中占重要地位。
在本节结束之前,来证明定理17.7的充分性:
由定理17.4可知:
2m=
deg(Ri)=3·r (17.6)
又因为G是连通的,由欧拉公式可知:
r=2+m-n (17.7)
将(17.7)代入(17.6),经过整理得:
m=3n-6 (17.8)
若G不是极大平面图,则G中一定存在不相邻的顶点u,v,使得G'=G∪(u,v)还是简单平面图,而G'的边数m'=m+1,n'=n.由(17.8)可知,
m'>3n'-6
这与定理17.12相矛盾。
17.3平面图的判断
一、库拉图斯基的两个定理
为了讨论平面图的判别法,还需要给出下面两个定义。
定义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.6若两个图G1与G2同构,或通过反复插入或消去2度顶点后是同构的,则称G1与G2是同胚的。
在图17.5中,
(1)与K3同胚,
(2)与K4同胚。
图17.5
定理17.15(库拉图斯基定理1)图G是平面图当且仅当G中既不含与K5同胚子图,也不含与K3,3同胚子图。
本定理的证明略。
定理17.16(库拉图斯基定理2)图G是平面图当且仅当G中既没有可以收缩到K5的子图,也没有可以收缩到K3,3的子图。
本定理的证明略。
关于边的收缩见定义14.10.
例17.1证明彼得松图不是平面图。
证将彼得松图顶点标顺序,见图17.6中
(1)所示。
在图中将边(a,f),(b,g),(c,h),(d,i),(e,j)收缩,所得图为图17.6中
(2)所示,它是K5,由定理17.16可知,彼得松图不是平面图。
还可以这样证明:
用G表示彼得松图,令
G'=G-{(j,g),(c,d)}
G'如图17.6中(3)所示,易知它与K3,3同胚,由定理17.15可知,G为非平面图。
图17.6
例17.2对K5插入2度顶点,或在K5外放置一个顶点使其与K5上的若干个顶点相邻,共可产生多少个6阶简单连通非同构的非平面图?
解由于所要求的非平面图是6阶的,因而用插入2度顶点的方法只能产生一个非平面图,见图17.7中
(1)所示的图,它与K5同胚,所以是非平面图。
在K5外放置一个顶点,使其与K5上的1个到5个顶点相邻,得5个图如图17.7中
(2)到(6)所示,它们都含K5为子图,由库拉图斯基定理可知,它们都是非平面图,并且也满足其它要求。
图17.7
例17.3由K3,3加若干条边能生成多少个6阶连通的简单的非同构的非平面图?
解对K3,3加1~6条边所得图都含K3,3为子图,由库拉图斯基定理可知,它们都是非平面图。
在加2条,加3条,加4条边时又各产生两个非同构的非平面图,连同K3,3本身共有10个满足要求的非平面图,在图17.8中给出了各图。
其中,绿线边表示后加的新边。
图17.8
讨论
现在可以问这样的问题:
6阶的连通的简单的非同构的非平面图共有多少个?
其实,例17.2中图17.7中给出的6个图,例17.3中图17.8中给出的10个图都满足要求,但仔细观察发现图17.7中的(4),(5),(6)分别与图17.8中的(8),(9),(10)同构,因而6阶的连通的简单的非同构的非平面图共有13个,它们都是K6的子图。
17.4平面图的对偶图
一.平面图的对偶图
定义17.7设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*).
从定义不难看出G的对偶图G*有以下性质:
1.G*是平面图,而且是平面嵌入。
2.G*是连通图。
3.若边e为G中的环,则G*与e对应的边e*为桥,若e为桥,则G*中与e对应的边e*为环。
4.在多数情况下,G*为多重图(含平行边的图)。
5.同构的平面图(平面嵌入)的对偶图不一定是同构的。
图17.9中
(1),
(2)所示的图(黑线边的图)是同构的,但它们的对偶图不是同构的。
图17.9
二.对偶图的性质
平面图G与它的对偶图G*的顶点数,边数和面数有如下定理给出的关系。
定理17.17设G*是连通平面图G的对偶图,n*,m*,r*和n,m,r分别为G*和G的顶点数,边数,面数,则
(1)n*=r
(2)m*=m
(3)r*=n
(4)设G*的顶点vi*位于G的面Ri中,则dG*(vi*)=deg(Ri).
证由G*的构造可知,
(1),
(2)是显然的。
(3)由于G与G*都连通,因而满足欧拉公式:
n-m+r=2 (17.9)
n*-m*+r*=2 (17.10)
由
(1),
(2)及(17.9),(17.10)可知
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).
定理17.18设G*是具有k(k≥2)个连通分支的平面图G的对偶图,则
(1)n*=r
(2)m*=m
(3)r*=n-k+1
(4)设vi*位于G的面Ri中,则dG*(vi*)=deg(Ri).其中n*,m*,r*,n,m,r同定理17.17.
请读者自己证明。
三.自对偶图
定义17.8设G*是平面图G的对偶图,若G*
G,则称G为自对偶图。
在图17.10
(1),
(2),(3)中黑线边图都是自对偶图。
在n-1(n≥4)边形Cn-1内放置一个顶点,使这个顶点与Cn-1上的所有顶点均相邻。
所得n阶简单图称为n阶轮图。
n为奇数的轮图称为奇阶轮图,n为偶数的轮图称为偶阶轮图,常将n阶轮图记为Wn.图17.10(3)中,黑边图为奇阶轮图W5.可以证明轮图都是自对偶图。
图17.10
主要内容
1.
平面图及平面嵌入。
2.
平面图的面与次数。
3.
极大平面图及性质。
4.
极小非平面图。
5.
欧拉公式及其推广。
6.
平面图的边数m与顶点数n的关系。
7.
简单平面图G中,δ(G)≤5。
8.
库拉图斯基的两个定理。
9.
平面图的对偶图。
学习要求
1.
深刻理解本部分的基本概念:
平面图、平面嵌入、平面图的面、次数、极大平面图、极小非平面图、平面图的对偶图、自对偶图等。
2.
熟练掌握极大平面的性质,特别是充分必要条件。
3.
熟练掌握并会应用欧拉公式及其推广形式。
4.
掌握由欧拉公式及其推广形式所证明的平面的性质。
5.
会用库拉图斯基定理证明某些图不是平面图。
6.
掌握平面图与其对偶图某些关系的定理。
典型习题
1.
设G是简单平面图,面数r<12,δ(G)≥3。
(1)证明G中存在次数小于等于4的面。
(2)举例说明,当r=12,其它条件不变时,
(1)中结论不真。
2.
设G是n(n≥11)阶无向简单图,证明G或
必为非平面图。
3.
证明下图中
(1)与
(2)均为非平面图。
4.
设G为n(n≥4)阶极大平面图,证明G的对偶图G*是2边-连通的3-正则图。
5.
设G为n阶m条边的简单连通平面图,证明:
当n=7,m=15时,G为极大平面图。
6.
设G*为平面图G的对偶图,G**是G*的对偶图,在什么条件下G**与G一定不同构?
又在什么条件下G**
G。
17.5图中顶点的着色
一、顶点的着色与点色数
图着色问题的研究起源于四色猜想,着色问题包含点着色,边着色,平面图的面着色等。
本节主要讨论点着色,规定点着色都是对无环无向图进行的。
定义17.9对无环图G的每个顶点涂上一种颜色,使相邻的顶点涂不同的颜色,称为对图G的一种着色。
若能用k种颜色给G的顶点着色,就称对G进行了k着色,也称G是k-可着色的。
若G是k-可着色的,但不是(k-1)-可着色的,就称G是k色图,并称这样的k为G的色数,记作χ(G)=k,不混淆时,色数χ(G)也可简记作χ.
二、关于点色数的一些定理
从定义不难看出下面定理都成立。
定理17.19χ(G)=1当且仅当G是零图。
定理17.20χ(Kn)=n.
定理17.21奇圈和奇阶轮图的色数均为3,而偶阶轮图的色数为4.
定理17.22设G中至少含一条边,则χ(G)=2当且仅当G为二部图。
注意,本定理中加G中至少含一条边的条件,是为了去掉零图这种特殊的二部图。
定理17.23对于任意的图G(当然G中不含环),均有
χ(G)≤Δ(G)+1
证对G的阶数n作归纳法。
n=1时,结论显然为真,设n=k(k≥1)时结论成立,当G的阶数n=k+1时,证明如下。
设v为G中任一个顶点,令G'=G-v,则G1的阶数为k,由归纳假设可知χ(G')≤Δ(G')+1≤Δ(G)+1.当将G1还原成G时,由于v至多与G1中Δ(G)个顶点相邻,而在G1的点着色中,Δ(G)个顶点至多用了Δ(G)种颜色,于是在Δ(G)+1种颜色中至少存在一种颜色给v涂色,使v与相邻顶点涂不同颜色。
下一页
当图G既不是完全图也不是奇圈时,定理17.23给出的色数的上界可以改进。
请见下面定理。
定理17.24设连通图G不是完全图Kn(n≥3),也不是奇圈,则
χ(G)≤Δ(G)
本定理的证明略。
本定理称为布鲁克斯(Brooks)定理。
例17.4求图17.11所示各图的色数。
图17.11
解为方便起见,记图17.11中的4个图依次的为G1,G2,G3(彼得松图)和G4.因为G1为二部图,由定理17.22可知,χ(G1)=2.G2为6阶轮图W6,由定理17.21可知,χ(G2)=4.由于Δ(G3)=3,利用布鲁克斯定理可知,χ(G3)≤3,又因为G3中有奇圈,由定理17.21知,χ(G3)≥3,于是χ(G3)=3.由布鲁克斯定理可知,χ(G4)≤Δ(G4)=4,又因为G4中有奇圈,于是χ(G4)≥3,因而χ(G4)为3或4,请读者讨论,用3种颜色不可能给G4着色,于是只能是χ(G4)=4.
17.6地图的着色与平面图的点着色
一、地图及其面着色、面色数
定义17.10连通无桥平面图的平面嵌入及其所有的面称为平面地图或地图,地图的面称为“国家”。
若两个国家的边界至少有一条公共边,则称这两个国家是相邻的。
定义17.11对地图G的每个国家涂上一种颜色,使相邻的国家涂不同的颜色,称为对G的一种面着色,若能用k种颜色给G的面着色,就称对G的面进行了k着色,或称G是k-面可着色的。
若G是k-面可着色的,但不是(k-1)-面可着色的,就称G的面色数为k,记作χ*(G)=k.
研究地图的着色可以转化成对它的对偶图的点着色,见下面定理。
定理17.25地图G是k-面可着色的当且仅当它的对偶图G*是k-可着色的。
证必要性。
给G一种k-面着色。
由于G连通,由定理17.17可知,n*=r,即G的每个面中含G*的一个顶点,设vi*位于G的Ri内,将G*的顶点vi*涂Ri的颜色,易知,若vi*与vj*相邻,则由于Ri与Rj的颜色不同,所以vi*与vj*的颜色也不同,因而G*是k-可着色的。
类似地可证充分性。
由定理17.25可知,研究地图的着色(面着色),等价于研究平面图的点着色。
对于平面图的点着色问题,到目前为止,人们证明了下面定理。
二、平面图的五色定理
定理17.26任何平面图都是5-可着色的。
本定理
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 17 平面图 着色