精选优质文档-倾情为你奉上算法分析与设计实验报告第 六 次附加实验姓名学号班级时间12.26上午地点工训楼309 实验名称回溯法实验(图的m着色问题)实验目的1. 掌握回溯法求解问题的思想2. 学会利用其原理求解图的m着色问题实验原理问题描述：给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。基本解题步骤：(1) 针对所给问题，定义问题的解空间；(2) 确定易于搜索的解空间结构；(3) 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。实验步骤（1）首先将给定的图利用抽象图表示出来；（2）判断该节点k当前的着色是否符合条件，需要判断xk与k节点其他相邻节点h的xh是否相等；
