部分二連通三正則網(wǎng)絡(luò)的結(jié)構(gòu)

林馨

摘要：2-連通三正則網(wǎng)絡(luò)是一類重要的網(wǎng)絡(luò)結(jié)構(gòu)。對(duì)任意一個(gè)簡(jiǎn)單圖G，其兩條獨(dú)立的邊ab，cd滿足ac，bdE（G），令，則該變換稱為開(kāi)關(guān)變換。若圖G經(jīng)過(guò)有限次開(kāi)關(guān)變換后，變成圖G，則我們稱圖G和圖G在開(kāi)關(guān)變換下是連通的。本文通過(guò)將2-連通三正則網(wǎng)絡(luò)抽象為2-連通三正則圖，討論此類圖的結(jié)構(gòu)、驗(yàn)證它們?cè)陂_(kāi)關(guān)變換下是連通的并給出相應(yīng)的算法。

關(guān)鍵詞：三正則 二連通 開(kāi)關(guān)變換

中圖分類號(hào)：O157.5 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）08-0223-01

1 引言

本文涉及到的圖論中常用符號(hào)和概念參見(jiàn)[1]。

在組合網(wǎng)絡(luò)理論中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可抽象為圖。網(wǎng)絡(luò)中的節(jié)點(diǎn)看做圖中的頂點(diǎn)，網(wǎng)絡(luò)中的連線看做圖中的邊。下面討論部分2-連通三正則圖的結(jié)構(gòu)。

對(duì)任意簡(jiǎn)單圖G的兩條獨(dú)立的邊ab，cd滿足ac，bdE（G），令，則該變換稱為對(duì)圖G進(jìn)行的一個(gè)開(kāi)關(guān)變換[2]。此時(shí)，我們稱G與在開(kāi)關(guān)變換下是連通的。若圖G經(jīng)過(guò)有限次開(kāi)關(guān)變換后，變成圖G，則我們稱圖G和圖G在開(kāi)關(guān)變換下是連通的。

2 主要結(jié)論

對(duì)任意n階2-連通三正則網(wǎng)絡(luò)G，。由于圖G為2-連通，所以G中必存在哈密爾頓圈。我們將圈上的頂點(diǎn)按次序編號(hào)為。圈上的邊的集合記為，不在圈上的邊的集合記為。

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

定理1.任取兩條滿足條件的中的邊，做開(kāi)關(guān)變換，則。

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

任取4個(gè)頂點(diǎn)滿足，且，則做開(kāi)關(guān)變換

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

定義2. 我們定義標(biāo)準(zhǔn)2-連通三正則圖：其哈密頓圈C上的頂點(diǎn)依次為，，

定理2.若，則對(duì)G進(jìn)行有限次定理1中的開(kāi)關(guān)變換之后可得到，且每次變換得到的圖的哈密爾頓圈保持不變。

下面給出將G通過(guò)有限次定理1中的開(kāi)關(guān)變換轉(zhuǎn)化為標(biāo)準(zhǔn)2-連通三正則圖算法。

3 結(jié)語(yǔ)

本文驗(yàn)證了在開(kāi)關(guān)變換下，任意一個(gè)任意2-連通三正則圖通過(guò)有限次開(kāi)關(guān)變換都可以轉(zhuǎn)化為標(biāo)準(zhǔn)圖G*，再由開(kāi)關(guān)變換的可逆性知整個(gè)2-連通三正則圖類在開(kāi)關(guān)變換下是連通的。此結(jié)論為進(jìn)一步研究此類網(wǎng)絡(luò)結(jié)構(gòu)提供了基礎(chǔ)。

參考文獻(xiàn)

[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.