2—连通三正则平面网络的结构

林馨

摘要：对任意简单图G的两条边ab，cd满足ac，bdE（G），令，该变换称为开关变换。若图G经过有限次开关变换后，变成图G，则称图G和图G在开关变换下是连通的。本文将2-连通三正则平面网络抽象为2-连通三正则平面图，讨论此图类的结构，并验证此图类在开关变换下是连通的。

关键词：三正则；2连通；平面；开关变换

中图分类号：O157.5 文献标识码：A 文章编号：1007-9416（2017）04-0095-01

1 引言

在组合网络理论中，网络拓扑结构可抽象为图。网络中的节点看做图中的顶点，网络中的连线看做图中的边。下面讨论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.