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

Question

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

S 有 k 个元素

S 的每个元素都是 G 中的一个完全子图(每个元素中的所有顶点在 G 中彼此共享一条边)

S 的所有元素都是互斥的(元素之间没有共同的顶点)

S 的所有元素的并集等于 V

S 的所有元素都具有基数 n/k

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

Answer 1

这个问题基本相当于graph coloring .图形着色为我们提供了一个图形，并要求我们为每个节点指定一种颜色，以便没有边具有相同颜色的端点。在这里，我假设节点是角色，边是至少在一个场景中一起出现的角色，颜色是扮演角色的人，并且您特别想要一种使用恰好 k 种颜色(对于 k 人)的着色。
图着色是 NP-hard，但除非图很大，否则约束规划求解器(例如，CP-SAT)应该很容易使用它，并另外处理优化目标，例如(例如)最大化最小行数每个人都有。