结合 图论中的概念与定义 食用更佳。
网络流与二分图
- Konig定理：最小点覆盖 = 最大匹配（proof）
- 二分图最大独立集 = 点数 - 最大匹配
- 二分图最大团 = 补图的最大独立集
- 最大流 = 最小割
- 二分图最小链覆盖数 = 最小边覆盖 = 节点数 - 最大匹配数
- 有孤立点的二分图没有边覆盖
- Hall 定理：二分图 \(\{X,Y\}\) 存在完美匹配的充要条件是对于 \(X\) 中的任意一个点集 \(W\), \(N(W)\) 为 \(Y\) 中与 \(W\) 联通的集合，有 \(W \leq N(W)\)
树
DAG
other
- Dilworth's Theorem：参考 深入浅出Dilworth's Theorem