vlambda博客
学习文章列表

给定如图5-43所示的无向连通图和m=3。

图的m着色问题的搜索过程如图5-44~图5-49所示。从根节点A开始，节点A是当前的活节点，也是当前的扩展节点，它代表的状态是给定无向连通图中任何一个顶点还没有着色，如图5-44(a)所示。沿着x₁=1分支扩展，满足约束条件，生成的节点B成为活节点，并且成为当前的扩展节点，如图5-44(b)所示。扩展节点B沿着x₂=1分支扩展，不满足约束条件，生成的节点被剪掉。然后沿着x₂=2分支扩展，满足约束条件，生成的节点C成为活节点，并且成为当前的扩展节点，如图5-44(c)所示。扩展节点C沿着x₃=1，2分支扩展，均不满足约束条件，生成的节点被剪掉。然后沿着x₃=3分支扩展，满足约束条件，生成的节点D成为活节点，并且成为当前的扩展节点，如图5-44(d)所示。

扩展节点D沿着x₄=1分支扩展，满足约束条件，生成的节点E成为活节点，并且成为当前的扩展节点，如图5-45(a)所示。扩展节点E沿着x₅=1，2分支扩展，均不满足约束条件，生成的节点被剪掉。然后沿着x₅=3分支扩展，满足约束条件，生成的节点F是叶子节点。此时，找到了一种着色方案，如图5-45(b)所示。从叶子节点F回溯到活节点E，节点E的所有孩子节点已搜索完毕，因此它成为死节点。继续回溯到活节点D，节点D再次成为扩展节点，如图5-45(c)所示。

扩展节点D沿着x₄=2和x₄=3分支扩展，均不满足约束条件，生成的节点被剪掉。再回溯到活节点C。节点C的所有孩子节点搜索完毕，它成为死节点，继续回溯到活节点B，节点B再次成为扩展节点，如图5-46(a)所示。扩展节点B沿着x₂=3分支继续扩展，满足约束条件，生成的节点G成为活节点，并且成为当前的扩展节点，如图5-46(b)所示。扩展节点G沿着x₃=1分支扩展，不满足约束条件，生成的节点被剪掉；然后沿着x₃=2分支扩展，满足约束条件，生成的节点H成为活节点，并且成为当前的扩展节点，如图5-46(c)所示。

扩展节点H沿着x₄=1分支扩展，满足约束条件，生成的节点I成为活节点，并且成为当前的扩展节点，如图5-47(a)所示。扩展节点I沿着x₅=1分支扩展，不满足约束条件，生成的节点被剪掉；然后沿着x₅=2分支扩展，满足约束条件，J已经是叶子节点，找到第2种着色方案，如图5-47(b)所示。从叶子节点J回溯到活节点I，节点I再次成为扩展节点，如图5-47(c)所示。

沿着节点I的 x₅=3分支扩展的节点不满足约束条件，被剪掉。此时节点I成为死节点。继续回溯到活节点H，节点H再次成为扩展节点，如图5-48(a)所示。沿着节点H的x₄=2，3分支扩展的节点不满足约束条件，被剪掉。此时节点H成为死节点。继续回溯到活节点G，节点G再次成为扩展节点，如图5-48(b)所示。沿着节点G的x₃=3分支扩展的节点不满足约束条件，被剪掉。此时节点G成为死节点。继续回溯到活节点B，节点B的孩子节点已搜索完毕，继续回溯到节点A，如图5-48(c)所示。

以此类推，扩展节点A沿着x₁=2，3分支扩展的情况如图5-49所示。

最终找到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)。

算法设计与分析（Python版）