流
假设G<V,E>是一个有限的有向图，它的每条边(u,v)∈都有一个非负值实数的容量c(u,v).如果（u,v）不属于E，我们假设c(u,v)=0.我们区别两个顶点：一个源s和一个汇t。一个网络流失一个对于所有结点u和V都有以下特征的实函数f:VxV->R 其容量满足以下三个要求：
- 容量限制：f(u,v)<=c(u,v)
- 斜对称：f(u,v)=-f(v,u)
- 流守恒：除非u=s或u=t，否则∑（w∈V）f(u,w)=0则该网络流的流量为s的总输出（或t的总输入）
割
设Ci为网络N中一些弧的集合，若从N中删去Ci中的所有弧，即：使得从顶点Vs到顶点Vt的路集为空集时，称Ci为Vs和Vt间的一个割。
最大流与最小割
最大流：从s到t的所有可行的网络流中，流量最大的网络流。
最小割：从s到t的割中，删除边权和最小的割。
对于一个给定的s和t，最大流=最小割
对于一个无向图G=<V,E> 点独立集：V的一个子集，使得该集合任意两点之间没有边。 点支撑集：V的一个子集，使得任意V中元素要么属于该集合，要么与该集合中有边相连。 点覆盖集：V的一个子集使得任意E中元素都与该集合中某个或某两个元素相关联。
极大/最大点独立集，极小/最小点支配集，极小/最小点覆盖集。
同样的，我们可以定义边覆盖集（即用边覆盖所有点）与边独立集（即任意两条边之间没有共同点）。
匹配
匹配：G的一个边独立集，又称为G的一个匹配。极大匹配与最大匹配。
二部图（二分图）：若无向图G的点集V可以分割成两个互不相交的子集，并且对于边集E中的所有边<vi,vj>所关联的两个顶点Vi，Vj都分属这两个子集，那么图G被称为一个二部图。
| 二部图匹配的霍尔定理（婚姻定理）：设有二部图G<V1,V2,E>且 | V1 | <= | V2 | ,则该图有完美匹配的充要条件是，对于任意V1的子集S，设 | S | =k，则与S想连的点集大小不小于k。 |
推论：若G为k-正则二部图，那么G重存在k个边不同的完全匹配。
例题分析
最小点权覆盖 假设有n行和m列 建图： 把矩阵里面的元素分为奇数和偶数的集合
建立一个二分图，把源点S到奇点集合，偶数点集合到汇点T的容量设为Mij 在奇点和偶点之间的边的容量为INF
求解：
求最小割，中间权值都是INF，所以一定是一个简单割最小割保证了
- 保证相邻至少选一个
- 求出解就是可行解
时间复杂度： （nm+2）个点
（n+m+3nm）个边 MaxFlow(nm+2,n+m+3nm)
如果使用Dinic’s算法时间复杂度是O((nm+2)^2(n+m+3nm))=O(n^6)