俞斌

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

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

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)語(yǔ)

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

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

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

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

1）S是一個(gè)有窮集合；

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

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

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

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

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

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

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

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

1）孤立的點(diǎn)

2）包含偶數(shù)條邊的環(huán)，環(huán)中的每條邊交替地屬于M-N及N-M

3）路徑，路徑中的每條邊交替地屬于M-N及N-M

證明：由于M與N均是G的匹配，因此V中的每個(gè)頂點(diǎn)至多與N-M中的一條邊相連，同時(shí)至多與M-N中的一條邊相連。

由于|X1|>|X2|，可知G=（V，M⊕N）中必然包含至少一個(gè)連通分量，其是一條G中的M2-增廣路徑。記G=（V， E）為其中一個(gè)連通分量，可得M2⊕E為G中的一個(gè)匹配，其覆蓋了X2中所有的頂點(diǎn)，且覆蓋了X1-X2中的某一個(gè)頂點(diǎn)。所以可得存在一個(gè)x∈X1-X2，使得X2∪{x}是一個(gè)可匹配集，即X2∪{x}∈LG。

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

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

3 結(jié)束語(yǔ)

作為貪心算法的理論基礎(chǔ)，擬陣在計(jì)算機(jī)算法研究中有著重要的意義。證明二分圖可匹配集的擬陣性質(zhì)，有助于利用貪心算法解決其上的動(dòng)態(tài)匹配問(wèn)題[2-3]。

參考文獻(xiàn)：

[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.