17平面图及图的着色

《17平面图及图的着色》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、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的平面嵌入可

2、由图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立刻可

3、知，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的一个面。其中面积无限的面称为无

4、限面或外部面，面积有限的面称为有限面或内部面。包围每个面的所有边组成的回路组称为该面的边界，边界的长度称为该面的次数。　　常记外部面为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和一个

5、复杂回路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)，所得图为非平面图

6、，则称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，下

7、面只需证明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.　　在图1