问个关于二分图的算法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个关于二分图的算法

问个关于二分图的算法# JobHunting - 待字闺中

u*g2013-04-03 07:04

1 楼

问个算法。。
这样的：一个二分图，顶点上有权，删除一些顶点，使得二分图的所有边被删光，（如
果一条边(A,B)那删除A或者B都会导致这条边被删除）
问删除哪些顶点可以让累计的权最小
只想的出brute force。。求大牛指导

B*t2013-04-03 07:04

2 楼

就是找一个累计权最小的node cover呗
min cover = max match
如果没记错的话应该这样：先引入一个s(source)和一个t(sink)，然后把这两个引入的
结点分别连接bipatite两个node set(A和B)里的每个结点，边的权值就是顶点的weight
。internal node之间的边的权值为无穷大。再用个max flow算法，再用BFS找到min
cut(S)。最后node cover = (A\S)并(B 交 S)

【在 u******g 的大作中提到】

: 问个算法。。
: 这样的：一个二分图，顶点上有权，删除一些顶点，使得二分图的所有边被删光，（如
: 果一条边(A,B)那删除A或者B都会导致这条边被删除）
: 问删除哪些顶点可以让累计的权最小
: 只想的出brute force。。求大牛指导

f*e2013-04-03 07:04

3 楼

这个NP吧？

【在 u******g 的大作中提到】

u*g2013-04-03 07:04

4 楼

When is a bipartite graph, prove that the constraint matrix of this IP is
totally unimodular. Hence conclude that the natural linear programming
relaxation of this IP is integral, implying that Minimum Weighted vertex
cover is polynomially solvable on bipartite graphs.
http://trueshelf.com/exercise/214/vertex-cover-in-bipartite-gra
给跪了。。这个解释我几乎一般都没听懂。。

【在 f*****e 的大作中提到】

: 这个NP吧？

u*g2013-04-03 07:04

5 楼

仔细想了想好像的确是这样的。。太牛了。。

weight

【在 B********t 的大作中提到】

: 就是找一个累计权最小的node cover呗
: min cover = max match
: 如果没记错的话应该这样：先引入一个s(source)和一个t(sink)，然后把这两个引入的
: 结点分别连接bipatite两个node set(A和B)里的每个结点，边的权值就是顶点的weight
: 。internal node之间的边的权值为无穷大。再用个max flow算法，再用BFS找到min
: cut(S)。最后node cover = (A\S)并(B 交 S)

l*i2013-04-03 07:04

6 楼

Babyknight has the right idea. In his/her construction, every vertex cover
maps to a cut of the graph, so min weight vertex cover is min cut.
If the vertex is unweighted, then the answer is simply the size of a maximum
matching (unweighted), see Konig's theorem in wikipedia.
Bipartite vertex cover or independent set, weighted or not, is in P. totally
unimodular implies there is always an optimal solution that is integral,
just like max-flow-min-cut. This was once an MIT algorithm homework problem.