我有一个断开的二部无向图。我想完全断开图表。我可以执行的唯一操作是删除节点。删除一个节点会自动删除它的边。任务是最小化要删除的节点数。图中的每个节点最多有 4 条边。
通过完全断开图表，我的意思是不应该通过链接连接两个节点。基本上是一个空边集。
问问题
1843 次
4 回答
7
我认为，你不能证明你的算法是最优的，因为事实上，它不是最优的。
要完全断开您的图以最小化要删除的节点数，您必须删除属于图的最小顶点覆盖的所有节点。搜索最小顶点覆盖通常是 NP 完全的，但对于二部图，有一个多项式时间的解决方案。
在图中找到最大匹配（可能使用Hopcroft–Karp 算法）。然后使用König 定理得到最小顶点覆盖：
考虑一个二分图，其中顶点被划分为左 (L) 和右 (R) 集。假设有一个最大匹配，它将边缘划分为匹配中使用的边（E_m）和不匹配的边（E_0）。令 T 包含来自 L 的所有不匹配的顶点，以及通过从 E_0 沿边从左到右以及从 E_m 沿边从右到左可从这些顶点到达的所有顶点。这实质上意味着对于 L 中的每个不匹配的顶点，我们将出现在从 E_0 和 E_m 的边之间交替的路径中出现的所有顶点添加到 T 中。
那么 (L\T) OR (R AND T) 是一个最小顶点覆盖。
于 2012-08-06T20:21:32.147 回答
3
这是您建议的算法的反例。
最好的解决方案是删除节点 A 和 B，即使它们是不同的颜色。
于 2012-08-06T20:35:03.030 回答
0
我已经想到了一个算法，但无法证明它是否是最优的。
我的算法：在每个断开的子图上，我运行一个 BFS 并相应地着色。然后我确定每种颜色着色的节点数，并取两者中的最小值并存储。我对每个子图重复该过程并加起来以获得所需的最小值。帮我证明算法是否正确。
编辑：上述算法不是最优的。接受的答案已被验证是正确的。
于 2012-08-06T19:46:32.690 回答
0
由于所有边缘都从一组到另一组，因此使用 BFS 找到这两组并使用 2 种颜色着色。然后删除较小集合中的节点。
由于它们之间没有边，其余节点也断开连接。
[作为预处理步骤，您可以先省略具有 0 条边的节点。]
于 2012-08-07T06:11:08.867 回答