二分图中的最大权独立集
6
- juver
6
你的图是如何表示的？权重在哪里？在边缘还是节点上？独立顶点集是什么意思？ - Nico Schertler
图形的表示方式并不重要。每个顶点都有一些整数权重。您可以在此处阅读关于独立集的信息 - http://en.wikipedia.org/wiki/Independent_set_(graph_theory)。 - juver
对于一般图，这个问题被认为是NP完全的。但是对于二分图，是否适用相同的方法？ - juver
1是的，使用最小割是可能的。 - Niklas B.
@NiklasB. 你能描述一下这个想法吗？ - juver
等待挑战结束。解决方案即将发布。 - shebang
2个回答
20
在任何图中，独立集的补集是一个顶点覆盖，反之亦然，因此您的问题等同于在图中找到最小权重的顶点覆盖。后者可以使用最大流技术解决：
引入一个超级源S和一个超级汇T。将二分图左侧的节点通过具有其权重作为容量的边连接到S。对于右侧也同样做并连接到汇T。将原始图的边赋予无限容量。
现在在构建的网络中找到最小的S-T割。割的值就是最小顶点覆盖的权重。为了理解这是为什么，考虑一下割边：它们不能是原始边，因为那些具有无限容量。如果切断左侧的边，则对应于将相应的左侧节点加入顶点覆盖。如果我们没有切断左侧的边，则需要从右侧上相邻节点的所有右侧边进行切断。
因此，要实际重构顶点覆盖，只需收集所有与切断边相邻的顶点，或者是从S不可达的左侧节点和可由S到达的右侧节点。
引入一个超级源S和一个超级汇T。将二分图左侧的节点通过具有其权重作为容量的边连接到S。对于右侧也同样做并连接到汇T。将原始图的边赋予无限容量。
现在在构建的网络中找到最小的S-T割。割的值就是最小顶点覆盖的权重。为了理解这是为什么，考虑一下割边：它们不能是原始边，因为那些具有无限容量。如果切断左侧的边，则对应于将相应的左侧节点加入顶点覆盖。如果我们没有切断左侧的边，则需要从右侧上相邻节点的所有右侧边进行切断。
因此，要实际重构顶点覆盖，只需收集所有与切断边相邻的顶点，或者是从S不可达的左侧节点和可由S到达的右侧节点。
- Niklas B.
-1
我认为这个问题并没有被很好地提出。首先，一个二分图已经由两个独立的集合组成。任何独立集必须是这些集合的子集，并且对于正权重它们显然必须具有较低的权重？
将二分图分割成不连通的子集也很简单，而且对于大多数实际目的，二分图将只有少量这些断开的子集，因此您可以将它们加起来。由于您可以在线性时间内找到所有独立子集，并且可以在线性时间内找到它们的权重，因此显然可以在节点+边的线性时间内完成此操作。
这让我怀疑我可能误解了您的问题。
基本上，从您的二分图开始，选择一个节点，找到与其连接的所有节点。如果这不是整个图形，则找到了一个不连通的子集，反复执行此操作。您可以在进行操作时逐步添加，因此整个过程对于每个节点和边都需要一个常数时间操作= N+E的线性时间。
- phil_20686
1
1一个二分图的独立集不一定只包含一个侧面的顶点。两个侧面组成极大独立集（假设是连通图），但不一定是最大独立集。 - Sneftel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接