图的m着色问题 讲课:吴双燕 PPT制作:谭晓雅 目录 问题产生的背景 问题描述 算法设计与分析 四程序运行及结果 产生背景 图的着色问题是由地图的着色问题引申而来的,用 m种颜色为地图着色,使得地图上的每一个区域 种颜色,且相邻区域颜色不同 嘉 二问题描述 给定无向连通图G和m种不同的颜色用这些颜色为图G 的各顶点着色,每个顶点着一种颜色是否有一种着色法 使G中每条边的2个顶点着不同颜色如果有