3月29日二分图与匈牙利算法
1.看到”二分图的一个等价定义是：不含有「含奇数条边的环」的图“时居然想了好一会儿，在环上走的时候不就相当与左右摇摆嘛，假设从左边开始，最后肯定要回到左边，那么一定会偶数了。
2.
最大匹配数：最大匹配的匹配边的数目
最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择
最大独立数：选取最多的点，使任意所选两点均不相连
最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。
定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）
定理2：最大匹配数 = 最大独立数
定理3：最小路径覆盖数 = 顶点数 - 最大匹配数【重要！！！】
评论