匹配 (图论)

在图论中，一个图是一个匹配（或称独立边集）是指这个图之中，任意两条边都没有公共的顶点。这时每个顶点都至多连出一条边，而每一条边都将一对顶点相匹配。

严格定义

对于一个给定的图G=(V,E)，这幅图的一个匹配M是图G的一个子图（由原来的图的一部分顶点和一部分边构成的图），其中每两条边都不相邻（没有公共顶点）。在匹配图中，一个顶点连出的边数至多是一条。如果这个顶点连出一条边，就称这个顶点是已匹配的。

图G的一个极大匹配是指这样一个匹配，它不可能是图G的任何一个匹配的真子图。换句话说，如果M是图G的一个极大匹配，那么不可能有另一个匹配包含M的全部边，而不等于M。如果一个子图包含了M，并且还有其它的边，那么必然不是匹配，也就是说一定有两条边有公共顶点。如果M是图G的一个极大匹配，那么G的每一条边都和M中的一条边相邻（否则可以加上这条边）。以下的三幅图是极大匹配的例子。

 

图G的一个最大匹配是另一个概念，指边数最多的匹配。最大匹配可能有不止一个，但最大匹配的边数是确定的，并且不可能超过图中顶点数的一半。这是因为一个匹配中的一条边对应一对（两个）顶点，而不同边所对应的两对顶点是完全不同的，否则它们就是相邻的两条边了。最大匹配中的顶点数称为图的“配对数”，一般记作${\displaystyle \nu (G)}$ 。最大匹配显然都是极大匹配，但极大匹配不一定是最大匹配。以下三幅图是最大匹配的例子。可以看出，在左起第一幅图中，最大匹配的顶点数是4，但在上面的极大匹配的例子中，存在着只有1条边的极大匹配。左起第二幅图中也是一样，最大匹配的顶点数是6，但在上面的极大匹配的例子中，存在着只有2条边的极大匹配。左起第三幅图则是一个“最大匹配必然是极大匹配”的例子。

 

图G的一个完美匹配（Perfect Match）是一个包括了图G中原来的所有顶点的匹配，是最大匹配的一种。一般来说，最大匹配不一定使用了原图的所有顶点，因此配对数小于等于原图的顶点数目，比如说上面左起第一和第三幅图。而第二幅图则是一个完美匹配的例子。完美匹配有时也叫做全局匹配或完全匹配。完美匹配同时也是一个原图的最小边数的边覆盖（即是用最少的边包括所有顶点的子图）。

一个准完美匹配则是当完美匹配不存在时的一个近似。准完美匹配中，原图只有一个顶点没有被使用，也就是说只差一个顶点达到完美匹配，这是因为原图的顶点数是奇数，完美匹配不可能存在。准完美匹配必然是最大匹配。

对一个给定的匹配M，定义：

• 一条交替路径（Alternating Path）是指这样一条路径，其中的每一条边交替地属于或不属于匹配M。比如说，第一、三、五条边属于M，而第二、四、六条不属于M，等等。
• 一条增广路径（Augmenting Path）是指从M中没有用到的顶点开始，并从M中没有用到的顶点结束的交替路径。

可以证明，一个匹配是最大匹配，当且仅当它没有任何增广路徑（这个结论有时被称为贝吉引理）。

性质

任意图中，极大匹配的边数不少于最大匹配的边数的一半^[1]。

如果A和B是两个极大匹配，那么|A| ≤ 2|B| 且 |B| ≤ 2|A|。因为，在B \ A里的每条边最多与A \ B中的两条边相连。而且，根据极大性，在A \ B中的边一定与一条B \ A中的边相连。所以${\displaystyle |A\setminus B|\leq 2|B\setminus A|.}$ 

因此我们可以得到:${\displaystyle |A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|.}$ 

特别地，这个结论告诉我们任何一个极大匹配都是最大匹配的2近似，也是最小的极大匹配的2近似。这个不等式是严格的。比如一个图G是一个4个点3条边的链，那么最小的极大匹配是1，最大匹配是2。

此外，霍爾婚配定理刻劃了二部圖中，何時能將一側全部頂點匹配到另一側。

匹配多项式

匹配多项式是一个图的k条边匹配的数量的生成函数。假定G是一个图，m_k是k条边匹配的数量。那么G的匹配多项式是

${\displaystyle \sum _{k\geq 0}m_{k}x^{k}.}$ 

另一个匹配多项式的定义是

${\displaystyle \sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k},}$ 

其中n是图中点的个数。每一种定义都有其作用，详情可以看匹配多项式的文章。

参考来源

1. Doratha E. Drake, Stefan Hougardy. A Simple Approximation Algorithm for the Weighted Matching Problem. Information Processing Letters. 

• 卢开澄,卢华明. 图论及其应用. 清华大学出版社. 1995. ISBN 978-7-302-01817-9.