💡

图论相关

创建于 2023-10-25

Tags: 笔记

  • 二分图最大匹配,最小点覆盖与最大独立集

二分图最大匹配 == 最小点覆盖,最大独立集 == 总点数 - 最小点覆盖。

  • 二分图匹配可行边,必经边,可行点与必经点

先对原图跑最大匹配,在残量网络上跑 tarjan 求强连通分量。

可行边:该边为原图上的匹配边或两点属于相同的强连通分量。

必经边:该边为原图上的匹配边且两点属于不同的强连通分量。

可行点:所有可行边的所有端点。

必经点:统计非必经点,从 SS 走流量为 11 的边走到的左部点与从 TT 走流量为 00 的边走到的右部点为非必经点。

  • Hall 定理

定义二分图的完美匹配为匹配数量 == 左部点数量。

一张二分图存在完美匹配的充要条件为:对于左部点的任意一个子集,其连到的右部点数量都 \ge 这个子集的大小。

Powered by Hexo, theme by Facter