匹配 (图论)
严格定义
对于一个给定的图G=(V,E),这幅图的一个匹配M是图G的一个子图(由原来的图的一部分顶点和一部分边构成的图),其中每两条边都不相邻(没有公共顶点)。在匹配图中,一个顶点连出的边数至多是一条。如果这个顶点连出一条边,就称这个顶点是已匹配的。
图G的一个极大匹配是指这样一个匹配,它不可能是图G的任何一个匹配的真子图。换句话说,如果M是图G的一个极大匹配,那么不可能有另一个匹配包含M的全部边,而不等于M。如果一个子图包含了M,并且还有其它的边,那么必然不是匹配,也就是说一定有两条边有公共顶点。如果M是图G的一个极大匹配,那么G的每一条边都和M中的一条边相邻(否则可以加上这条边)。以下的三幅图是极大匹配的例子。
图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中的边相连。所以
因此我们可以得到:
特别地,这个结论告诉我们任何一个极大匹配都是最大匹配的2近似,也是最小的极大匹配的2近似。这个不等式是严格的。比如一个图G是一个4个点3条边的链,那么最小的极大匹配是1,最大匹配是2。
匹配多项式
匹配多项式是一个图的k条边匹配的数量的生成函数。假定G是一个图,mk是k条边匹配的数量。那么G的匹配多项式是
另一个匹配多项式的定义是
其中n是图中点的个数。每一种定义都有其作用,详情可以看匹配多项式的文章。
参考来源
- Doratha E. Drake, Stefan Hougardy. . Information Processing Letters.
- 卢开澄,卢华明. . 清华大学出版社. 1995. ISBN 978-7-302-01817-9.