寻找图的最小顶点着色
Finding the minimum vertex coloring of a graph
我想解决 NetworkX 中的数独难题，方法是将其简化为顶点着色问题。该图对于数独网格的每个单元格都有一个顶点，当且仅当相应的单元格属于同一行、列或块时，两个顶点才相邻。线索由图中的附加边表示，图中的 9 色表示拼图的解决方案。
但是，似乎 NetworkX 中的所有顶点着色算法都是启发式算法，并且不能保证找到最小顶点着色。在我的实验中，我得到了 10 种颜色的顶点着色，即使我知道存在 9 种着色。
如何使用 NetworkX 找到最小顶点着色？
不幸的是，在 networkx 中没有针对 chromatic number problem 的精确算法。
这意味着您必须自己实现它（或找到一些可用的实现）。
您可以使用精确算法（例如 Lawler 算法）或基于 ILP 的算法。
我想解决 NetworkX 中的数独难题，方法是将其简化为顶点着色问题。该图对于数独网格的每个单元格都有一个顶点，当且仅当相应的单元格属于同一行、列或块时，两个顶点才相邻。线索由图中的附加边表示，图中的 9 色表示拼图的解决方案。
但是，似乎 NetworkX 中的所有顶点着色算法都是启发式算法，并且不能保证找到最小顶点着色。在我的实验中，我得到了 10 种颜色的顶点着色，即使我知道存在 9 种着色。
如何使用 NetworkX 找到最小顶点着色？
不幸的是，在 networkx 中没有针对 chromatic number problem 的精确算法。
这意味着您必须自己实现它（或找到一些可用的实现）。
您可以使用精确算法（例如 Lawler 算法）或基于 ILP 的算法。