图的着色.ppt

,n=7,m=15,证明G的所有面次数为3。。,要避免一个学生在同一天参加两个考试,试问最少需要安排几天进行期末考试?右图矩阵表示:(a , b)=1表示有学生同时参加a和b考试。练习0 1 0 1 0 10 1 1 1 00 1 0 10 1 10 10abcdefa b c d e f? ?? ?? ?? ?? ?? ?? ?? ?? ?2第五章图的着色Vertex Colouring3?图的着色包括顶点着色,边着色和面着色。?主要讨论简单图的顶点着色。[例]假设要安排6个期末考试,要避免一个学生在同一天参加两个考试,试问最少需要安排几天进行期末考试?例如,用矩阵表示,(a , b)=1表示有学生同时参加a和b考试。第五章图的着色0 1 0 1 0 10 1 1 1 00 1 0 10 1 10 10abcdefa b c d e f? ?? ?? ?? ?? ?? ?? ?? ?? ?4[解]以该矩阵为邻接矩阵构造图如上所示。给图的顶点染色使得相邻点具有不同颜色,最少需要3种颜色。第五章图的着色0 1 0 1 0 10 1 1 1 00 1 0 10 1 10 10abcdefa b c d e f? ?? ?? ?? ?? ?? ?? ?? ?? ?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)。 色数[例]7[例] 色数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)} 色数9[定理]对G=(V,E),?=max{deg(vi)|vi?V},则?(G) ??+1。[证明]对于结点数使用归纳法,证明G是(?+1) -可着色的。[定理] (Brooks)设G=(V,E) 是简单连通图,但不是完全图,不是奇数长度圈,?=max{deg(vi)|vi?V}?3,则?(G) ??, 即G是?-可着色的。?定理给出了色数的一个上限,但很不精确。Brooks定理也说明只存在两类满足?(G) =?+1的图。[例]二部图可2着色,但是?可以相当大。 色数10[Hajós猜想]若G是n色图,则G包含Kn的一个同胚图。?n=1,2显然,n=3,4已证,其他未决。[四色猜想]任何平面图都是4-可着色的。?由于存在着不可3-着色的平面图K4,4色问题若可证明,将是平面图色数问题的最佳结果。[五色定理]任何简单平面图都是5-可着色的。[证明](1890,Heawood)