第九章平面图与图的着色.pdf

第九章 平面图与图的着色  9.1 平面图与欧拉公式  9.1 平面图与欧拉公式（补充）  9.2 顶点着色  9.3 平面图的着色  9.4 边的着色  9.5 图着色的应用 平面图  在现实生活中，常常要画一些图形，希 望边与边之间尽量减少相交的情况，例 如印刷线路板上的布线，交通道的设计 等。  同构 9.1 平面图与欧拉公式  一、平面图  定义9.1 （平面图） 若一个图能画在平面上使它的边互不 相交（除在顶点处），则称该图为平面图， 或称该图能嵌入平面的。  图9.1(a),(b)  图9.1(a)平面图G, (b) 所示的Ğ是G的平面嵌入。  图9.2：并不是所有的图都是平面图。（K 和 5 K ） 3,3 9.1 平面图与欧拉公式  二、欧拉公式  1 定义9.2 （面/外部面/ 内部面） 平面图G嵌入平面后将Ğ分成若干 个连通闭区域，每一个连通闭区域称为G 的一个面。 恰有一个无界的面，称为外部面。 其余的面称为内部面。 9.1 平面图与欧拉公式  2 欧拉公式  （1）定理9.1 若连通平面图G有n个顶点，e条边和f 个面，则 n-e+f=2 称为欧拉公式。  证明方法：归纳法  证明：  （1）归纳基础：一条边，欧拉公式成立；  （2）归纳步骤：假设m-1条边，欧拉公式成立； 考察m条边的连通平面图： 1）若有度数为1的顶点，则删去该顶点及其关联边， 便得到连通平面图G’，G’满足欧拉公式，再将删去 的点和边加回G’得到G也满足欧拉公式； 2）若没有度数为1的顶点，则删去有界面边界上的 任一边，便得到连通平面图G’，G’满足欧拉公式， 再将删去的边加回G’得到G也满足欧拉公式。 9.1 平面图与欧拉公式  (2)推论9.1 若G是n3 的平面简单图，则e3n-6 。 证明：只证明连通的平面简单图的情况，G是n3 的平面简单图，每个面由3条或更多条边围成， 因此边的总数大于等于3f，因为每条边至多被 计算两次，所以G中至少有3f/2条边，即e3f/2 。 根据欧拉公式，有n-e+2e/32 。 所以3n-6e 。  (3)推论9.2 若平面图的每个面由四条或更多条边围成， 则e2n-4 。  证明：类似推论9.1的证明  （由学生在课堂上当场进行推导）  (4)推论9.3 K5和K3,3是非平面图。 证明：反证法：若K5是平面图，由推论9.1， 当n=5, e=10时，3n-6e不可能。所以K5 是非平面图。 若K3,3 是平面图，由推论9.2，当n=6, e=9 时，2n-4e不可能。所以K3,3是非平面图。 9.1 平面图与欧拉公式  (5)定理9.2 在平面简单图G中至少存在一个顶点v0 ， d(v ) 5 0  证明方法：反证法，假设所有顶点度数 大于5，由推论9.1，导致矛盾。 9.1 平面图与欧拉公式  三 平面图的特征  1 剖分  在G的边上插入有限个点便得到G的一个剖 分。  例：  2 定理9.3 （库拉托斯基定理） 图G是平面图 它的任何子图都不 是K5和K3,3 的剖分。