二分圖可匹配集的擬陣性質(zhì)

俞斌

摘要：二分圖是計算機理論中的一種重要模型。提出了二分圖可匹配集的概念，介紹了可匹配集的擬陣性質(zhì)，并基于交替路徑、增廣路徑、對稱差等概念對擬陣性質(zhì)予以證明。

關(guān)鍵詞：二分圖；匹配；可匹配集；擬陣；交替路徑；增廣路徑；對稱差

中圖分類號：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 相關(guān)概念與術(shù)語

二分圖（Bipartite Graph，BG）是圖論中的一種特殊模型。令G=（V，E）是一個無向圖。若頂點集V可劃分為兩個互不相交的子集（X，Y），并且圖中的每條邊ei=（xp，yq ）所連接的兩個頂點xp和yq分別屬于這兩個不同的頂點集，即xp∈X，yq∈Y，則稱G為一個二分圖；對于若干個頂點，如果它們?nèi)珜儆赬或者全屬于Y，則我們稱這若干個頂點位于G的同一側(cè)，否則稱它們位于G的不同側(cè)。若M為E的一個子集，且M中任意兩條邊都不連接于同一個頂點，則稱M是G的一個匹配（Matching）；若存在邊e=（vx，vy ）∈M，我們稱vx與vy在M中匹配；對于V中的任意一個頂點vi，若?ej∈M滿足ej連接于vi，則稱vi被M覆蓋。對于若干個位于同一側(cè)的頂點，若存在一個匹配M使得這些頂點均被其覆蓋，則稱這些頂點構(gòu)成的集合V為G的一個可匹配集。規(guī)定空集是任意二分圖的一個可匹配集。

一條G中的M-交替路徑（M-Alternating Path of G）是指這樣一條路徑，其中的每一條邊交替地屬于或不屬于匹配M。一條G中的M-增廣路徑（M-Augmenting Path of G）是指這樣一條G中的M-交替路徑，其兩個端點均是沒有被M覆蓋的頂點。

對稱差（Symmetric Difference）是一種二元集合操作。兩個集合的對稱差是只屬于其中一個集合，而不屬于另一個集合的元素形成的集合。集合A和B的對稱差通常表示為A⊕B。根據(jù)定義，有A⊕B=（A-B）∪（B-A）=（A∪B）-（A∩B）。

一個擬陣是滿足下列條件的一個序?qū)?M=（S，L）：

1）S是一個有窮集合；

2）L是S的一個非空子集簇，即L是由S的子集作為元素構(gòu)成的集合，且非空；

3）如果B∈L，并且A包含于B，則有A屬于L。如果L滿足此性質(zhì)，則稱之為遺傳性；

4）如果A∈L，B∈L并且|B|>|A|，則有一定存在一個x∈B-A，使得集合A并上{x}之后形成的集合仍屬于L，該性質(zhì)稱為交換性。

2 二分圖可匹配集的擬陣性質(zhì)描述與證明

對于一個序?qū)G=（SG，LG），其中SG是某二分圖G一側(cè)的所有頂點形成的集合，即SG=X或SG=Y，LG是以所有該側(cè)的可匹配集為元素構(gòu)成的集合，我們證明MG是一個擬陣。

根據(jù)可匹配集的定義，MG滿足擬陣的1）2）兩個條件。由于匹配的子集依然是匹配，所以可匹配集的子集依然是可匹配集。MG滿足擬陣的條件3）。

我們現(xiàn)在證明條件4）。記X1，X2是G的兩個可匹配集且|X1|>|X2|，M1與M2分別是覆蓋了X1與X2的兩個匹配。根據(jù)文獻[1]，我們有如下引理。

引理 1. 令M、N是無向圖G=（V，E）的兩個匹配。G=（V，M⊕N）僅包含以下幾類連通分量：

1）孤立的點

2）包含偶數(shù)條邊的環(huán)，環(huán)中的每條邊交替地屬于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。

根據(jù)上述內(nèi)容，我們得出如下定理。

定理 1. 序?qū)G=（SG，LG）是一個擬陣。其中SG是某二分圖G一側(cè)的所有頂點形成的集合，LG是以所有該側(cè)的可匹配集為元素構(gòu)成的集合。

3 結(jié)束語

作為貪心算法的理論基礎(chǔ)，擬陣在計算機算法研究中有著重要的意義。證明二分圖可匹配集的擬陣性質(zhì)，有助于利用貪心算法解決其上的動態(tài)匹配問題[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.