学习

二分图简要总结

Wider · 1月27日 · 2020年 · · 1775次已读

二分图简要总结

  • 二分图最大匹配
    参考:http://www.cnblogs.com/widerg/p/7402848.html

  • 二分图最小点覆盖
    最小点覆盖数=最大匹配数

  • 二分图最小边覆盖
    最小边覆盖数=总点数-最大匹配数

  • 二分图最大独立集
    最大独立集=总点数-最小点覆盖数

  • 二分图最大团
    二分图的最大团=补图的最大独立集。

参考资料

  • http://blog.csdn.net/hitwhacmer1/article/details/46718793
  • http://www.cnblogs.com/widerg/p/7402848.html
  • http://www.cnblogs.com/jianglangcaijin/p/6035945.html
  • http://blog.csdn.net/techmonster/article/details/50011363
  • http://dsqiu.iteye.com/blog/1689505
  • http://www.cnblogs.com/KonjakJuruo/p/5471008.html
0 条回应