林馨

摘要：对任意的简单图G，若其存在两条边，满足，E（G），令，该变换称为图G上的开关变换。若图G经过有限次开关变换后，得到图G，则称G和G在开关变换下是连通的。本文将三正则二部网络抽象为三正则二部平面图，讨论此类图的结构，并用算法验证此图类在开关变换下是连通的。

关键词：三正则；二部；开关变换

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

1 引言

在图论中，图是由若干给定的顶点以及顶点之间的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用顶点代表事物，用连接两点的边表示相应两个事物间具有的关系。

在组合网络理论中，我们可将网络拓扑结构可抽象为图。其中，网络中的节点对应着图中的顶点，而网络中的连線则对应着图中的边。

图中，集合V的元素称为图G的顶点，而集合E的元素称为图G的边。

若图的各边都没有方向，称为无向图。

若图若无重边（即任意两个顶点间至多只有一条边），则称为简单图。

若图的每个顶点的度数（即其邻接的边数）皆为n，那么我们称其为n-正则图。

设G是无向图，如果顶点集V可分割成两个互不相交的子集，并且图中的每条边所关联的两个顶点分别属于这两个不同的顶点集，则称G是一个二部图。

本文将借助三正则二部图，研究三正则二部网络的结构。而文中所涉及的而以上未提及的图论中常用符号和概念参见[1]。

2 主要结论

对任意的简单图G，若其存在两条边，满足，E（G），令，那么该变换称为图G上的一次开关变换。……