部分二連通三正則網絡的結構

林馨

摘要：2-連通三正則網絡是一類重要的網絡結構。對任意一個簡單圖G，其兩條獨立的邊ab，cd滿足ac，bdE（G），令，則該變換稱為開關變換。若圖G經過有限次開關變換后，變成圖G，則我們稱圖G和圖G在開關變換下是連通的。本文通過將2-連通三正則網絡抽象為2-連通三正則圖，討論此類圖的結構、驗證它們在開關變換下是連通的并給出相應的算法。

關鍵詞：三正則 二連通 開關變換

中圖分類號：O157.5 文獻標識碼：A 文章編號：1007-9416（2016）08-0223-01

1 引言

本文涉及到的圖論中常用符號和概念參見[1]。

在組合網絡理論中，網絡拓撲結構可抽象為圖。網絡中的節點看做圖中的頂點，網絡中的連線看做圖中的邊。下面討論部分2-連通三正則圖的結構。

對任意簡單圖G的兩條獨立的邊ab，cd滿足ac，bdE（G），令，則該變換稱為對圖G進行的一個開關變換[2]。此時，我們稱G與在開關變換下是連通的。若圖G經過有限次開關變換后，變成圖G，則我們稱圖G和圖G在開關變換下是連通的。

2 主要結論

對任意n階2-連通三正則網絡G，。由于圖G為2-連通，所以G中必存在哈密爾頓圈。我們將圈上的頂點按次序編號為。圈上的邊的集合記為，不在圈上的邊的集合記為。

定義1.記J為n階2-連通三正則圖的集合。

定理1.任取兩條滿足條件的中的邊，做開關變換，則。

證明. 顯然有n是偶數。令C為G中的哈密爾頓圈并記。

任取4個頂點滿足，且，則做開關變換

，則，且C仍是G中的哈密爾頓圈。

定義2. 我們定義標準2-連通三正則圖：其哈密頓圈C上的頂點依次為，，

定理2.若，則對G進行有限次定理1中的開關變換之后可得到，且每次變換得到的圖的哈密爾頓圈保持不變。

下面給出將G通過有限次定理1中的開關變換轉化為標準2-連通三正則圖算法。

3 結語

本文驗證了在開關變換下，任意一個任意2-連通三正則圖通過有限次開關變換都可以轉化為標準圖G*，再由開關變換的可逆性知整個2-連通三正則圖類在開關變換下是連通的。此結論為進一步研究此類網絡結構提供了基礎。

參考文獻

[1]J.A Bondy and U.S.R Murty，“graph theory with applications”， 1st Edition， The MacMillan Press，1976.

[2]N.Punnim，Decycling regular graphs， Australasian Journal of Combinatorics， 32（2005），147-162.