17平面图的及图的着色.ppt

图20 图19 解 小节结束 作业 习题十七： 1、3、15、24、26、29 结束 现实生活中，印刷线路板上的布线、交通道的设计等，要求尽量减少相交情况。 无向树有许多性质，这些性质中有些既是树的必要条件又是充分条件，因而都可以看作树的等价定义。 各面的边界由学生自己写。 充分性在下一节证明 欧拉在研究多面体时发现，多面体的顶点数减去棱数加上面数等于2.后来发现，连通的平面图的阶数，边数，面数之间也有同样的关系。 画上参考图，否则学生不会清楚。 欧拉公式中，平面图G的连通性是不可少的。对于非连通的平面图有下面定理成立。 证明中对各连通分支用欧拉公式，并注意即可外部面即可。 定理17.12用来判定某些图是非平面图。 插入2度顶点：右到左。 消去2度顶点：左到右。 2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树。 很多实际问题可以用2叉树或m叉树表示，如比赛。 都不是最优树 请同学们自己课下证明。 证明（3）时应同时应用欧拉公式及欧拉公式的推广. 轮图都是自对偶图。学生可以证明。 图着色问题的研究起源于四色猜想，着色问题包含点着色，边着色，平面图的面着色等。本节主要讨论点着色，规定点着色都是对无环无向图进行的。 这些定理很容易理解，所以此处无需证明，让学生理解就可以了。 注意，定理17.22中加G中至少含一条边的条件，是为了去掉零图这种特殊的二部图。 当图G既不是完全图也不是奇圈时，定理17.23给出的色数的上界可以改进。请见定理17.24。 （4）见书。 　 定理17.25的必要性证明：给学生解释一下即可。无需写出来。 给G一种k-面着色。由于G连通，由定理17.17可知，n*＝r，即G的每个面中含G*的一个顶点，设vi*位于G的Ri内，将G*的顶点vi*涂Ri的颜色。易知，若vi*与vj*相邻，则由于Ri与Rj的颜色不同，所以vi*与vj*的颜色也不同，因而G*是k-可着色的。 实线边图为平面图，虚线边图为其对偶图。 从定义不难看出G的对偶图G*有以下性质： G*是平面图，而且是平面嵌入。 G*是连通图。 若边e为G中的环，则G*与e对应的边e*为桥，若e为桥，则G*中与e对应的边e*为环。 在多数情况下，G*为多重图（含平行边的图）。 同构的平面图（平面嵌入）的对偶图不一定是同构的。 二、平面图与对偶图的阶数、边数与面数之间的关系。 定理17.17 设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) (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)。 证明 定理17.18 设G*是具有k（k?2）个连通分支的平面图G的对偶图， n*, m*, r*, n, m, r分别为G*和G的顶点数、边数和面数， （1）n*= r （2）m*=m （3）r*=n?k+1 （4）设G*的顶点v*i位于G的面Ri中，则dG*(v*i)=deg(Ri) 三、自对偶图 定义17.8 设G*是平面图G的对偶图，若G*?G，则称G为自对偶图。 在n?1(n?4)边形Cn?1内放置1个顶点，使这个顶点与Cn?1上的所有的顶点均相邻，所得n阶简单图称为n阶轮图。记为Wn。 n为奇数的轮图称为奇阶轮图。 n为偶数的轮图称为偶阶轮图。 轮图都是自对偶图。 小节结束 17.5 图中顶点的着色 规定：点着色都是对无环无向图进行的。 一、关于顶点着色的基本概念 定义17.9 （1）图G的一种着色——对无环图G的每个顶点涂上一种颜 色，使相邻顶点涂不同的颜色。 （2）对G进行k着色（G是k-可着色的）——能用k种颜色给G 的顶点着色。 （3）G的色数?(G)=k——G是k-可着色的，但不是(k?1)-可着 色的。 二、关于顶点着色的几个简单结果 定理17.19 ?(G)=1当且仅当G为零图。 定理17.20 ?(Kn)=n。 定理17.21 奇圈或奇阶轮图的色数均为3，偶阶轮图的色数为4