有向图分割成子图

Question

给定一个DAG，其中|V|=n并且具有s个源，我们必须呈现子图，使得每个子图具有大约k1=√|s|个源和大约k2=√|n|个节点。

如果我们定义DAG的高度为从某个源到某个汇的最大路径长度。

我们要求生成的所有子图的高度大致相同。

每对节点集合（子图）的交集为空。

您可以在附带的图片中看到正确分区的示例（图中的每条边都向上指向）。

在示例中有36个节点和8个汇[#10,11,12,13,20,21,22,23]。因此，每个子图应具有6个节点和2或3个汇。

您有算法的想法吗？

非常感谢。

- YAKOVM

---

不，这不是作业，而是研究项目的一部分。 - YAKOVM

如所述，这相当于找到集合的子集。如果“叶子”表示一个节点，那么它只是列出从G中取出大小为(sqrt（|V|）的所有子集（带有它们的边缘），这是微不足道的。如果叶子是一个具有指向它但没有从它指向的边缘的节点，则使用可以成为叶子的节点执行相同操作（根据需要省略边缘），然后在所有必要节点之间进行选择（以提供“嫩枝”），然后在所有不必要的节点之间进行选择。这似乎太容易了；您确定没有其他条件吗？ - Beta

子图必须选择在这样的方式下，即禁止“子图”由不共享任何公共节点的两个“部分”组成。 - YAKOVM

所以你希望每个子图都是（无向）连通的？对于所有G来说显然不可能（例如，G没有边）。也许你的意思是其他的，或者你对G有更强的条件？ - Keith Randall

你应该学习使用Graphviz。它有非常简单的语法，并且可以生成非常漂亮的图表。http://www.graphviz.org/ - user57368

Answer 1

看起来你错过了一些信息，即使我们假设图是间接连接的。看下面的例子。
每个子图中应该有3个顶点，但是看看顶点6，如果它没有5-我们完成了，因为图不连通，就像你在评论中说的那样。
如果它是-必须至多与{7,8,9}中的一个相连-假设它与7相连。即U={5,6,7}
现在让我们看看8，假设它在U'中，由于5不在U'中，不存在可能的解决方案，其中子集U'将被连接。
请再次查看任务描述并给我们更多细节（或将此示例作为反例以显示它可能无法解决）

- amit