juv*_*ver 4 algorithm graph-algorithm independent-set
给出二分图.每个顶点都有一些整数值 - 权重.
如果存在这样的解决方案,这个问题的算法是什么？
Nik*_* B. 15
在任何图形中,独立集合的补集是顶点覆盖,反之亦然,因此您的问题等同于在图形中找到最小权重顶点覆盖.后者可以使用最大流技术解决:
引入超级源S和超级接收器T.将二分图左侧的节点连接到S,通过其权重为容量的边缘.对右侧做同样的事情并且下沉T.为原始图形的边缘分配无限容量.
现在找到构建网络中的最小ST切割.切割的值是最小顶点覆盖的权重.要想知道为什么这是真的,请考虑切边:它们不能是原始边缘,因为它们具有无限的容量.如果切割左侧边缘,则这对应于将相应的左侧节点带入顶点覆盖.如果我们不切割左侧边缘,我们需要从右侧的相邻顶点切割所有右侧边缘.
因此,实际重构顶点覆盖,只是收集所有彼此相邻的顶点到切割的边缘,或可替代地,左侧节点不选自S到达和来自酿酒右侧节点可到达的