2—連通三正則平面網(wǎng)絡的結(jié)構(gòu)

林馨

摘要：對任意簡單圖G的兩條邊ab，cd滿足ac，bdE（G），令，該變換稱為開關(guān)變換。若圖G經(jīng)過有限次開關(guān)變換后，變成圖G，則稱圖G和圖G在開關(guān)變換下是連通的。本文將2-連通三正則平面網(wǎng)絡抽象為2-連通三正則平面圖，討論此圖類的結(jié)構(gòu)，并驗證此圖類在開關(guān)變換下是連通的。

關(guān)鍵詞：三正則；2連通；平面；開關(guān)變換

中圖分類號：O157.5 文獻標識碼：A 文章編號：1007-9416（2017）04-0095-01

1 引言

在組合網(wǎng)絡理論中，網(wǎng)絡拓撲結(jié)構(gòu)可抽象為圖。網(wǎng)絡中的節(jié)點看做圖中的頂點，網(wǎng)絡中的連線看做圖中的邊。下面討論2-連通三正則平面網(wǎng)絡（圖）的結(jié)構(gòu)。

對任意簡單圖G的兩條獨立的邊ab，cd滿足ac，bdE（G），令，則該變換稱為開關(guān)變換。

若圖G經(jīng)過有限次開關(guān)變換后，變成圖G，則我們稱圖G和圖G在開關(guān)變換下是連通的。

2 主要結(jié)論

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

對任意n階2-連通三正則平面網(wǎng)絡G，，G中必存在哈密爾頓圈C。將圈C上的頂點按次序編號為。我們給出圖G的一個平面嵌入，并記落在圈C內(nèi)的邊集記為，在圈C外的邊集記為。

定義1：記Jn為n階2-連通三正則平面圖集合。

類似地，時，也能使得中含情形1）中的子圖H。

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

。

定理2： 若，則對G進行有限次開關(guān)變換之后可得到，且每次變換得到的圖仍屬于Jn。

證： （1）容易驗證n=4和n=6時，結(jié)論成立。（2）則對可以對G實行定理1中的開關(guān)變換，使其含有子圖K，將K中的3圈收縮后，得到的圖。

綜上，由歸納法可知，若，則對G進行有限次開關(guān)變換之后可得到，且每次變換得到的圖仍屬于Jn。

3 結(jié)語

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

參考文獻

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