二分图定义

顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

抽象理解：将人群分为男生和女生两部分，一对一的交往

二分图匹配

在二分图的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

最大匹配：（匈牙利算法）

选择这样的边数最大的子集称为图的最大匹配问题,最大匹配的边数称为最大匹配数。

完全匹配

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

最优匹配（KM算法）

最优匹配又称为带权最大匹配，是指在带有权值边的二分图中，求一个匹配使得匹配边上的权值和最大。一般X和Y集合顶点个数相同，最优匹配也是一个完备匹配，即每个顶点都被匹配。如果个数不相等，可以通过补点加0边实现转化。

最小覆盖

最小顶点覆盖：

最小顶点覆盖是指最少的顶点数使得二分图G中的每条边都至少与其中一个点相关联，二分图的最小顶点覆盖数=二分图的<mark>最大匹配数</mark>；

最小路径覆盖

最小路径覆盖也称为最小边覆盖，是指用尽量少的不相交简单路径覆盖二分图中的所有顶点。二分图的最小路径覆盖数=|V|-<mark>二分图的最大匹配数</mark>；

最大独立集

最大独立集是指寻找一个点集，使得其中任意两点在图中无对应边。对于一般图来说，最大独立集是一个NP完全问题，对于二分图来说最大独立集=|V|-二分图的<mark>最大匹配数</mark>。