查看“匹配 (图论)”的源代码

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

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

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

:[[File:Maximal-matching.svg]]

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

:[[File:Maximum-matching-labels.svg]]

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

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

对一个给定的匹配''M''，定义：
* 一条'''交替路径'''（''Alternating Path''）是指这样一条路径，其中的每一条边交替地属于或不属于匹配''M''。比如说，第一、三、五条边属于''M''，而第二、四、六条不属于''M''，等等。
* 一条'''增广路径'''（''Augmenting Path''）是指从''M''中没有用到的[[顶点 (图论)|顶点]]开始，并从''M''中没有用到的顶点结束的交替路径。

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

== 性质 ==
任意图中，极大匹配的边数不少于最大匹配的边数的一半<ref>{{cite journal | title =A Simple Approximation Algorithm for the Weighted Matching Problem |author = Doratha E. Drake, Stefan Hougardy |journal = Information Processing Letters | volume = 85 , Issue 4 (February 2003) }}</ref>。

== 参考来源 ==
<references/>
* {{cite book | title = 图论及其应用 | author = 卢开澄,卢华明 | publisher =清华大学出版社 | year =1995 | isbn =978-7-302-01817-9 }}

{{Authority control}}
[[Category:图论]]
[[Category:组合最优化]]
[[Category:多项式时间问题]]