数事载本与度用
部分二连通三正则网络的结构
林馨
(福建师范大学数学与计算机科学学院福建州350007)
学术论坛
摘要:2-连通三正则网络是一类重要的网络结构。对任意一个简单图G，其两条独立的边ab，cd满足ac，bd多E（G），令 G(a,ord)=G-{ab,cd)+{ac,bd)，则该变模(a,b;c,d)称为开关变模。带图G经过有限次开关史换后，变成图G',则我们称图G和图G'在开关变模下是连通的。本丈通过将2-连通三正则网络指象为2-连通三正则图，讨论此类图的结构、验证它们在开关变换下是连通的并给出相应的算法。
关键词：三正则二连通开关变换
中图分类号：O157.5 1引言
文献标识码:A
本文涉及到的图论中常用符号和概念参见叫。
在组合网络理论中，网络拓扑结构可抽象为图。网络中的节点看做图中的顶点，网络中的连线看做图中的边。下面讨论部分2-连通三正则图的结构。
对任意简单图G的两条独立的边ab，cd满足ac,bdgE(G)，令 Galak>=G(ab,cd)+(ac,bd),则该变换o(a,b;c,d)称为对图G进行的一个开关变换"。此时，我们称G与G°在开关变换下是连通的。著图G经过有限次开关变换后，变成图G”，则我们称图G和函
G'在开关变换下是连通的。 2主要结论
3R
。由于图G为2-连
对任意n阶2-连通三正则网络G，IE(G)上
通，所以G中必存在哈密尔顿圈。我们将图上的顶点按次序编号为 V，V,.，V。圈上的边的集合记为E,(G)，不在图上的边的集合记为E,(G)。
定义1.记J为n阶2-连通三正则图的集合。
定理1.对VGeJ,任取两条满足条件的E,(G)中的边，做开关变换,则G°J。
证明，
显然有Ⅱ是偶数，令C为G中的哈密尔顿圈并记
V(C)= (v,.V....,V.)。
任取4个顶点V,V,,V,,V,满足v,V,eE,(G),v,VE,(G)，且VV,E(G),VVE(G),则做开关变换G"=G(yV,V,V) +(v,V,，VV)，则G°eJ，且C仍是G中的哈密尔顿圈。
定义2.我们定义标准2-连通三正则图G"：其哈密顿圈C上的顶点依次为V,V2,*+,V，E,(G")=E(C),E(G")(v.|f= 1,2.
E(G") = E,(G")UE,(G")
定理2.对VGeJ,若G￥G"，则对G进行有限次定理1中的开收稿日期：2016-05-30
文章编号:1007-9416(2016)08-0223-01
关变换之后可得到G"，且每次变换得到的图的哈密尔顿圈保持不变。
下面给出将G通过有限次定理1中的开关变换转化为标准2-连通三正则图G算法。
算法1.
Step 1.i:=1. Step 2. i<
=若，则转step3，否则，转step11. 2
VVEE,(G)
若，则转step4;否则转step5.
Step3.
+
Step 4. i:=i+1,转step 2.
Step 5.VE(G),若VEE(G),转step否则，转step 7.
G=G-vw.+fwyy.转step4.
Step 6.
+
Step 7.s:=i+1,转step 8.
+2
01a*6da特“()8as
Step 9.s:=s+1,转step 8. Step 10. V,v, E E,(G),
G:=G{vV,V,v}+(v,V,V,v),转step6. Step 11, G*:=G.
3结语
本文验证了在开关变换下，任意一个任意2一连通三正则图通过有限次开关变换都可以转化为标准图G*，再由开关变换的可逆性知整个2一连通三正则图类在开关变换下是连通的。此结论为进一步研
究此类网络结构提供了基础。参考文献
[1JJ.A Bondy and U.S.R Murty."graph theory with applications", 1st Edition, The MacMiilan Press,1976.
[2jN.Punnim,Decycling regular graphs, Australasian Journa1 of Combinatorics, 32(2005),1 47162.
作者简介：林馨(1981一),女,福建福州人,颈士学位，研究方向：图论及其应用。万方数据