無標度Sierpiński網絡上的匹配與最大匹配數目

江 青 宇

(復旦大學計算機科學技術學院 上海 200433)

0 引 言

對于G=(V,E)表示的一個無向連通圖，集合V是其所有頂點的集合，集合E是其所有邊的集合。圖G的一個匹配M是邊集合E的一個子集，且在M中任意兩條邊都互不相鄰，即M中沒有兩條邊連接在一個相同的頂點上。一個頂點如果被匹配M中的一條邊連接，我們稱這個頂點被匹配M覆蓋。若圖G中沒有不同于M且所包含邊的數量多于M的匹配M′，就稱匹配M為圖G的一個最大匹配。匹配中兩種比較特殊的情況為：若圖G中的所有的頂點都被匹配M覆蓋，匹配M稱為圖G的一個完美匹配；若圖G中除一個頂點外的其余所有頂點都被匹配M覆蓋，匹配M稱為圖G的一個近完美匹配。圖G的最大匹配包含的邊數稱為圖G的匹配數。

復雜網絡上一類很重要的問題就是復雜網絡上的計數問題[1]。復雜網絡上計數問題在很多領域都有著廣泛的應用，其中比較典型的就是網絡的匹配問題[2]。例如網絡匹配數和最大匹配的數目經常被用在化學[3]中。研究發現，在頂點[4]或者邊[5]動力學性質的基礎上，最大匹配數和最小支配集是復雜網絡結構可控性分析的重要工具[6]。在點動力學的背景下，控制整個網絡最少驅動頂點的數目和驅動頂點集合可能的配置，分別由原始網絡派生出一個二分圖的匹配數和最大匹配的數目決定[4]。然而，在一般圖中求解最大匹配數是很困難的，甚至在二分圖上都是一個NP完全問題[7]。在目前，復雜網絡上的匹配問題仍然是科研人員積極研究的內容[8]。

由于尋找網絡所有的匹配，特別是在一般圖上是難以做到的，因此本文對那些既在現實網絡中有重要意義，又能夠對網絡上的匹配問題進行求解的圖給予了更多的關注[9]。在復雜網絡的研究中，Sierpiński網絡是一類有著重要研究意義的網絡[10]。本文研究的無標度Sierpiński網絡可以更方便地研究一些真實網絡系統的復雜性，并且其具有更廣泛的適用性。例如，其可以運用于調查城市導航的復雜性[11]；被頻繁地用于RNA折疊研究[12]；可被應用于調查旅行商問題的復雜性[14]。而且，將無標度Sierpiński網絡與聚合物相聯系起來已被證明對于高分子物理的研究有很大幫助[13]。

針對以上問題，無標度Sierpiński網絡的相關拓撲性質的研究還是空白。本文主要研究無標度Sierpiński網絡上的匹配問題，包括無標度Sierpiński網絡的匹配數、邊覆蓋數、最大匹配的數目。本文利用無標度Sierpinski的自相似性，計算出了無標度Sierpinski網絡的匹配數。利用網絡的邊覆蓋數和匹配之間的關系，給出了無標度Sierpinski網絡的邊覆蓋數的解析式。通過對無標度Sierpinski網絡匹配的類型進行分類，分析不同情況下匹配數目最大的情況下可能的網絡構造方式，根據網絡迭代次數的奇偶性給出了最大匹配數目的遞推表達式。

1 網絡構造與性質

1.1 網絡的構造

對于第n代無標度Sierpiński網絡，當n=0時，無標度Sierpiński網絡I0為一個三個頂點構成的三角形，當n≥1時，記網絡最外層的3個頂點分別為A、B、C，那么無標度Sierpiński可由下面的過程來迭代構造：

(1) 將3個無標度Sierpiński網絡In-1，分別命名為In-1(i)，i=1,2,3,每個無標度Sierpiński網絡In-1的最外層3個頂點命名為Ai、Bi、Ci(i=1,2,3)，其中Ai、Bi、Ci分別對應In-1(i)中的頂點A、B、C。

(2) 將A1和A3(或者B1和B2，C2和C3)合并為產生無標度Sierpiński網絡In的最外層頂點A(或者B,C)，而A2、B3、C1之間分別兩兩相連形成In中心的三角形。

圖1表示了這樣的構造過程。從上面的構造方法可以知道，當n≥1時，第n代無標度Sierpiński網絡In可以看成由三個前一代的無標度Sierpiński網絡In-1構造而來，因而無標度Sierpiński網絡有很好的自相似性。

圖1 無標度Sierpinski網絡的構造方法

1.2 網絡的性質

令Vn和En分別表示第n代無標度Sierpiński網絡的總頂點數和總邊數，從上面的構造方法容易得出以下關系：

Vn=3Vn-1-3

En=3En-1+3

解出步驟n中存在的頂點Vn和邊En的總數分別是：

文獻[15]給出了每一代無標度Sierpiński網絡的度分布Pcum(k)。通過每一次構造時的規律，得出原來頂點和新產生頂點的度，進而求得整個網絡In的度分布：

當n趨向于無窮大時，可以得到：

Pcum(k)=(k-2)-(ln3/ln2)

與很多現實網絡一樣，無標度Sierpiński網絡的度分布指數也滿足冪率分布。

2 無標度Sierpiński網絡的匹配

2.1 匹配數目

定理2對于兩個相鄰階的無標度Sierpiński網絡In和In+1(n>1)，下面的關系式成立：

圖2 In+1中所有中的匹配的布局

定理4無標度Sierpiński網絡In(n≥2)的匹配數為：

2.2 邊覆蓋數

邊覆蓋是一類邊的子集。對于無向連通圖G=(V,E)，集合V是其所有頂點的集合，集合E是其所有邊的集合。若E′?E，即圖G的每一個頂點在E′中都有邊與之關聯，那么稱E′為圖G的邊覆蓋集，簡稱邊覆蓋。在所有邊覆蓋中，包含邊數最少的邊覆蓋稱為最小邊覆蓋，其所包含的邊數稱為邊覆蓋數。對于連通網絡上，最大匹配數與最小邊覆蓋數之和等于網絡頂點數。根據兩者之間的關系，結合上文求解到的匹配數，可以很容易地求出無標度Sierpiński網絡的邊覆蓋數。

定理5無標度Sierpiński網絡In的邊覆蓋數為：

定理5給出無標度Sierpiński網絡的邊覆蓋數，由于當n是偶數時，結點數目為奇數無標度Sierpiński網絡存在近完美匹配，因此只需在最大匹配的基礎上增加一條邊覆蓋唯一不在最大匹配中的頂點。當n是奇數時無標度Sierpiński網絡存在完美匹配，最大匹配數即為邊覆蓋數。

2.3 最大匹配的數目

令τn為無標度Sierpiński網絡In最大匹配的數目。為了求解τn，本文引入了三個輔助的量。令φn為無標度Sierpiński網絡In的最外層3個結點X、Y、Z均未覆蓋的最大匹配的數目。令θn為無標度Sierpiński網絡In覆蓋了頂點Z而未覆蓋頂點X、Y的最大匹配的數目，同時它也等于無標度Sierpiński網絡In覆蓋了頂點X而未覆蓋頂點Y、Z的最大匹配的數目，和無標度Sierpiński網絡In覆蓋了頂點Y而未覆蓋頂點X、Z的最大匹配的數目。令φn為無標度Sierpiński網絡In覆蓋了頂點X、Y而未覆蓋頂點Z的最大匹配的數目，同時它也等于無標度Sierpiński網絡In覆蓋了頂點Y、Z而未覆蓋頂點X的最大匹配的數目，和無標度Sierpiński網絡In覆蓋了頂點X、Z而未覆蓋頂點Y的最大匹配的數目。對于比較小的n，φn、θn、φn、τn都比較容易求解。例如，當n=2時，φn=8、θn=112、φn=56、τn=1 392。但當n繼續增大時，直接求解是比較困難的，所以本文給出了無標度Sierpiński網絡最大匹配的數目的遞推關系式。

定理6對于無標度Sierpiński網絡In，φn、θn、φn、τn可以依據下式遞推地表示，當n為奇數時：

當n為偶數時：

證明：在文中僅證明當n為偶數時的第一個等式。

從定理6可以看出，無標度Sierpiński網絡隨著結點總數奇偶不斷變化，最大匹配的組合情況也在不斷改變。

3 結 語

本文求解了無標度Sierpiński網絡的匹配數，利用無標度Sierpiński網絡結構上的規律，建立了匹配數的遞推關系，最后得到了匹配數的解析表達式，避免一般求解匹配數方法的高時間和空間復雜度。隨著無標度Sierpiński網絡每一次的迭代構建，網絡的結點總數也在奇偶交替變換，且當網絡結點總數為偶數時，無標度Sierpiński網絡存在完美匹配，邊覆蓋數等于匹配數；當網絡結點總數為奇數時，無標度Sierpiński網絡存在近完美匹配，邊覆蓋數等于匹配數加1。本文計算出匹配數最大時可能出現的子圖的組合情況，然后結合無標度Sierpiński網絡的結構特點，建立每種情況最大匹配數的遞推關系，最后得到了無標度Sierpiński網絡最大匹配數的遞推關系式。本文采用的方法，不僅對無標度Sierpiński網絡適用，對其他有自相似性質網絡上的計數問題也有重要的借鑒意義。