《设G是n阶m条边的简单平面图,n=7,m=15,证明G的所有面次数为3.ppt》由会员分享，可在线阅读，更多相关《设G是n阶m条边的简单平面图,n=7,m=15,证明G的所有面次数为3.ppt（27页珍藏版）》请在三一文库上搜索。
1、设G是n阶m条边的简单平面图,n=7,m=15,证明G的所有面次数为3。 证明正多面体有且仅有5种。,3. 假设要安排6个期末考试，要避免一个学生在同一天参加两个考试，试问最少需要安排几天进行期末考试？右图矩阵表示：(a , b)=1表示有学生同时参加a和b考试。,练习,第五章 图的着色,Vertex Colouring,图的着色包括顶点着色，边着色和面着色。 主要讨论简单图的顶点着色。,例 假设要安排6个期末考试，要避免一个学生在同一天参加两个考试，试问最少需要安排几天进行期末考试？例如，用矩阵表示,(a , b)=1表示有学生同时参加a和b考试。,第五章 图的着色,解以该矩阵为邻接矩阵构造
2、图如上所示。给图的顶点染色使得相邻点具有不同颜色，最少需要3种颜色。,第五章 图的着色,着色 图 G=(V,E) 的一个k顶点着色(k colouring)指用k种颜色对G的各顶点的一种分配方案, 使得相邻顶点的颜色都不同. 此时称G存在一个k着色，或者称G为k-可着色的(k-colourable)。 色数 使 G=(V,E) k-可着色的最小k值称为G的色数（chromatic number），记为 (G)（或(G)）。若 (G)=k，称G为k色图(k-chromatic)。,5.1 色数,5.1 色数,例,例,5.1 色数,特殊图的色数 零图： (G)=1 完全图Kn： (G)=n G是一
3、条回路： (G)=2 若|V|是偶数 (G)=3 若|V|是奇数 G是一棵非平凡树： (G)=2 (G)=2的充要条件是: (a) |E|1；(b) G中不存 在边数为奇数的回路。（此时G为二部图） 若G1、G2为G的两个连通分支，则 (G)=max(G1), (G2),5.1 色数,定理 对G=(V,E)， =maxdeg(vi)|viV，则 (G) +1。 证明对于结点数使用归纳法，证明G是(+1) -可着色的。 定理 (Brooks)设G=(V,E) 是简单连通图，但不是完全图，不是奇数长度圈， =maxdeg(vi)|viV3，则 (G) , 即G是 -可着色的。 定理给出了色数的一个
4、上限，但很不精确。Brooks定理也说明只存在两类满足(G) =+1的图。 例 二部图可2着色，但是可以相当大。,5.1 色数,Hajs猜想 若G是n色图，则G包含Kn的一个同胚图。 n=1,2显然，n=3,4已证，其他未决 。 四色猜想 任何平面图都是 4-可着色的。 由于存在着不可3-着色的平面图K4，4色问题若可证明，将是平面图色数问题的最佳结果。 五色定理 任何简单平面图都是 5-可着色的。 证明（1890，Heawood）,5.1 色数,五色定理证明,对结点数n归纳。假定n个结点的平面图可5着色。当G有n个结点时，必有一个结点v其度数6. 不妨设 dev(v)=5, 其邻接点是v1,
5、v5. 至少有两个结点不相邻，否则G包含K5, 是非平面图。设v1,v3不相邻，将v1,v3”拉至v”与v合并，其结点数n, 故可5 着色。现在将v1,v3”从中拉出”，v1,v3着色不变，此时v1,v2,v5着4种颜色，故v可着第五种颜色。,5.1 色数,如果G 的最小着色方案使得i,j着相同颜色，那么,例,i,j,i,j,ij,G,对于两个不相邻结点i,j, 如果G 的最小着色方案使得i,j着不同颜色，那么,5.1 色数,定理 G=(V,E) 为简单图，vi, vj 为其中不相邻顶点。 为在G中添加边(vi, vj) 得到的图， 为在G中合并vi, vj ，其他顶点与其关系不变，并合并多重
6、边（称为收缩 vi, vj ）得到的图。则有： (G)=min( ), ( ) 证明,例 如图， 求 (G)。,5.1 色数,(K5)=5,(K4)=4,(K4)=4,(K3)=3,定义 对给定的图 G=(V,E) ， PG(k)表示以k种颜色给G进行正常着色的方案数目。 两种方案相同：同一个结点着同一种颜色。 例如，PK3(3)=6,5.2 色数多项式,当 k0。 4色猜想：对平面图G, PG(4)0（存在4-着色方案） 若干特殊图的 PG(k) 零图： G=(V,E) ，n=|V|，|E|=0，PG(k)=kn 树：根节点在K种颜色中任取，非根节点选取与其父亲节点不同的颜色。 PG(k)=
7、k(k-1)n-1 n阶完全图： PG(k)=k(k-1)(k-2)(k-n+1),5.2 色数多项式,5.2 色数多项式,定理5-2-1 设简单图G， 和 分别如前所述，则,证明,推论1 对任何图G=(V,E)，n=|V|，m=|E|，PG(k)都是k的整系数n次多项式，且： 首项为kn； 次项为-mkn-1； 常数项为0； 各项系数的符号正-负交替。 证明 留作 习题 推论1证明了函数PG(k) 具有多项式形式。 色数多项式 上述函数 PG(k)称为图G的色数多项式。,5.2 色数多项式,加边法 求给定图G的色数多项式 原理：由定理5-2-1， PG(k) = P1(k) + P2(k)
8、P(k)1 和 P2(k) 对应图 和 。 在图G中任取两个不相邻顶点u, v； 在图G中加上 (u,v)，得新图G1， 在图G中收缩 (u,v)，得新图G2，由上述讨论有 PG(k) = PG1(k) + PG2(k) 继续分解G1和G2，直到最后全部为完全图。 利用n阶完全图的 P(k)=k(k-1)(k-2)(k-n+1) 构造图G的色数多项式。,5.2 色数多项式,例 如图，求其色数多项式。,加边法比较适合于求稠密图的色数多项式。,5.2 色数多项式,5.2 色数多项式,减边法 求给定图G的色数多项式, 在图G中任取一边e； 在图G中去掉e，得新图G1 在图G中收缩e的两端点，得新图G
9、2，由上述有 PG(k) = PG1(k) - PG2(k) 继续分解G1和G2，直到最后全部为零图。 利用n阶零图的 P(k)=kn 构造图G的色数多项式。,例 如图，求其色数多项式。,减边法比较适合于求稀疏图的色数多项式。 证明n个结点的树的色数多项式是k(k-1)n-1.,5.2 色数多项式,边着色 图 G=(V,E) 的一个边着色(edge colouring)指用k种颜色对G的各边着色, 使得相邻边的颜色都不同. 此时称G存在一个k-边着色，或者称G为k-边可着色的(k-edge colourable)。如果是k-边可着色的，而不是(k-1)-边可着色的，则称G的边色数是k, 记作(
10、G).,5.3 边着色,例,右图的边色数是。 显然，(G)(G),定理(Knig)任何二部图G的边色数为(G). 定理(Vizing)如果G是简单图，则(G)=,或者(G)=+1. Open problem: which graphs have edge-chromatic number ? http:/en.wikipedia.org/wiki/Edge_colouring,5.3 边着色,课程表假设有位老师给个班上课，如何将这些课程安排在最少的时段内？,5.3 边着色,图的着色和意义，色数概念； 特殊图的色数，图的色数求法； 理解图的色数特点，如上界，Brooks定理，五色定理等； 色数多项式特点及求法。,本章内容要求,Exercises,Develop a traffic light pattern so that traffic will flow smoothly at the cross.,