一種改進的自補圖構造方法

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

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

一種改進的自補圖構造方法

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

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

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

自補圖；補圖；標準型矩陣；算法優化

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

1 圖的標準型矩陣

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

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

2 4n階和4n+1階自補圖的構造

2.14n階自補圖的構造

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

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

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

Step1 構造4n階的全部可自補度序列。

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

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

2.24n+1階自補圖的構造方法

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

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

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

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

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

…

并且構造出相應的自補圖。

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

3 自補圖的構造算法

3.14n階自補圖的構造算法

4n階自補圖的構造算法包括7個步驟，具體內容如下。

Step1 構造出4n階自補圖的度序列。

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

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

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

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

Step7 程序結束運行。

3.24n+1階自補圖的構造算法

4n+1階自補圖的構造算法包括9個步驟，具體內容如下。

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

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

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

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

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

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

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

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

Step9 判斷4n階自補圖表是否已經取完，如果沒有，則轉至Step2；否則，程序運行結束。

3.3算法運行結果

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

4 結語

自補圖作為一種具有與其補圖同構性質的特殊圖，計算量大一直是構造自補圖的主要問題。在分析前人給出的自補圖計數理論的基礎上，提出了一種通過構造標準型矩陣來判斷一個圖是否為自補圖以及2個圖是否同構的方法，采用該方法能夠在很大程度上解決同構圖判定中計算量過大的問題。今后，在構造程序的設計上還應繼續研究采用集群或利用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] 聶靈沼，丁石孫.代數學引論[M].第2版.北京：高等教育出版社，2000.

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

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

[編輯] 李啟棟

O157.5；TP393

A

1673-1409(2013)22-0006-03

2013-05-14

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

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