部分二连通三正则网络的结构

林馨

摘要：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.