Hall定理 二分图完美匹配
2024-08-25 07:08:57
充分性证明就先咕了，因为楼主太弱了，有一部分没看懂
霍尔定理内容
二分图G中的两部分顶点组成的集合分别为X, Y(假设有\(\lvert X \rvert \leq \lvert Y \rvert\))。G中有一组无公共点的边，一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W的所有邻居， 霍尔定理即对于任意W，\(\lvert W\rvert \leq \lvert N(W)\rvert\)
证明
1.必要性显然
2.充分性咕咕咕
但是仅仅是这样Hall定理是没什么用的，有一个NB的推论：
推论
假设两边的点集分别为X，Y，则二分图的最大匹配数为\(\lvert X \rvert - max\{\lvert W\rvert -\lvert N(W)\rvert \}\)，其中W是X的子集
这个推论就很厉害啦，对于一些特殊的题目，它可以免去建图而直接求最大匹配
最新文章
- loaded the "ViewController" nib but the view outlet was not set.'
- c#连接mysql环境配置
- ThinkPHP随笔
- [jetbrains系列] 外链第三方库+代码补全设置
- PHP正则表达式的快速学习方法
- delphi 10.1 berlin最新的开发框架：咏南中间件+咏南开发框架，购买后提供全部的源码
- ul li横向排列及圆点处理
- C#如何获取快捷方式指向的目标文件
- javascipt取整数四舍五入
- Android设备内存和SD卡操作工具类
- distributor之Interrupt Set/Clear-Active Registers, GICD_IS/CACTIVERn
- hr定位
- 第二周个人作业WordCount
- 转 MYSQL InnoDB Record, Gap, and Next-Key Locks
- oc语言的Foundation框架（学习笔记2）
- Java Base64位加密和解密（包括其他加密参考）
- EChart中使用地图方式总结（转载）
- MyBatis进阶（一）
- 在宿主机查看docker使用cpu、内存、网络、io情况
- pyg 图片服务器中使用的nginx 编译位置