無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)上的匹配與最大匹配數(shù)目

江 青 宇

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

0 引 言

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

復(fù)雜網(wǎng)絡(luò)上一類很重要的問(wèn)題就是復(fù)雜網(wǎng)絡(luò)上的計(jì)數(shù)問(wèn)題[1]。復(fù)雜網(wǎng)絡(luò)上計(jì)數(shù)問(wèn)題在很多領(lǐng)域都有著廣泛的應(yīng)用，其中比較典型的就是網(wǎng)絡(luò)的匹配問(wèn)題[2]。例如網(wǎng)絡(luò)匹配數(shù)和最大匹配的數(shù)目經(jīng)常被用在化學(xué)[3]中。研究發(fā)現(xiàn)，在頂點(diǎn)[4]或者邊[5]動(dòng)力學(xué)性質(zhì)的基礎(chǔ)上，最大匹配數(shù)和最小支配集是復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)可控性分析的重要工具[6]。在點(diǎn)動(dòng)力學(xué)的背景下，控制整個(gè)網(wǎng)絡(luò)最少驅(qū)動(dòng)頂點(diǎn)的數(shù)目和驅(qū)動(dòng)頂點(diǎn)集合可能的配置，分別由原始網(wǎng)絡(luò)派生出一個(gè)二分圖的匹配數(shù)和最大匹配的數(shù)目決定[4]。然而，在一般圖中求解最大匹配數(shù)是很困難的，甚至在二分圖上都是一個(gè)NP完全問(wèn)題[7]。在目前，復(fù)雜網(wǎng)絡(luò)上的匹配問(wèn)題仍然是科研人員積極研究的內(nèi)容[8]。

由于尋找網(wǎng)絡(luò)所有的匹配，特別是在一般圖上是難以做到的，因此本文對(duì)那些既在現(xiàn)實(shí)網(wǎng)絡(luò)中有重要意義，又能夠?qū)W(wǎng)絡(luò)上的匹配問(wèn)題進(jìn)行求解的圖給予了更多的關(guān)注[9]。在復(fù)雜網(wǎng)絡(luò)的研究中，Sierpiński網(wǎng)絡(luò)是一類有著重要研究意義的網(wǎng)絡(luò)[10]。本文研究的無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)可以更方便地研究一些真實(shí)網(wǎng)絡(luò)系統(tǒng)的復(fù)雜性，并且其具有更廣泛的適用性。例如，其可以運(yùn)用于調(diào)查城市導(dǎo)航的復(fù)雜性[11]；被頻繁地用于RNA折疊研究[12]；可被應(yīng)用于調(diào)查旅行商問(wèn)題的復(fù)雜性[14]。而且，將無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)與聚合物相聯(lián)系起來(lái)已被證明對(duì)于高分子物理的研究有很大幫助[13]。

針對(duì)以上問(wèn)題，無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的相關(guān)拓?fù)湫再|(zhì)的研究還是空白。本文主要研究無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)上的匹配問(wèn)題，包括無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的匹配數(shù)、邊覆蓋數(shù)、最大匹配的數(shù)目。本文利用無(wú)標(biāo)度Sierpinski的自相似性，計(jì)算出了無(wú)標(biāo)度Sierpinski網(wǎng)絡(luò)的匹配數(shù)。利用網(wǎng)絡(luò)的邊覆蓋數(shù)和匹配之間的關(guān)系，給出了無(wú)標(biāo)度Sierpinski網(wǎng)絡(luò)的邊覆蓋數(shù)的解析式。通過(guò)對(duì)無(wú)標(biāo)度Sierpinski網(wǎng)絡(luò)匹配的類型進(jìn)行分類，分析不同情況下匹配數(shù)目最大的情況下可能的網(wǎng)絡(luò)構(gòu)造方式，根據(jù)網(wǎng)絡(luò)迭代次數(shù)的奇偶性給出了最大匹配數(shù)目的遞推表達(dá)式。

1 網(wǎng)絡(luò)構(gòu)造與性質(zhì)

1.1 網(wǎng)絡(luò)的構(gòu)造

對(duì)于第n代無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)，當(dāng)n=0時(shí)，無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)I0為一個(gè)三個(gè)頂點(diǎn)構(gòu)成的三角形，當(dāng)n≥1時(shí)，記網(wǎng)絡(luò)最外層的3個(gè)頂點(diǎn)分別為A、B、C，那么無(wú)標(biāo)度Sierpiński可由下面的過(guò)程來(lái)迭代構(gòu)造：

(1) 將3個(gè)無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In-1，分別命名為In-1(i)，i=1,2,3,每個(gè)無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In-1的最外層3個(gè)頂點(diǎn)命名為Ai、Bi、Ci(i=1,2,3)，其中Ai、Bi、Ci分別對(duì)應(yīng)In-1(i)中的頂點(diǎn)A、B、C。

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

圖1表示了這樣的構(gòu)造過(guò)程。從上面的構(gòu)造方法可以知道，當(dāng)n≥1時(shí)，第n代無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In可以看成由三個(gè)前一代的無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In-1構(gòu)造而來(lái)，因而無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)有很好的自相似性。

圖1 無(wú)標(biāo)度Sierpinski網(wǎng)絡(luò)的構(gòu)造方法

1.2 網(wǎng)絡(luò)的性質(zhì)

令Vn和En分別表示第n代無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的總頂點(diǎn)數(shù)和總邊數(shù)，從上面的構(gòu)造方法容易得出以下關(guān)系：

Vn=3Vn-1-3

En=3En-1+3

解出步驟n中存在的頂點(diǎn)Vn和邊En的總數(shù)分別是：

文獻(xiàn)[15]給出了每一代無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的度分布Pcum(k)。通過(guò)每一次構(gòu)造時(shí)的規(guī)律，得出原來(lái)頂點(diǎn)和新產(chǎn)生頂點(diǎn)的度，進(jìn)而求得整個(gè)網(wǎng)絡(luò)In的度分布：

當(dāng)n趨向于無(wú)窮大時(shí)，可以得到：

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

與很多現(xiàn)實(shí)網(wǎng)絡(luò)一樣，無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的度分布指數(shù)也滿足冪率分布。

2 無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的匹配

2.1 匹配數(shù)目

定理2對(duì)于兩個(gè)相鄰階的無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In和In+1(n>1)，下面的關(guān)系式成立：

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

定理4無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In(n≥2)的匹配數(shù)為：

2.2 邊覆蓋數(shù)

邊覆蓋是一類邊的子集。對(duì)于無(wú)向連通圖G=(V,E)，集合V是其所有頂點(diǎn)的集合，集合E是其所有邊的集合。若E′?E，即圖G的每一個(gè)頂點(diǎn)在E′中都有邊與之關(guān)聯(lián)，那么稱E′為圖G的邊覆蓋集，簡(jiǎn)稱邊覆蓋。在所有邊覆蓋中，包含邊數(shù)最少的邊覆蓋稱為最小邊覆蓋，其所包含的邊數(shù)稱為邊覆蓋數(shù)。對(duì)于連通網(wǎng)絡(luò)上，最大匹配數(shù)與最小邊覆蓋數(shù)之和等于網(wǎng)絡(luò)頂點(diǎn)數(shù)。根據(jù)兩者之間的關(guān)系，結(jié)合上文求解到的匹配數(shù)，可以很容易地求出無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的邊覆蓋數(shù)。

定理5無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In的邊覆蓋數(shù)為：

定理5給出無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的邊覆蓋數(shù)，由于當(dāng)n是偶數(shù)時(shí)，結(jié)點(diǎn)數(shù)目為奇數(shù)無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)存在近完美匹配，因此只需在最大匹配的基礎(chǔ)上增加一條邊覆蓋唯一不在最大匹配中的頂點(diǎn)。當(dāng)n是奇數(shù)時(shí)無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)存在完美匹配，最大匹配數(shù)即為邊覆蓋數(shù)。

2.3 最大匹配的數(shù)目

令τn為無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In最大匹配的數(shù)目。為了求解τn，本文引入了三個(gè)輔助的量。令φn為無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In的最外層3個(gè)結(jié)點(diǎn)X、Y、Z均未覆蓋的最大匹配的數(shù)目。令θn為無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In覆蓋了頂點(diǎn)Z而未覆蓋頂點(diǎn)X、Y的最大匹配的數(shù)目，同時(shí)它也等于無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In覆蓋了頂點(diǎn)X而未覆蓋頂點(diǎn)Y、Z的最大匹配的數(shù)目，和無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In覆蓋了頂點(diǎn)Y而未覆蓋頂點(diǎn)X、Z的最大匹配的數(shù)目。令φn為無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In覆蓋了頂點(diǎn)X、Y而未覆蓋頂點(diǎn)Z的最大匹配的數(shù)目，同時(shí)它也等于無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In覆蓋了頂點(diǎn)Y、Z而未覆蓋頂點(diǎn)X的最大匹配的數(shù)目，和無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In覆蓋了頂點(diǎn)X、Z而未覆蓋頂點(diǎn)Y的最大匹配的數(shù)目。對(duì)于比較小的n，φn、θn、φn、τn都比較容易求解。例如，當(dāng)n=2時(shí)，φn=8、θn=112、φn=56、τn=1 392。但當(dāng)n繼續(xù)增大時(shí)，直接求解是比較困難的，所以本文給出了無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)最大匹配的數(shù)目的遞推關(guān)系式。

定理6對(duì)于無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)In，φn、θn、φn、τn可以依據(jù)下式遞推地表示，當(dāng)n為奇數(shù)時(shí)：

當(dāng)n為偶數(shù)時(shí)：

證明：在文中僅證明當(dāng)n為偶數(shù)時(shí)的第一個(gè)等式。

從定理6可以看出，無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)隨著結(jié)點(diǎn)總數(shù)奇偶不斷變化，最大匹配的組合情況也在不斷改變。

3 結(jié) 語(yǔ)

本文求解了無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的匹配數(shù)，利用無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)結(jié)構(gòu)上的規(guī)律，建立了匹配數(shù)的遞推關(guān)系，最后得到了匹配數(shù)的解析表達(dá)式，避免一般求解匹配數(shù)方法的高時(shí)間和空間復(fù)雜度。隨著無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)每一次的迭代構(gòu)建，網(wǎng)絡(luò)的結(jié)點(diǎn)總數(shù)也在奇偶交替變換，且當(dāng)網(wǎng)絡(luò)結(jié)點(diǎn)總數(shù)為偶數(shù)時(shí)，無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)存在完美匹配，邊覆蓋數(shù)等于匹配數(shù)；當(dāng)網(wǎng)絡(luò)結(jié)點(diǎn)總數(shù)為奇數(shù)時(shí)，無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)存在近完美匹配，邊覆蓋數(shù)等于匹配數(shù)加1。本文計(jì)算出匹配數(shù)最大時(shí)可能出現(xiàn)的子圖的組合情況，然后結(jié)合無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)，建立每種情況最大匹配數(shù)的遞推關(guān)系，最后得到了無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)最大匹配數(shù)的遞推關(guān)系式。本文采用的方法，不僅對(duì)無(wú)標(biāo)度Sierpiński網(wǎng)絡(luò)適用，對(duì)其他有自相似性質(zhì)網(wǎng)絡(luò)上的計(jì)數(shù)問(wèn)題也有重要的借鑒意義。