例如: 定理642(G)=min{(G),x(G")} 证明:考虑图G的所有可能的正常点染色方案。设l,v是G中互不相邻的两点,则在G中 的正常染色下u,v的染色有两种可能:u与v同色,或l与v异色。G的使u与v染同色 的正常点染色方案与G”的正常点染色方案一一对应,而G的使u与v染异色的正常点染色 方案与G′的正常点染色方案一一对应。因此xG)=min{(G),z(G")}。证毕。 添边粘合算法基本思想:对于给定的图G,若G是一个U阶完全图,则x(G)=U。此时给 G的每个顶点一个不同的色即可。若G不是完全图,则可取两个不相邻顶点L,v,对G进 行添边操作和粘合操作,反复进行这个过程,直至获得完全图为止。设最终得到的阶数最小 的完全图为K,则由定理642,x(G)=m。对该完全图进行顶点正常m染色,并进行反 向操作,便可得图G的顶点正常m染色。 根据定理642,添边粘合算法的运行结果是顶点染色问题的精确解。但添边粘合法的 执行过程是一棵二叉树,因此其计算复杂性是指数阶的。 例6.2求下图G的色数,及项点正常x(G)染色。 G 解:添边和粘合运算过程如下所示。10 例如： 定理 6.4.2 χ(G) = min{χ(G′), χ(G′′)}。 证明：考虑图 G 的所有可能的正常点染色方案。设 u, v 是 G 中互不相邻的两点，则在 G 中 的正常染色下 u, v 的染色有两种可能：u 与 v 同色，或 u 与 v 异色。G 的使 u 与 v 染同色 的正常点染色方案与G′′ 的正常点染色方案一一对应，而 G 的使 u 与 v 染异色的正常点染色 方案与G′的正常点染色方案一一对应。因此 χ(G) = min{χ(G′), χ(G′′)}。证毕。 添边粘合算法基本思想：对于给定的图 G，若 G 是一个υ 阶完全图，则 χ( ) G = υ 。此时给 G 的每个顶点一个不同的色即可。若 G 不是完全图，则可取两个不相邻顶点 u, v，对 G 进 行添边操作和粘合操作，反复进行这个过程，直至获得完全图为止。设最终得到的阶数最小 的完全图为 Km ，则由定理 6.4.2, χ(G) = m。对该完全图进行顶点正常 m 染色，并进行反 向操作，便可得图 G 的顶点正常 m 染色。 根据定理 6.4.2，添边粘合算法的运行结果是顶点染色问题的精确解。但添边粘合法的 执行过程是一棵二叉树，因此其计算复杂性是指数阶的。 例 6.4.2 求下图 G 的色数，及顶点正常 χ(G) 染色。 解：添边和粘合运算过程如下所示。 u v u v u v G G′ G′′ G G