818 图的着色.pdf

《818 图的着色.pdf》由会员分享，可在线阅读，更多相关《818 图的着色.pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 图的着色 Graph Coloring 图的着色 2 图的着色 有6种化学药品，其中药品a和b不能存放 在同一个仓库中，否则将发生化学反应， 类似地，a和d、b和e、b和f、c和d、c 和e、c和f、d和e也不能存放在同一个仓 库中，请问至少需要多少个仓库存放这6 种药品？ 3 a b c d e f 图的着色 对简单图 G 的每个顶点赋予一种颜色， 使得相邻的顶点颜色不同，称为图 G 的一种点着色点着色（vertex coloring） 对简单图 G 进行点着色所需要的最少 颜 色 数 目 ， 称 为 G 的 点 色 数点 色 数 （chromatic number），记为 (G) 对于

2、n 阶简单图 G，明显地有 (G) n 4 图的着色 5 Peterson graph 图的着色 对简单图 G 的每条边赋予一种颜色， 使得相邻的边颜色不同，称为图 G 的 一种边着色边着色（edge coloring） 对无桥平面图 G 的每个面赋予一种颜 色，使得相邻的面颜色不同，称为图 G 的一种面着色面着色（face coloring） 6 图的着色 7 Peterson graph 图的着色 8 图的着色 利用对偶图的概念，可以把平面图 G 的面着色问题转化为研究对偶图 G* 的 点着色问题 9 图的着色 10 图的着色 利用对偶图的概念，可以把平面图 G 的面着色问题转化为研究对偶

3、图 G* 的 点着色问题 而通过下面的线图概念，也可以将图 的边着色问题转化为点着色问题 11 图的着色 假设 G 是简单图，构造图 L(G)，G 中的 边和 L(G) 中的顶点一一对应，如果 G 中 的边 e1 和 e2 相邻，则在 L(G) 中与 e1 和 e2 相对应的两个顶点间连一条边，称 L(G) 是 G 的线图线图（line graph） 12 e2 e1 e4 e3 e2 e1 e4 e3 图的着色 13 图的着色 14 图的着色 例 (a) (G)=1 当且仅当 G 是离散图 (b) (Kn)=n (c) (Cn)=2，n 是偶数时； (Cn)=3，n 是奇数时（n 3） (d

4、) (G)=2 当且仅当 G 是二部图 15 图的着色 彼得森图中含有长度为5的圈，因此 至少要用3种颜色才能够正常着色 另一方面彼得森图可以用3种颜色进 行点着色 16 图的着色 17 Peterson graph 图的着色 彼得森图中含有长度为5的圈，因此 至少要用3种颜色才能够正常着色 另一方面彼得森图可以用3种颜色进 行点着色 因此彼得森图的点色数是3 18 图的着色 图 G 的点着色可以确立其顶点集 V 上的一 个等价关系 R (u, v) R 当且仅当 u 和 v 着以同一种颜色 由此可以得到 V 的一个划分 V1, V2, , Vk， 其中每个划分块 Vi 都是 G 的一个点独立集 反过来，若 V1, V2, , Vk 是 V 上对应于点 独立集的一个划分，则可由此确定 G 的一 种着色法 显然，图 G 的点色数就是将顶点集 V 关于 独立集作划分时，划分块为最少时的数目 19 图的着色 决定一个图的色数是一个难题（准确 地讲，它是一个NP完全问题），目前 尚不存在有效的方法，因此在对图进 行点着色时常采用近似算法尽管 不能得到最优结果，但是算法的执行 却是快捷有效的 20 下一讲 韦尔奇-鲍威尔算法