在联合是整个图的图中寻找大小相等的互斥完全子图

Question

输入
具有 n 个顶点和一个整数 k 的无向图 G，使得 k 整除 n。
所有顶点的集合将由 V 表示。

OUTPUT
一组 S 的顶点集，使得：

1. S 有 k 个元素
2. S 的每个元素都是 G 中的一个完全子图（每个元素中的所有顶点在 G 中彼此共享一条边）
3. S 的所有元素都是互斥的（元素之间没有共同的顶点）
4. S 的所有元素的并集等于 V
5. S 的所有元素都有基数 n / k

背景
我经营一个小型剧本阅读小组，我们有时喜欢阅读大型剧本。我想以这样的方式为一小群人演一场大型戏剧，这样一个人就不会扮演一组彼此共享场景的角色。我意识到这个问题可以用图论来表述，我很好奇一个好的解决方案是什么样的。

Answer 1

这个问题基本上等价于图形着色。图形着色为我们提供了一个图形，并要求我们为每个节点指定一种颜色，以便没有边具有相同颜色的端点。在这里，我假设节点是角色，边缘是至少在一个场景中一起出现的角色，颜色是扮演角色的人，并且您特别需要一种恰好使用 k 种颜色（针对 k 个人）的着色。

图形着色是 NP 困难的，但除非图形很大，否则约束规划求解器（例如CP-SAT）应该很容易使用它，并且另外处理优化目标，例如（例如）最大化最小行数每个人都有。