二分图
不存在奇数环，染色法不存在矛盾
通常将点分为两个集合，看每一条边是否为连向两个集合中的点，是则为二分图
染色法辨别二分图
匈牙利算法
概念
最小点覆盖：选出最小的点集，使得每一条边的两个端点至少有一个被选出来
在二分图当中，最小点覆盖等于最大匹配数
最大独立集：从一个图中选出最多的点，使得选出的点之间没有边，内部没有边
最大团：选出最多的点，使得选出的点之间都有边
两者之间互为补集
二分图中求最大独立集等价于去掉最少的点破坏所有的边
=找最小点覆盖=找最大匹配数
即最终为n-m
最小路径点覆盖:针对有向无环图，用最少的互不相交的路径(意味着所有点不能重复)，将所有点覆盖,和最大匹配数互补
推导
拆点：
路径对应匹配点，路径终点对应一个左部的非匹配点
将路径转化为二分图，每条边最多只有一个出度入度，即两类图中只有一条边
将路径的出点入点分为两类，必为二分图
<=>让左侧非匹配点最少
<=>让左侧点匹配最多
<=>找最大匹配
最大匹配数=最小点覆盖=总点数-最大独立集=总点数-最小路径点覆盖
最小路径重复点覆盖：两条路径允许 原图的最小路径覆盖等于新图的最小路径重复点覆盖
- 先求传递闭包
- 求最小路径覆盖