数事费本与度用
2－连通三正则平面网络的结构
林馨
(福建师范大学数学与计算机科学学院,福建福州350007)
应用研究
摘要:对任意简单图G的两条边ab,cd满定ac,bdeE(G),令G(ah)=G-{ab,cd)+{ac,bd),该变换α(a,b;c,d)称为开关变模。若图G经过有限次开关变换后，变成图G'"，则称图G和图G'在开关变换下是连通的。本文将2-连通三正削平面网络抽象为2-连通三正则平面图，讨论此图奠的结构，并验证此图类在开关变换下是连通的。
关键词：三正则；2连通；平面；开关变换
中图分类号：0157.5 1引言
文献标识码：A
在组合网络理论中，网络拓扑结构可抽象为图。网络中的节点看做图中的顶点，网络中的连线看做图中的边。下面讨论2一连通三正则平面网络(图)的结构。
对任意简单图G的两条独立的边ab,cd满足ac,bd多E(G)，令 Ge(ad)=Gtab,cd)+(ac,bd)，则该变换a(a,b;c,d)称为开关变换。
若图G经过有限次开关变换后，变成图G”，则我们称图G和图
G"在开关变换下是连通的。 2主要结论
以下涉及到的图论中常用符号和概念参见叫。
对任意n阶2一连通三正则平面网络G，，G中必存在哈密尔顿圈 C。将图C上的顶点按次序编号为，，"。我们给出图G的一个平面嵌人，并记落在图C内的边集记为E,(G)，在图C外的边集记为 E,(G)。
定义1：记J为n阶2-连通三正则平面图集合。定义2记K为以下图：V(K)=(,，4s， E(K) = (u,,,,,uMa,,u,ug)
定理1：对VGeJ，若G中不含子图K，则对G做开关变换α，使得G°中含子图K
证：(1)G中含子图H,其中V(H)=(u,42，,4s,， E(H) = (,,,,us,3
做变换G°=G(y,V,)+(v,V,),则G"J,且G"中含子图K。
(2)G中不含3图：
1)若G中含子图H，其中V(H)=(-"",,，
E(H)= (v-M,VMV-V,V, V+V , 且VV, E E,(G),V-I,,V+V EE,(G),
做变换G"=G(v-V,VV)+(V-W+,V,V), 则G°eJ,且G"中含子图K。
类似地，V,EE,(G),V-",,VEE,(G)时图G也能通过开关收稿日期：2017-04-06
文章编号:1007-9416(2017)04-0095-01 变换得到子图K。
2)若G中含子图H,其中(H)=(v,",3， E(H)= (v,VVVV+2,V-V,,V,M*,+2* ,
且v,V+2*, e E,(G),VV,VmVe E,(G), 做变换G"=G(v+2r,V+V*}+(v,VV/+2V, 则G°eJ,且G°中含情形1)中的子图H。
类似地，-,+,E,(G),,E(G)时,也能使得G"中含情形1)中的子图H。
定义3：标准2-连通三正则平面图G：其哈密顿图C上的顶点依次为V,V2.·,V
E(G")=E(C)U(M_,U(vV+2-,i =23...
定理2：对VGeJ.若G￥G"，则对G进行有限次开关变换之后可得到G，且每次变换得到的图仍属于J。。
证：(1)容易验证n=4和n=6时，结论成立。(2)则对VGeJ，可以对G实行定理1中的开关变换，使其含有子图K，将K中的3圈收缩后，得到的图G'eJ-t
综上，由归纳法可知，对VGeJ,,若G±G"，则对G进行有限次
开关变换之后可得到G"，且每次变换得到的图仍属于J。 3结语
本文验证了在开关变换下，任意一个2一连通三正则平面图通过有限次开关变换都可以转化为标准图G*，再由开关变换的可逆性知整个2一连通三正则平面图类在开关变换下是连通的。此结论为进
步研究各类网络结构提供了基础。参考文献
[1 JJ.A Bondy and U.S.R Murty."graph theory with applications", 1st Edition, The MacMillan Press,1976.
作者简介：林馨(1981一),女，福建福州人硕士，讲师，研究方向：图论及其应用。
95
万方数据