二分图可匹配集的拟阵性质

俞斌

摘要：二分图是计算机理论中的一种重要模型。提出了二分图可匹配集的概念，介绍了可匹配集的拟阵性质，并基于交替路径、增广路径、对称差等概念对拟阵性质予以证明。

关键词：二分图；匹配；可匹配集；拟阵；交替路径；增广路径；对称差

中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2015）06-0093-02

Matroid in Bipartite Graphs

YU Bin

（School of Software Engineering， Tongji University， Shanghai 201804， China）

Abstract： Bipartite graph is one of the most important model in graph theory. Bring forward the concept of matchable set in bipartite graphs， and prove the matroid property on it based on alternating path， augmenting path and symmetric difference.

Key words： bipartite graph； match； matchable set； matroid； alternating path； augmenting path； symmetric difference

1 相关概念与术语

二分图（Bipartite Graph，BG）是图论中的一种特殊模型。令G=（V，E）是一个无向图。若顶点集V可划分为两个互不相交的子集（X，Y），并且图中的每条边ei=（xp，yq ）所连接的两个顶点xp和yq分别属于这两个不同的顶点集，即xp∈X，yq∈Y，则称G为一个二分图；对于若干个顶点，如果它们全属于X或者全属于Y，则我们称这若干个顶点位于G的同一侧，否则称它们位于G的不同侧。若M为E的一个子集，且M中任意两条边都不连接于同一个顶点，则称M是G的一个匹配（Matching）；若存在边e=（vx，vy ）∈M，我们称vx与vy在M中匹配；对于V中的任意一个顶点vi，若?ej∈M满足ej连接于vi，则称vi被M覆盖。对于若干个位于同一侧的顶点，若存在一个匹配M使得这些顶点均被其覆盖，则称这些顶点构成的集合V为G的一个可匹配集。规定空集是任意二分图的一个可匹配集。

一条G中的M-交替路径（M-Alternating Path of G）是指这样一条路径，其中的每一条边交替地属于或不属于匹配M。一条G中的M-增广路径（M-Augmenting Path of G）是指这样一条G中的M-交替路径，其两个端点均是没有被M覆盖的顶点。

对称差（Symmetric Difference）是一种二元集合操作。两个集合的对称差是只属于其中一个集合，而不属于另一个集合的元素形成的集合。集合A和B的对称差通常表示为A⊕B。根据定义，有A⊕B=（A-B）∪（B-A）=（A∪B）-（A∩B）。

一个拟阵是满足下列条件的一个序对 M=（S，L）：

1）S是一个有穷集合；

2）L是S的一个非空子集簇，即L是由S的子集作为元素构成的集合，且非空；

3）如果B∈L，并且A包含于B，则有A属于L。如果L满足此性质，则称之为遗传性；

4）如果A∈L，B∈L并且|B|>|A|，则有一定存在一个x∈B-A，使得集合A并上{x}之后形成的集合仍属于L，该性质称为交换性。

2 二分图可匹配集的拟阵性质描述与证明

对于一个序对MG=（SG，LG），其中SG是某二分图G一侧的所有顶点形成的集合，即SG=X或SG=Y，LG是以所有该侧的可匹配集为元素构成的集合，我们证明MG是一个拟阵。

根据可匹配集的定义，MG满足拟阵的1）2）两个条件。由于匹配的子集依然是匹配，所以可匹配集的子集依然是可匹配集。MG满足拟阵的条件3）。

我们现在证明条件4）。记X1，X2是G的两个可匹配集且|X1|>|X2|，M1与M2分别是覆盖了X1与X2的两个匹配。根据文献[1]，我们有如下引理。

引理 1. 令M、N是无向图G=（V，E）的两个匹配。G=（V，M⊕N）仅包含以下几类连通分量：

1）孤立的点

2）包含偶数条边的环，环中的每条边交替地属于M-N及N-M

3）路径，路径中的每条边交替地属于M-N及N-M

证明：由于M与N均是G的匹配，因此V中的每个顶点至多与N-M中的一条边相连，同时至多与M-N中的一条边相连。

由于|X1|>|X2|，可知G=（V，M⊕N）中必然包含至少一个连通分量，其是一条G中的M2-增广路径。记G=（V， E）为其中一个连通分量，可得M2⊕E為G中的一个匹配，其覆盖了X2中所有的顶点，且覆盖了X1-X2中的某一个顶点。所以可得存在一个x∈X1-X2，使得X2∪{x}是一个可匹配集，即X2∪{x}∈LG。

根据上述内容，我们得出如下定理。

定理 1. 序对MG=（SG，LG）是一个拟阵。其中SG是某二分图G一侧的所有顶点形成的集合，LG是以所有该侧的可匹配集为元素构成的集合。

3 结束语

作为贪心算法的理论基础，拟阵在计算机算法研究中有着重要的意义。证明二分图可匹配集的拟阵性质，有助于利用贪心算法解决其上的动态匹配问题[2-3]。

参考文献：

[1] Hopcroft J E， Karp R M. An n^（5/2） Algorithm for Maximum Matchings in Bipartite Graphs[C]. Siam Journal. on Computing. 1973（2）： 225-231.

[2] Zu Q， Zhang M， Yu B. Dynamic Matchings in Left Weighted Convex Bipartite Graphs[C]. Frontiers of Algorithmics Workshop， LNCS 2014， 8497： 330-342.

[3] Zu Q， Zhang M，Yu B. Dynamic Matchings in Left Vertex Weighted Convex Bipartite Graphs[C]. Journal of Combinatorial Optimization， LNCS，2015， 30： 1-26.

[4] Berge C. Two Theorems in Graph Theory[C]. in Proceedings of the National Academy of Sciences of the United States of America， 1957： 842-844.