【线性规划与网络流24题】方格取数问题

还是个论文题

二分图的最小点权覆盖集与最大点权独立集

最小点权覆盖集:满足每一条边的两个端点至少选一个的最小权点集。

最大点权独立集:满足每一条边的两个端点最多选一个的最大权点集。

然后就是结论:

把原二分图转为网络,S向每个X集合点连一条该点权值的边,每个Y集合点向T连一条该点权值的边,原来的边流量全部变为INF。这个网络的最小割为最小点权覆盖集。

这个最小割满足了,对于中间每一条边,两端的点必定选择了一个。若一个都没有选择则S与T仍连通。且因为中间的边流量为INF所以不会是中间被堵塞。

然后我们可以证明对于每一个点权覆盖集,将选的点不选,不选的点选,得到的点集一定是一个点权独立集。因为每一条边至少选了一个,反选后就至少有一个选不了。

那么易证最大点权独立集=最小点权覆盖集的补集。

说点什么

  Subscribe  
提醒