一種改進的自補圖構(gòu)造方法

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

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

一種改進的自補圖構(gòu)造方法

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

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

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

自補圖；補圖；標準型矩陣；算法優(yōu)化

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

1 圖的標準型矩陣

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

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

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

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

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

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

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

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

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

(1)對每個可自補度序列，構(gòu)造出與其對應的全部H(G的度數(shù)較小的前2n個頂點的導出子圖)與H′(G的度數(shù)較大的后2n個頂點的導出子圖)。

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

定理4設G是一個4n+1階的自補圖，σ是G的一個自補置換，v∈V(G)且為σ的不動點(即σ(v)=v)，則G-v是一個4n階的自補圖。

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

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

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

Step2 寫出全部4n階可自補度序列，并按從小到大進行排列：

…

并且構(gòu)造出相應的自補圖。

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

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

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

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

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

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

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

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

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

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

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

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

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

Step2 從4n階自補圖表中取出一個自補圖。

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

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

Step5 對標準型矩陣進行取反操作，即除主對角線以外，都進行取反操作(原來為1的變?yōu)?，原來為0的變?yōu)?)。

Step6 對Step5生成的4n+1階矩陣進行標準化處理。

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

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

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

3.3算法運行結(jié)果

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

4 結(jié)語

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

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

[2] 許進.自補圖理論及其應用[M].西安：西安電子科技大學出版社，2000.

[3]卜月華. 圖論及其應用[M].南京：東南大學出版社，2000.

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

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

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

[編輯] 李啟棟

O157.5；TP393

A

1673-1409(2013)22-0006-03

2013-05-14

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

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