多重染色陷阱
两条独立色链共同困住外部候选时。
讲解
多重染色比较同一候选上两条互不连通的强链色链。若来自不同链的两种颜色互相可见,则对立颜色中必有至少一处为真,因此同时看到两种对立颜色的格子可删除该候选。
练习提示
先建简单染色链,再比较各簇颜色之间的弱链。
示例步骤
- 选定一个候选,建立两条互不连通的色链。
- 在两条链各取一色,找它们之间的弱连接。
- 从同时看到两种对立颜色的格子删除该候选。
两条独立色链共同困住外部候选时。
多重染色比较同一候选上两条互不连通的强链色链。若来自不同链的两种颜色互相可见,则对立颜色中必有至少一处为真,因此同时看到两种对立颜色的格子可删除该候选。
先建简单染色链,再比较各簇颜色之间的弱链。