一些二分图相关的网络流模型转换
标签： 一些二分图相关的网络流模型转换 博客 51CTO博客
2023-05-09 18:23:59 157浏览
DAG最小不可相交路径覆盖
将每个点拆成\(x,x'\)
若\(x->y\)有边，则\(x和y'\)连边。
最小不可路径覆盖=点数-二分图最大匹配
简略证明：
考虑一开始每个点自成一条路径，答案是n条路径。
每在二分图上完成一个匹配，则把两个点代表的路径合并成1条路径，路径数-1。
要路径数最少，所以匹配数要最大。
DAG最小可相交路径覆盖
将每个点拆成\(x,x'\)
若\(x\)能到达\(y\)，则\(x和y'\)连边。
最小可路径覆盖=点数-二分图最大匹配
简略证明：
区别于不可相交路径覆盖，可相交路径让一个点作为中转点多次。
所以干脆传递闭包，这样就跨过了中转点。
二分图最小点覆盖：
最小点覆盖：选最少的点，使得每条边上的两个点有至少一个被选了。
最小点覆盖=最大匹配
简略证明：
先证明最大匹配可以对应一种顶点覆盖。
假设不能，说明有一条匹配边\((x,y)\)都有连出去的非匹配边，那么就存在更大匹配，不合法。
由上面这个，同时可以得到小于最大匹配的匹配都不能做出顶点覆盖。
二分图最大独立集（最大团）：
最大团=补图的最大独立集。
最大独立集=顶点数-最小点覆盖（最大匹配）
简略证明：
一个独立集的补集就是一个点覆盖。
要独立集最大，所以点覆盖要最小。
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
展开评论
