算法设计与分析课件--回溯法-图的m着色问题.pptxVIP

算法设计与分析

第五章回溯法目录5.1有哪些信誉好的足球投注网站概述回溯法算法框架5.25.5n皇后问题0-1背包问题5.3作业调度问题5.4图的m着色问题5.6

5.6图的m着色问题m图着色问题-相关概念：给定无向连通图G=(V,E)和m种不同颜色。用这些颜色为图G的各个顶点着色，每个顶点着一种颜色。如果有一种着色法使G中有边相连的两个顶点着不同颜色，则称该图是m可着色的。12345问题描述：图的m着色问题(GraphColoringProblem,GCP)是对于给定图G和m种颜色，找出所有不同的着色方法。

5.6图的m着色问题求解步骤：问题的解空间：解空间形式为(x1,x2,…,xn)，分量xi(i=1,2,…,n)表示第i个顶点着第xi号颜色。m种颜色的色号组成的集合为S={1,2…,m}。xi∈S，i=1,2,…,n。解空间的组织结构：问题的解空间组织结构是一棵满m叉树，树的深度为n。解空间有哪些信誉好的足球投注网站（剪枝函数）：约束条件：相邻顶点着不同的颜色。限界条件：无。有哪些信誉好的足球投注网站过程：回溯法。

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A12345GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A2345ABX1=11GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A345ABX1=121GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A345ABX1=121ABCX1=1X2=2GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A45ABX1=121ABCX1=1X2=23ABCX1=1X2=2DX3=3GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)A5ABX1=121ABCX1=1X2=23ABCX1=1X2=2DX3=34ABCX1=1X2=2DEX4=1X3=3GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)21345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345ABCX1=1X2=2DX3=3EX4=1FX5=3GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)ABCX1=1X2=2DX3=3EX4=1FX5=312345GX2=3GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345GX2=3ABCX1=1X2=2DX3=3EX4=1FX5=3HX3=2GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)12345GX2=3ABCX1=1X2=2DX3=3EX4=1FX5=3HX3=2IX4=1GCP示例

5.6图的m着色问题n=5,m=3的GCP：解形式(x1,x2,x3,x4,x5)xi=1(红色),2(绿色),3(蓝色)