由于我是图论**，本文定理一般情况下不给出证明。

二分图

定义

二分图又称作二部图，是图论中的一种特殊模型。
设 $G=(V, E)$ 是一个无向图。如果顶点集 $V$ 可分割为两个互不相交的子集 $X$ 和 $Y$，并且图中每条边连接的两个顶点一个在 $X$ 中，另一个在 $Y$ 中，则称图 $G$ 为二分图。

判定

  • 一个图是二分图当且仅当它无奇环。

匹配

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

  • 最大匹配就是选择边数最大的匹配。

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

显然完备匹配一定是最大匹配，而最大匹配不一定是完备匹配。

最大匹配算法

匈牙利算法

最大流