设G是n阶m条边的简单平面图-n=7-m=15-证明G的所有面次数为3.ppt

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