舒 濤 (四川民族學(xué)院網(wǎng)絡(luò)信息中心，四川 康定 626001)

肖紅德 (中科方德軟件有限公司，北京 100190)

一種改進(jìn)的自補(bǔ)圖構(gòu)造方法

舒 濤 (四川民族學(xué)院網(wǎng)絡(luò)信息中心，四川 康定 626001)

肖紅德 (中科方德軟件有限公司，北京 100190)

現(xiàn)實(shí)世界中的交通網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)等網(wǎng)絡(luò)的模型構(gòu)建都可以用圖的構(gòu)造方法來(lái)實(shí)現(xiàn)，研究滿足某一性質(zhì)圖的構(gòu)造方法具有十分重要的意義。提出了一種采用自補(bǔ)圖標(biāo)準(zhǔn)型矩陣構(gòu)造自補(bǔ)圖的方法，并給出了具體實(shí)現(xiàn)算法。結(jié)果表明，利用該方法可以解決自補(bǔ)圖構(gòu)造過(guò)程中計(jì)算量過(guò)大的問(wèn)題。

自補(bǔ)圖；補(bǔ)圖；標(biāo)準(zhǔn)型矩陣；算法優(yōu)化

自補(bǔ)圖是一種具有與其補(bǔ)圖同構(gòu)的特殊圖，其計(jì)數(shù)問(wèn)題在文獻(xiàn)[1]中已有具體描述。而對(duì)于給定頂點(diǎn)數(shù)量時(shí)的所有不同構(gòu)自補(bǔ)圖的尋找問(wèn)題，當(dāng)頂點(diǎn)數(shù)為8和9的時(shí)候，很容易找到所有不同構(gòu)自補(bǔ)圖。實(shí)際上，要直接計(jì)算給定的2個(gè)圖是否同構(gòu)是一個(gè)非常困難問(wèn)題，因?yàn)槠溆?jì)算量隨著頂點(diǎn)規(guī)模的增加呈指數(shù)級(jí)增長(zhǎng)[2]。下面，筆者在自補(bǔ)圖計(jì)數(shù)理論[3]的基礎(chǔ)上，給出了標(biāo)準(zhǔn)型矩陣的定義，這為判斷一個(gè)圖是否為自補(bǔ)圖以及2個(gè)圖是否同構(gòu)提供了重要思路，并最終解決了同構(gòu)圖判定中計(jì)算量過(guò)大的問(wèn)題。

1 圖的標(biāo)準(zhǔn)型矩陣

圖矩陣的標(biāo)準(zhǔn)型定義如下[4-5]：用和頂點(diǎn)數(shù)相等的階數(shù)的方陣來(lái)表示自補(bǔ)圖，0表示2頂點(diǎn)間無(wú)邊相連，1表示2頂點(diǎn)間有邊相連，并且矩陣的行和列所代表的頂點(diǎn)按照主對(duì)角線對(duì)稱表示。把該矩陣的度序列按照由大到小的順序排列，且度序列相等的行(若把一行從左到右看成一個(gè)整數(shù)的話)排在前面的比排在后面的大(或小)，所有符合這樣的要求的矩陣中的最大(或最小)者。

上述定義的標(biāo)準(zhǔn)型矩陣為判斷一個(gè)圖是否為自補(bǔ)圖以及是否為不同構(gòu)的自補(bǔ)圖提供了方便。因?yàn)閷?duì)于一個(gè)給定的自補(bǔ)圖，由整數(shù)的良序性質(zhì)可知，其所對(duì)應(yīng)的標(biāo)準(zhǔn)型矩陣是唯一的，通過(guò)對(duì)其標(biāo)準(zhǔn)型矩陣進(jìn)行比較立即可以得出它們是否為不同構(gòu)的自補(bǔ)圖。另外，在判斷一個(gè)圖對(duì)應(yīng)的矩陣是否為自補(bǔ)圖的遍歷方面也提供了方便。依據(jù)上述標(biāo)準(zhǔn)，只需對(duì)所有度序列相等的結(jié)點(diǎn)的順序作全遍歷即可，則要大大減少了遍歷的次數(shù)，從而提高程序的執(zhí)行效率。

2 4n階和4n+1階自補(bǔ)圖的構(gòu)造

2.14n階自補(bǔ)圖的構(gòu)造

定理1一個(gè)單調(diào)遞減的圖序列π=(v1,v2,…,vp)是可自補(bǔ)度序列的充要條件π是相配的。

1)4n階可自補(bǔ)度序列的構(gòu)造 下面給出可自補(bǔ)度序列構(gòu)造的步驟：

2)4n階自補(bǔ)圖的構(gòu)造步驟 4n階自補(bǔ)圖的構(gòu)造包括2個(gè)步驟，具體內(nèi)容如下[6]。

Step1 構(gòu)造4n階的全部可自補(bǔ)度序列。

Step2 對(duì)每個(gè)可自補(bǔ)度序列，構(gòu)造出與其對(duì)應(yīng)的全部自補(bǔ)圖，可按下列步驟完成：

(1)對(duì)每個(gè)可自補(bǔ)度序列，構(gòu)造出與其對(duì)應(yīng)的全部H(G的度數(shù)較小的前2n個(gè)頂點(diǎn)的導(dǎo)出子圖)與H′(G的度數(shù)較大的后2n個(gè)頂點(diǎn)的導(dǎo)出子圖)。

2.24n+1階自補(bǔ)圖的構(gòu)造方法

定理4設(shè)G是一個(gè)4n+1階的自補(bǔ)圖，σ是G的一個(gè)自補(bǔ)置換，v∈V(G)且為σ的不動(dòng)點(diǎn)(即σ(v)=v)，則G-v是一個(gè)4n階的自補(bǔ)圖。

定理6設(shè)π*是一個(gè)4n維的可自補(bǔ)度序列，π是一個(gè)4n+1維的可自補(bǔ)度序列，并且π*可構(gòu)造出π，則π*對(duì)應(yīng)每個(gè)4n階的自補(bǔ)圖G*。通過(guò)增加一個(gè)度數(shù)為2n的頂點(diǎn)v與G*中的適當(dāng)2n個(gè)頂點(diǎn)相連邊，至少要產(chǎn)生一個(gè)4n+1階的、度序列為π的自補(bǔ)圖G。

應(yīng)用定理4、定理5、定理6可以構(gòu)造出所有4n+1階的自補(bǔ)圖，相關(guān)步驟如下。

Step1 按照4n階可自補(bǔ)度序列的構(gòu)造方法，從小到大求出4n+1維全部自補(bǔ)度序列。

Step2 寫(xiě)出全部4n階可自補(bǔ)度序列，并按從小到大進(jìn)行排列：

…

并且構(gòu)造出相應(yīng)的自補(bǔ)圖。

Step3 對(duì)于每一個(gè)4n+1階的可自補(bǔ)度序列π，構(gòu)造出它所對(duì)應(yīng)的所有自補(bǔ)圖，相關(guān)步驟如下：

3 自補(bǔ)圖的構(gòu)造算法

3.14n階自補(bǔ)圖的構(gòu)造算法

4n階自補(bǔ)圖的構(gòu)造算法包括7個(gè)步驟，具體內(nèi)容如下。

Step1 構(gòu)造出4n階自補(bǔ)圖的度序列。

Step2 把自補(bǔ)圖按照下列方法進(jìn)行分解：先將自補(bǔ)圖G的頂點(diǎn)按其度數(shù)的大小，從小到大進(jìn)行排列v1,v2,…,v2n,…,v4n,然后令H=G[v1,v2,…,v2n]( 即G的度數(shù)較小的前2n個(gè)頂點(diǎn)的導(dǎo)出子圖)，H′=G[v1,v2,…,v2n,…,v4n](即G的度數(shù)較大的后2n個(gè)頂點(diǎn)的導(dǎo)出子圖)，再令H*=G-E(H)-E(H′)，于是有G=H+H′+H*。

Step3 構(gòu)造H*(即所有2n階補(bǔ)圖，都為標(biāo)準(zhǔn)補(bǔ)圖產(chǎn)生的矩陣)。

Step5 根據(jù)已經(jīng)構(gòu)造出來(lái)的H、H′和H*判斷合起來(lái)的G是否為自補(bǔ)圖，方法如下：把G及其補(bǔ)都化為標(biāo)準(zhǔn)型，然后判斷其標(biāo)準(zhǔn)型是否相等，若相等，則可判斷其為自補(bǔ)圖，否則轉(zhuǎn)至Step4。

Step6 若Step5產(chǎn)生的G是自補(bǔ)圖，則將其加入到4n階自補(bǔ)圖的集合中去(若集合中存在該自補(bǔ)圖，則不做任何操作，否則將其加入到自補(bǔ)圖的集合中去)，轉(zhuǎn)至Step4。

Step7 程序結(jié)束運(yùn)行。

3.24n+1階自補(bǔ)圖的構(gòu)造算法

4n+1階自補(bǔ)圖的構(gòu)造算法包括9個(gè)步驟，具體內(nèi)容如下。

Step1 構(gòu)造4n+1階行向量，其中含有2n個(gè)1和2n+1個(gè)0。

Step2 從4n階自補(bǔ)圖表中取出一個(gè)自補(bǔ)圖。

Step3 把構(gòu)造的4n+1階行向量加入4n階自補(bǔ)圖的中間一行，并把4n+1階行向量的轉(zhuǎn)置加入到4n階自補(bǔ)圖的中間一列，構(gòu)成4n+1階矩陣。

Step4 把4n+1階矩陣轉(zhuǎn)換成標(biāo)準(zhǔn)型矩陣。

Step5 對(duì)標(biāo)準(zhǔn)型矩陣進(jìn)行取反操作，即除主對(duì)角線以外，都進(jìn)行取反操作(原來(lái)為1的變?yōu)?，原來(lái)為0的變?yōu)?)。

Step6 對(duì)Step5生成的4n+1階矩陣進(jìn)行標(biāo)準(zhǔn)化處理。

Step7 對(duì)Step4和Step6生成的矩陣進(jìn)行比較，如果2個(gè)矩陣相等，說(shuō)明該矩陣是4n+1階自補(bǔ)圖，轉(zhuǎn)至Step8；否則，說(shuō)明該矩陣不是4n+1階自補(bǔ)圖，轉(zhuǎn)至Step9。

Step8 判斷該4n+1階自補(bǔ)圖是否已經(jīng)在4n+1階自補(bǔ)圖表中，如果已經(jīng)存在，則不做任何操作，直接轉(zhuǎn)至Step9；否則，把該4n+1階自補(bǔ)圖寫(xiě)入4n+1階自補(bǔ)圖表中，再轉(zhuǎn)至Step9。

Step9 判斷4n階自補(bǔ)圖表是否已經(jīng)取完，如果沒(méi)有，則轉(zhuǎn)至Step2；否則，程序運(yùn)行結(jié)束。

3.3算法運(yùn)行結(jié)果

按照上述構(gòu)造算法編寫(xiě)的程序，通過(guò)分別構(gòu)造頂點(diǎn)數(shù)為8、9、12、13的不同構(gòu)自補(bǔ)圖，其得到的結(jié)果與理論計(jì)算一致。在硬件配置相同的計(jì)算機(jī)上，構(gòu)造出13個(gè)頂點(diǎn)的所有5600個(gè)不同構(gòu)自補(bǔ)圖，采用文獻(xiàn)[1]的方法編寫(xiě)的程序需要運(yùn)行8d，而采用上述算法編寫(xiě)的程序則只需要1d，大大提高了計(jì)算速度，縮短了構(gòu)造時(shí)間。

4 結(jié)語(yǔ)

自補(bǔ)圖作為一種具有與其補(bǔ)圖同構(gòu)性質(zhì)的特殊圖，計(jì)算量大一直是構(gòu)造自補(bǔ)圖的主要問(wèn)題。在分析前人給出的自補(bǔ)圖計(jì)數(shù)理論的基礎(chǔ)上，提出了一種通過(guò)構(gòu)造標(biāo)準(zhǔn)型矩陣來(lái)判斷一個(gè)圖是否為自補(bǔ)圖以及2個(gè)圖是否同構(gòu)的方法，采用該方法能夠在很大程度上解決同構(gòu)圖判定中計(jì)算量過(guò)大的問(wèn)題。今后，在構(gòu)造程序的設(shè)計(jì)上還應(yīng)繼續(xù)研究采用集群或利用GPU加速的方法以進(jìn)一步提高運(yùn)算速度。

[1]Read R C. On the number of self-complementary graphs and digraphs[J].Lond Math Soc，1963 (38)：99-104.

[2] 許進(jìn).自補(bǔ)圖理論及其應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2000.

[3]卜月華. 圖論及其應(yīng)用[M].南京：東南大學(xué)出版社，2000.

[4] 聶靈沼，丁石孫.代數(shù)學(xué)引論[M].第2版.北京：高等教育出版社，2000.

[5] 沈正梅. 探析同構(gòu)圖證明的新方法[J]. 常州工學(xué)院學(xué)報(bào), 2007，20(1)：27-29.

[6] 李鋒，李曉艷. 圖的同構(gòu)判定算法：關(guān)聯(lián)序列法及其應(yīng)用[J]. 復(fù)旦大學(xué)學(xué)報(bào)(自然科學(xué)版)，2001，40(3)：21-24.

[編輯] 李啟棟

O157.5；TP393

A

1673-1409(2013)22-0006-03

2013-05-14

四川省教育廳一般項(xiàng)目(12ZB086)。

舒濤(1980-)，男，碩士，講師，現(xiàn)主要從事計(jì)算機(jī)應(yīng)用、計(jì)算機(jī)網(wǎng)絡(luò)方面的教學(xué)與研究工作。