在一张图中找到大小相等、互不重叠且并起来为整张图的完全子图。

Question

输入
具有n个顶点和整数k的无向图G，其中k是n的因子。
所有顶点的集合将用V表示。

输出
一个顶点集合S的集合，使得：

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

背景
我运行着一个小型的朗读小组，我们有时喜欢读大剧本。我想以这样一种方式为小组扮演一个大剧本，使得单个人不会扮演彼此共享场景的角色集。我意识到这个问题可以用图论来表述，我很好奇一个好的解决方案是什么样子的。

- ChocolateDrops

---

根据您的描述（包括标题），S 集合中的任何一对元素之间都不能存在边。因此，只有当 G 是由 k 个或更多组件构成的分离图时，才能存在解决方案。这是您的意图吗？如果是这样，那么更好的描述方式是二进制装箱。 - Gene

你有人物、角色和场景。人物到场景是一个固定的二分图。你想要一个从人物到角色的二分图，受到限制条件的约束。对吧？你能解释一下这如何映射到你的输入和输出定义吗？N？k？ - Ian Mercer

我怀疑这个问题是NP完全问题（它似乎介于团和集合覆盖之间）。虽然我没有证明。如果我能想出一个证明，我会发布一个完整的答案。 - colopop

你可能也希望每个人都尽可能拥有多个角色，而不是让任何人没有角色？这是否成为一个优化问题？ - Ian Mercer

@IanMercer 编辑后明确指出每个人应该被分配相同数量的角色。同时，是的——你可以用二分图来表述这个问题。问题陈述中给出的公式正确的原因如下： - ChocolateDrops

Answer 1

这个问题基本上等同于图着色。图着色要求我们给出一个图，并要求为每个节点分配一种颜色，使得没有边具有相同颜色的端点。在这里，我假设节点是角色，边是至少在一个场景中一起出现的角色，颜色是扮演角色的人，而您需要特别使用恰好k种颜色（对于k个人）进行着色。

图着色是NP难的，但除非图很大，否则约束编程求解器（例如CP-SAT）应该可以轻松处理它，并且还可以处理类似优化目标（例如）最大化每个人拥有的最小行数。

- David Eisenstat

---

在问题中，我指的是边缘表示彼此没有共同场景的字符。然而，用相反的方式表述问题，并使用图形着色解决它是等效的 - 正如你所说的那样。理想情况下，每种颜色的节点数量应该是相等的。 - ChocolateDrops