寻找图的最小顶点着色

Finding the minimum vertex coloring of a graph

我想解决 NetworkX 中的数独难题,方法是将其简化为顶点着色问题。该图对于数独网格的每个单元格都有一个顶点,当且仅当相应的单元格属于同一行、列或块时,两个顶点才相邻。线索由图中的附加边表示,图中的 9 色表示拼图的解决方案。

但是,似乎 NetworkX 中的所有顶点着色算法都是启发式算法,并且不能保证找到最小顶点着色。在我的实验中,我得到了 10 种颜色的顶点着色,即使我知道存在 9 种着色。

如何使用 NetworkX 找到最小顶点着色?

不幸的是,在 networkx 中没有针对 chromatic number problem 的精确算法。
这意味着您必须自己实现它(或找到一些可用的实现)。

您可以使用精确算法(例如 Lawler 算法)或基于 ILP 的算法。