林馨

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

關鍵詞：三正則；2連通；平面；開關變換

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

1 引言

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

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

若圖G經過有限次開關變換后，變成圖G，則我們稱圖G和圖G在開關變換下是連通的。

2 主要結論

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

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

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

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

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

。

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

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

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

3 結語

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

參考文獻

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