形式陈述

图 $G=(V,E)$$G=(V,E)$ 中的匹配是边集 $M\subseteq E$$M\subseteq E$，使任意两条不同边不共享端点。若顶点是 $M$$M$ 中某条边的端点，则称被 $M$$M$ 饱和。

匹配 $M$$M$ 称：

• 最大匹配，若 $|M|$$|M|$ 在所有匹配中最大；
• 极大匹配，若不存在严格包含 $M$$M$ 的匹配；
• 完美匹配，若每个顶点都被饱和。

最大必极大，极大不必最大。

直觉

匹配选择互不冲突的配对，每个顶点最多参加一次。极大只表示再也不能直接加边，最大则要求全局配对数最优。

例子与边界

在四顶点路径 $v_1v_2v_3v_4$$v_1{v}_2{v}_3{v}_4$ 中，$\{v_2v_3\}$$\{v_2{v}_3\}$ 是极大匹配但大小为 $1$$1$；$\{v_1v_2,v_3v_4\}$$\{v_1{v}_2,v_3{v}_4\}$ 是大小为 $2$$2$ 的最大且完美匹配。完美匹配若存在必为最大，但最大匹配未必完美。

推论与应用

匹配用于资源分配、婚配、调度和网络设计。增广路定理刻画最大性：匹配最大当且仅当不存在相对于它的增广路；在二分图中可用网络流高效求解。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017，§2.1。
• Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001，Ch. 3。