文章目录

• 一、前言
• 二、二分图
• • 1、什么是二分图
  • 2、二分图的判定
  • • 1）圈的定义
    • 2）二分图判定性质
    • 3）二分图染色
    • • 3.a）深搜染色
      • 3.b）广搜染色
• 三、二分图最大匹配
• • 1、定义
  • 2、匈牙利算法
  • 3、匈牙利算法实现
• 四、二分图最大匹配的应用
• • 1、最小顶点覆盖
  • 2、最小边覆盖
  • 3、最大独立集
  • 4、最大完全子图
  • 5、有向无环图的最小路径覆盖
  • • 1）不相交的情况
    • 2）相交的情况