关于 Hall 定理的正则二分图应用推广
  • 板块学术版
  • 楼主syta
  • 当前回复10
  • 已保存回复12
  • 发布时间2025/1/1 19:28
  • 上次更新2025/1/2 12:29:11
查看原帖
关于 Hall 定理的正则二分图应用推广
505643
syta楼主2025/1/1 19:28

众所周知,两边点数相等的 kk-正则二分图可以证明存在完美匹配。

那么对于二分图 G=(X,Y,E)G=(X,Y,E),满足 XX 中点的度数相等,YY 中点的度数相等,是否可以证明此时一定存在最大匹配数为 min(X,Y)\min(|X|,|Y|),如何证明?

2025/1/1 19:28
加载中...