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