AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

二分图的概念定义等

作者: 作者的头像   yxc_助手1387号 ,  2022-09-06 14:40:37 ,  所有人可见 ,  阅读 291


3


假设二分图左边是A 右边是B
1.最大匹配
匹配: 任意两条边没有公共点的集合
最大匹配: 让这个集合最大

2.最小点覆盖
定义: 用最少的点覆盖所有边
证明: 如果二分图A到B存在一条边没有被包含, 说明最大匹配之后还多了一条从A到B的边,那就不是最大匹配了

3.最小边覆盖
定义: 用最少的边覆盖所有点
证明: 用最少的边覆盖所有点,等价于找到最多的边,使这些边没有重复点。
所以最小边覆盖 = n - res

最大独立集
定义: 选出最多的点,使得点集内部没有边
证明: 因为最小点覆盖包含了所有边,所以减去最小点覆盖
所以最大独立集 = n - res

最小路径点覆盖(无重复点)
定义: 选出最少不相交路径,使得其覆盖所有点
证明: 把x到y这样的一条边分到两个集合, 集合A和集合B,既然不存在重复点,所以这样把边分配之后所有点没有重复点,所有点都不相交。
建完图之后,左边集合每一个非匹配点都对应一个路径,所以要路径最小,就要非匹配点最少,等价于找到最多的匹配点
所以最小路径点覆盖: n - res

最小路径点覆盖(有重复点)
定义: 选出最少的路径,使其覆盖所有点
证明:
在该题中,记最小路径重复点覆盖数为cnt,该题的答案就是cnt
证明:
①k<=cnt
这cnt条路径覆盖了所有的点,所以所求的k个点一定要从这cnt条路径中的点选,
并且每条路径上最多选一个点,所以k<=cnt
②k>=cnt
构造:将cnt条路径的终点都放到一个集合E中,记next(E)返回的是从E中的每个点出发能到的所有点的集合
分类讨论:
i)E ∩ next(E) = Ø ,此时E内的点不能相互到达,说明E中所有的点就是一种k=cnt的方案
ii)E ∩ next(E) ≠ Ø , 对于E中的任何一个点p,让这个点反向走,直到这个点走到一个不在next(E-p)中的点,可证当这个点走到起点时肯定不在next(E-p)中。
反证法:如果这个点走到起点,仍在next(E-p)中,说明p所在的路径的起点可以被其他路径到达,那么这条路径就没有存在的意义可以省去,不满足最小路径重复点覆盖。
所以此时同样可以在每一条路径中选出一个点,使得这些点之间两两不可到达,即k=cnt、

证明可能不够严谨,只用于自己方便记忆。

2 评论


用户头像
霊梦   2022-11-03 19:01      1    踩      回复

醍醐灌顶

用户头像
yxc_助手1387号   2022-11-03 19:04         踩      回复

你在装钩子


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息