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

二分图

定义

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

判定

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

匹配

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

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

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

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

最大匹配算法

匈牙利算法

最大流