算法-作业12-图的m着色问题
1.问题
图的m着色问题。给定无向连通图G和m种颜色，用这些颜色给图的顶点着色，每个顶点一种颜色。如果要求G的每条边的两个顶点着不同颜色。给出所有可能的着色方案；如果不存在，则回答“NO”。
2.解析
设G有n个顶点，将顶点编号为1，2，…，n，则搜索空间为深度n的m叉完全树，将颜色编号为1,2,…,m,结点<x1,x3,…,xk>(x1,x2,…,xk属于{1,…,m},1<=k<=n)表示顶点1的颜色x1，顶点2的颜色x2,…顶点k的颜色xk。
3.设计
1)在填写每一个顶点的颜色时检查与相邻已填顶点的颜色是否相同。
2)如果不同，则填上；如果相同（冲突），则另选一种；如果已没有颜色可供选择，则回溯到上一顶点。
3)重复2，直到所有顶点的颜色都已填上。
4.分析
搜索树有：1+m+m2+…+mn<=2m^2个结点。（m>2）
每个结点要和其他所有顶点笔记哦啊颜色，进行n-1次比较。
所以最坏的时间复杂度为O(nm^n)