k次Petersen连通圈网络

k Times Petersen Connected Cycles Networks

摘要: 互连网络是超级计算机体系结构的重要组成部分。文中利用正则图连通圈网络模型，设计出了新模型k次Petersen连通圈网络PGCC(k)，它是3正则3连通的，且具有其他好的性质。本文对它的圈因子分解、Hamilton性和一些基本性质进行了研究，并证明了PGCC(1)可分解为边不交的两个等长圈和一个完美对集的并。

Abstract: Interconnected networks are an important part of supercomputer architecture. In the paper, using the regular graph connected circle network model, a new model kth Peterson connected circle network PGCC(k), which is 3-regular 3-connected and has many good properties, is designed. In this paper, we study its circle factorization, Hamiltonianity and some basic properties, and prove that PGCC(1) can be decomposed into two equal circles with non-intersecting edges and a perfect pairwise set of merges.

1. 引言

对于超级计算机来讲，互连网络是其非常重要的一部分，它一定程度上决定着超级计算机的性能。互连网络的结构和性质是超级计算机研究的一个重要课题，在设计和选择一个互连网络的拓扑结构时，它的哈密顿性、圈分解、连通度等指标对分析网络性能起着重要作用。我们在分析互连网络的拓扑结构时，一般都是将互连网络拓扑结构模型化为一个无向图，通过研究无向图的相关性质和特征来深入研究互连网络。互连网络拓扑的性能我们一般由图的性能和指标来衡量，如Hamilton性、嵌入性、圈因子分解、容错性、泛圈性等 [1] - [15] ，现如今已经研究提出的大多数互连网络参见 [1] - [15] 。

在图论研究中圈分解是非常重要的问题之一，通过分解可以深入揭示图的结构特征，并研究是否可以将给定的图分解成具有特殊结构的子图，不仅在图论中具有重要理论意义，而且还广泛应用于计算机等其他学科。图的分解问题在结构图论中是一个非常典型的问题，如何把一个图分解成路、圈、树或者具有某些特殊结构的子图，一直是图论中研究的热点问题 [1] [3] 。所以在设计和分析互连网络过程中，图论是运用的最基本和最强大的工具。

Petersen图一般译为彼得森图，是一个有趣的连通简单图，它一般画作五边形中包含有五角星的造型。Petersen图的同构多种多样，形态各异，共一百二十多种，然而它不是平面图，因此没有一种使得边与边没有交点。在大规模计算机并行系统中，互连网络在硬件成本、通信性能、高效算法和容错能力方面扮演着很重要的角色。在近些年以来，很多学者提出了一些有用的互连网络拓扑，本文是在师海忠的互连网络正则图连通圈网络模型的思想基础之上，进一步探究提出了k次Petersen连通圈网络模型，并对该网络进行了初步的探究。k次Petersen连通圈网络在互连网络拓扑中，是一类非常重要的网络拓扑结构，由于它具有很多好的性质，如正则性、嵌入性、连通性等等各种性质，从而为我们设计大规模超级计算机系统和互连网络的优化提供了一定的理论参考。

2. 基本概念

定义1 [3] [5] ：图G是一点边连续交替出现的序列 $w=v_0{e}_1{v}_1{e}_2{v}_2\cdots e_n{v}_n$ 称为图G的一个途径，其中 $v_0$ 、 $v_n$ 分别称为途径的起点和终点，w上其余顶点称为中途点，图G中边不重复出现的途径称为迹。图G中起点和终点相同的途径称为闭途径，边不重复出现的闭途径称为闭迹(也称为回路)。中途点不重复的闭途径称为圈。包含图G的每个顶点的圈称为图G的Hamilton圈，具有Hamilton圈的图称为Hamilton图。

定义2 [3] [5] ：设M是E的一个子集，它的元素是G中连杆，并且这些连杆中的任意两个在G中均不相邻，则称M为G的对集(或匹配)；M中一条边的两个端点称为在M下是配对的。若对集M的某条边与顶点v关联，则称M饱和顶点v，并且称v是M饱和的，否则称v是M非饱和的，若G的每个顶点均为M饱和的，则称M为G的完美对集。

定义3 [3] [5] ：图G中与一个顶点 $v_i$ 相关联的边的数目叫做顶点 $v_i$ 的度，记作 $d\left(v_i\right)$ 或 $\mathrm{deg}\left(v_i\right)$ ，图G中所有顶点中最小的度记作 $\delta \left(G\right)=\min \left\{d\left(v\right)|v\in V\left(G\right)\right\}$ ，最大的度记作 $\Delta \left(G\right)=\max \left\{d\left(v\right)|v\in V\left(G\right)\right\}$ 。如果 $\delta \left(G\right)=\Delta \left(G\right)=k$ ，则图G中所有顶点的度相等，这时称图G是k正则的。

定义4 [5] ：设G是正则图， $E\left(G\right)$ 是G的边集，我们称G是Hamilton可分解的，如果：

要么(1) $d\left(G\right)=2k$ 且 $E\left(G\right)$ 能被划分成k个边不交的Hamilton圈；

要么(2) $d\left(G\right)=2k+1$ 且 $E\left(G\right)$ 能被划分成k个边不交的Hamilton圈和一个完美对集。

定义5 [5] ：图G的一个k正则生成图，称为G的一个k因子，若图G可表示为若干个k因子的和，则称图G是k因子可分解的。当 $k=2$ 时，图G的2因子分解也称为圈因子分解，若图G是2因子可分解的，表示G可以分解为若干个圈的并。

定义6 [5] ：若图G是非H图，但对于G中任意点V，都有 $G-V$ 是Hamilton图，则称G为是超H图。

定义7：将Petersen连通圈网络中的每一个顶点用一个3长的圈代替，得到的新网络称为1次Petersen连通圈网络，记为PGCC(1)。再将PGCC(1)中的每个顶点用一个3长的圈代替，得到的新网络称为2次Petersen连通圈网络，记为PGCC(2)。依次类推代替k次之后，得到的新网络我们称之为k次Petersen连通圈网络，记为PGCC(k)。

3. 主要结果

3.1. Petersen图连通圈网络

为了方便起见，我们将Petersen图用PGCC(0)表示，如图1。

引理1 [2] [5] ：Petersen图不是Hamilton图。

引理2 [5] ：Petersen图是超Hamilton图。

引理3 [5] ：Petersen图中存在Hamilton路，共有240条。

引理4 [3] [5] ：Petersen图的同构图共有120多种，常见的9种如图2~10：

Figure 1. Petersen graph

图1. Petersen图

Figure 2. Isomorphisms of Petersen graph (1)

图2. Petersen图的同构图(1)

Figure 3. Isomorphisms of Petersen graph (2)

图3. Petersen图的同构图(2)

Figure 4. Isomorphisms of Petersen graph (3)

图4. Petersen图的同构图(3)

Figure 5. Isomorphisms of Petersen graph (4)

图5. Petersen图的同构图(4)

Figure 6. Isomorphisms of Petersen graph (5)

图6. Petersen图的同构图(5)

定理1：Petersen连通圈网络PGCC(1)的基本性质：

(1) PGCC(0)是非平面图；

(2) PGCC(0)是旋转对称的，是轴对称图；

(3) PGCC(0)的顶点数 $V=10$ ，边数 $e=15$ ，分支数 $\omega =1$ ；

(4) PGCC(0)是3-正则图3-连通图；

(5) PGCC(0)的围长 $g\left(\text{PGCC}\left(0\right)\right)=5$ ，周长 $c\left(\text{PGCC}\left(0\right)\right)=9$ ；

(6) PGCC(0)的直径 $d\left(\text{PGCC}\left(0\right)\right)=2$ ；

(7) PGCC(0)是三部图；

(8) PGCC(0)是Hamilton图，非欧拉图；

(9) PGCC(0)的补图是6正则图；

(10) PGCC(0)的连通度 $k\left(\text{PGCC}\left(0\right)\right)=3$ ，边连通度 $\lambda \left(\text{PGCC}\left(0\right)\right)=4$ 。

证明：以上性质从Petersen图中可以观察得到。其中性质(9)是因为Petersen图是3-正则图，而Petersen图对应的完全图是9-正则的，故它的补图是6-正则的。

定理2：Petersen连通圈网络PGCC(0)中存在恰为2-圈的圈因子。

证明：PGCC(0) 2-圈的圈因子为两个5长的圈，分别为：

C₅：1-2-3-4-5-1；C₅：6-8-10-7-9-6。

Figure 7. Isomorphisms of Petersen graph (6)

图7. Petersen图的同构图(6)

Figure 8. Isomorphisms of Petersen graph (7)

图8. Petersen图的同构图(7)

Figure 9. Isomorphisms of Petersen graph (8)

图9. Petersen图的同构图(8)

Figure 10. Isomorphisms of Petersen graph (9)

图10. Petersen图的同构图(9)

定理3：Petersen连通圈网络PGCC(0)可分解为边不交的两个5长圈和一个完美对集的并。

证明：两个5长的圈 $C_5,C_5$ 和一个完美对集M，如下：

C₅：1-2-3-4-5-1；C₅：6-8-10-7-9-6；M：1-7；2-8；3-9；4-10；5-6。

3.2. k次Petersen连通圈网络PGCC(k)

定理4：PGCC(k)不是Hamilton图，但存在Hamilton路。

证明：由引理3知，Petersen图中存在Hamilton路，再由PGCC(k)的定义可知，PGCC(k)中存在Hamilton路。

定理5：PGCC(1)中存在恰为 $k\left(k=2,3,6,10\right)$ 圈的圈因子。

Figure 11. PGCC(1)

图11. 1次Petersen连通圈网络

证明：PGCC(1)如图11所示。在1次Petersen连通圈网络PGCC(1)中，我们能够找到2圈的圈因子 $\left(C_{15},C_{15}\right)$ 为：

C₁₅：(1,1)-(1,2)-(1,3)-(7,1)-(7,3)-(7,2)-(9,3)-(9,1)-(9,2)-(6,3)-(6,2)-(6,1)-(5,3)-(5,1)-(5,2)-(1,1)；

C₁₅：(2,3)-(2,1)-(2,2)-(3,1)-(3,3)-(3,2)-(4,1)-(4,2)-(4,3)-(10,1)-(10,2)-(10,3)-(8,2)-(8,3)-(8,1)-(2,3)。

3圈的圈因子 $\left(C_3,C_3,C_{24}\right)$ 为：

C₃：(8,1)-(8,2)-(8,3)-(8,1)；

C₃：(10,1)-(10,2)-(10,3)-(10,1)；

C₂₄：(1,1)-(1,2)-(2,1)-(2,3)-(2,2)-(3,1)-(3,3)-(3,2)-(4,1)-(4,3)-(4,2)-(5,1)-(5,2)-(5,3)-(6,1)-(6,2)-(6,3)-(9,2)-(9,1)-(9,3)-(7,2)-(7,3)-(7,1)-(1,3)-(1,1)。

6圈的圈因子 $\left(C_3,C_3,C_3,C_3,C_3,C_{15}\right)$ 为：

5个C₃为： $\left(i,1\right)\text{-}\left(i,2\right)\text{-}\left(i,3\right)\text{-}\left(i,1\right),\left(i=6,7,8,9,10\right)$ ；

C₁₅：(1,1)-(1,3)-(1,2)-(2,1)-(2,3)-(2,2)-(3,1)-(3,3)-(3,2)-(4,1)-(4,3)-(4,2)-(5,1)-(5,3)-(5,2)-(1,1)。

10圈的圈因子(10个C₃)为：

10个C₃： $\left(i,1\right)\text{-}\left(i,2\right)\text{-}\left(i,3\right)\text{-}\left(i,1\right),\left(i=1,2,3,\cdots ,10\right)$ 。

定理6：1次Petersen连通圈网络PGCC(1)可分解为边不相交的2个等长的15圈和1个完美对集的并。

证明：如图11，两个15长的圈和一个完美对集分别为：

C₁₅：(1,1)-(1,3)-(1,2)-(2,1)-(2,3)-(2,2)-(3,1)-(3,3)-(3,2)-(4,1)-(4,3)-(4,2)-(5,1)-(5,3)-(5,2)-(1,1)；

C₁₅：(6,1)-(6,2)-(8,3)-(8,1)-(8,2)-(10,3)-(10,1)-(10,2)-(7,3)-(7,1)-(7,2)-(9,3)-(9,1)-(9,2)-(6,3)-(6,1)；

M：(1,1)-(1,2)；(2,1)-(2,2)；(3,1)-(3,2)；(4,1)-(4,2)；(5,1)-(5,2)；

(1,3)-(7,1)；(2,3)-(8,1)；(3,3)-(9,1)；(4,3)-(10,1)；(5,3)-(6,1)；

(6,2)-(6,3)；(7,2)-(7,3)；(8,2)-(8,3)；(9,2)-(9,3)；(10,2)-(10,3)。

定理7：PGCC(k)的基本性质：

(1) PGCC(k)有 $10\times 3^k$ 个顶点，有 $15\times 3^k$ 条边；

(2) PGCC(k)是3正则3连通的；

(3) PGCC(k)的连通度 $k\left(\text{PGCC}\left(k\right)\right)=3$ ，边连通度 $\lambda \left(\text{PGCC}\left(k\right)\right)=4$ ；

(4) PGCC(k)非平面图；

(5) PGCC(k)是轴对称图。

证明：1) 因为Petersen图PGCC(0)中有10个顶点，15条边，根据PGCC(k)的定义，可知PGCC(k)有 $10\times 3^k$ 个顶点，有 $15\times 3^k$ 条边；

2) 因为PGCC(0)是3正则的，由PGCC(k)的定义可知，在k变化的过程中并不改变PGCC(k)顶点的度数，所以PGCC(k)的每个顶点度数都是3，故PGCC(k)是3正则的。再由性质(4)知，PGCC(k)的连通度 $k\left(\text{PGCC}\left(k\right)\right)=3$ ，故PGCC(k)是3正则3连通的；

3) PGCC(k)的连通度 $k\left(\text{PGCC}\left(k\right)\right)$ 表示PGCC(k)所具有的k顶点割中最小的k，即顶点割中顶点个数最少为k。而PGCC(k)是3正则图，故最小顶点割中元素至少为3个，所以 $k\left(\text{PGCC}\left(k\right)\right)=3$ 。在正则图中，一般边连通度 $\lambda$ 与点连通度k有关系式 $\lambda =2k-2$ 成立，故 $\lambda \left(\text{PGCC}\left(k\right)\right)=2\times 3-2=4$ 。

4) 由欧拉公式可以证明该结论。或者根据定理1知，Petersen图PGCC(0)是非平面图，而PGCC(k)是由Petersen图中的每个顶点用一个3长的圈依次代替k次之后得到的，一个非平面图中的每个顶点被依次代替k次之后依然是非平面图，故PGCC(k)也是非平面图。

5) 由定理1知，Petersen图PGCC(0)是轴对称图。再根据PGCC(k)的定义，PGCC(k)是由Petersen图中的每个顶点用一个3长的圈依次代替k次之后得到的，故PGCC(k)保留了Petersen图PGCC(0)是轴对称性，所以PGCC(k)也是轴对称图。

4. 结束语

本文在图的基础上，设计出了新网络模型——k次Petersen连通圈网络，并对它许多好的性质：如Hamilton性、圈因子分解、直径、连通度、容错性、正则性等进行了具体研究。在国家现代信息化发展过程中，必然对互连网络的要求越来越高，尤其是信息传输和连通性等方面。比如在网络通讯应用上，当需要增加网络基站或者网络节点时，我们就可以利用连通圈网络具有的连通性、嵌入性和圈因子分解性等好的特殊性质，去解决当有多个信息传输时涉及分解的问题和需要在原有互连网络体系结构中增加节点的问题，以此来减少互连网络体系的建设成本。这样不但能够有效解决网络结构设计中存在硬件成本过高的难题，更能为网络的通信性能、可靠性、独立性、高效算法和容错能力等方面提供有效的理论保障。因此连通圈网络在大规模计算机并行系统中扮演着重要的角色，为超大规模计算机体系结构和互连网络拓扑的优化设计提供了很好的理论参考。

本文对该网络的研究只是一个开始，关于该网络其他更好的性质，比如泛圈性等，以及在互连网络建设中更多的实际应用，还有待于我们更进一步地探究，来拓宽对该网络的认识。