匹配 (图论)

维基百科,自由的百科全书
跳转至: 导航搜索

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

严格定义[编辑]

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

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

Maximal-matching.svg

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

Maximum-matching-labels.svg

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

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

对一个给定的匹配M,定义:

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

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

性质[编辑]

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

参考来源[编辑]

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