实例图解该问题回溯算法求解过程。
01、实例构造
给定如图5-43所示的无向连通图和m=3。
图的m着色问题的搜索过程如图5-44~图5-49所示。从根节点A开始，节点A是当前的活节点，也是当前的扩展节点，它代表的状态是给定无向连通图中任何一个顶点还没有着色，如图5-44(a)所示。沿着x1=1分支扩展，满足约束条件，生成的节点B成为活节点，并且成为当前的扩展节点，如图5-44(b)所示。扩展节点B沿着x2=1分支扩展，不满足约束条件，生成的节点被剪掉。然后沿着x2=2分支扩展，满足约束条件，生成的节点C成为活节点，并且成为当前的扩展节点，如图5-44(c)所示。扩展节点C沿着x3=1，2分支扩展，均不满足约束条件，生成的节点被剪掉。然后沿着x3=3分支扩展，满足约束条件，生成的节点D成为活节点，并且成为当前的扩展节点，如图5-44(d)所示。
图5-44 图的m着色问题的搜索过程（一）
扩展节点D沿着x4=1分支扩展，满足约束条件，生成的节点E成为活节点，并且成为当前的扩展节点，如图5-45(a)所示。扩展节点E沿着x5=1，2分支扩展，均不满足约束条件，生成的节点被剪掉。然后沿着x5=3分支扩展，满足约束条件，生成的节点F是叶子节点。此时，找到了一种着色方案，如图5-45(b)所示。从叶子节点F回溯到活节点E，节点E的所有孩子节点已搜索完毕，因此它成为死节点。继续回溯到活节点D，节点D再次成为扩展节点，如图5-45(c)所示。
图5-45 图的m着色问题的搜索过程（二）
扩展节点D沿着x4=2和x4=3分支扩展，均不满足约束条件，生成的节点被剪掉。再回溯到活节点C。节点C的所有孩子节点搜索完毕，它成为死节点，继续回溯到活节点B，节点B再次成为扩展节点，如图5-46(a)所示。扩展节点B沿着x2=3分支继续扩展，满足约束条件，生成的节点G成为活节点，并且成为当前的扩展节点，如图5-46(b)所示。扩展节点G沿着x3=1分支扩展，不满足约束条件，生成的节点被剪掉；然后沿着x3=2分支扩展，满足约束条件，生成的节点H成为活节点，并且成为当前的扩展节点，如图5-46(c)所示。
图5-46 图的m着色问题的搜索过程（三）
扩展节点H沿着x4=1分支扩展，满足约束条件，生成的节点I成为活节点，并且成为当前的扩展节点，如图5-47(a)所示。扩展节点I沿着x5=1分支扩展，不满足约束条件，生成的节点被剪掉；然后沿着x5=2分支扩展，满足约束条件，J已经是叶子节点，找到第2种着色方案，如图5-47(b)所示。从叶子节点J回溯到活节点I，节点I再次成为扩展节点，如图5-47(c)所示。
图5-47 图的m着色问题的搜索过程（四）
沿着节点I的 x5=3分支扩展的节点不满足约束条件，被剪掉。此时节点I成为死节点。继续回溯到活节点H，节点H再次成为扩展节点，如图5-48(a)所示。沿着节点H的x4=2，3分支扩展的节点不满足约束条件，被剪掉。此时节点H成为死节点。继续回溯到活节点G，节点G再次成为扩展节点，如图5-48(b)所示。沿着节点G的x3=3分支扩展的节点不满足约束条件，被剪掉。此时节点G成为死节点。继续回溯到活节点B，节点B的孩子节点已搜索完毕，继续回溯到节点A，如图5-48(c)所示。
图5-48 图的m着色问题的搜索过程（五）
以此类推，扩展节点A沿着x1=2，3分支扩展的情况如图5-49所示。
图5-49 图的m着色问题的搜索过程（六）
最终找到6种着色方案，分别为根节点A到如图5-49(b)所示的叶子节点F、J、O、S、X、I的路径，即(1,2,3,1,3)、(1,3,2,1,2)、(2,1,3,2,3)、(2,3,1,2,1)、(3,1,2,3,2)和(3,2,1,3,1)。
