k次十二面体–师连通圈网络 K Dodecahedron-Shi Connected Cycles Networks

doi:10.12677/CSA.2018.86113

Computer Science and Application
Vol.08 No.06(2018), Article ID:25672,14 pages
10.12677/CSA.2018.86113

K Dodecahedron-Shi Connected Cycles Networks

Haizhong Shi, Zhicheng Zhang

●How to Cite this Article

College of Mathematics and Statistics, Northwest Normal University, Lanzhou Gansu

Received: Jun. 7^th, 2018; accepted: Jun. 22^nd, 2018; published: Jun. 29^th, 2018

ABSTRACT

An interconnection network is an important part of a supercomputer. On chip interconnection network is one of the hot topics in current research. A class of important interconnection network of the K dodecahedron-Shi connected cycle network is a new network model based on the regular graph connected cycle network model of the internet in 2010. It is obtained by replacing each vertex of a dodecahedron connected cycle network with triangle K times, and it is recorded as DSCC(k). It is a 3-regular and 3-connected plane graph, and has many good properties. In this paper, a series of conjectures about the network are proposed, such as the conjecture 1: K dodecahedron-Shi connected cycle network is a Hamilton graph, and the conjectures 1, 2, and 3 are proved strictly. The author also uses the Descartes product method of graphs to construct a new Descartes product interconnected DSCC(k)xK₂ and DSCC(k)xC_m, and study their properties.

Keywords:Interconnection Network, Dodecahedron Connected Cycle Network, Hamilton Graph, Cartesian Product Interconnection Network

k次十二面体–师连通圈网络

师海忠，张治成

西北师范大学数学与统计学院，甘肃兰州

收稿日期：2018年6月7日；录用日期：2018年6月22日；发布日期：2018年6月29日

摘要

互连网络是超级计算机的重要组成部分，片上互连网络是当前研究的热点课题之一。k次十二面体–师连通圈网络是一类重要的互连网络，是在2010年师海忠提出互联网络的正则图连通圈网络模型的基础上设计的新网络模型。它是将十二面体连通圈网络的每个顶点用三角形代替k次得到的，记为DSCC(k)，它是3正则3连通的平面图，且有许多好的性质。文中提出了关于该网络的一系列猜想，如猜想1：k次十二面体–师连通圈网络是Hamilton图，对猜想1、2、3作了严格的证明。作者还利用图的笛卡尔乘积方法构建了新的笛卡尔乘积互连网络DSCC(k)xK₂和DSCC(k)xC_m，并对其性质进行了研究。

关键词 :互连网络，十二面体连通圈网络，Hamilton图，笛卡尔乘积网络

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

互连网络是超级计算机的重要组成部分，它的性能在某种程度上决定着超级计算机的性能。片上互连网络是当前研究的热点课题之一，互连网络通常被模型化为一个图，图的结点对应处理机，图的边对应处理机间的通信信道。各种已有的互连网络参见 [1] [2] [3] [5] - [10] 。2010年，在中国运筹学大会上，师海忠提出了互连网络的正则图连通圈网络模型，设计出了多种互连网络，并提出了一系列猜想 [1] 。在此基础上，师海忠又进一步提出了k次十二面体–师连通圈网络 $D S C C (k)$ 和笛卡尔乘积网络 $D S C C (k) \times K_{2}$ 、 $D S C C (k) \times C_{m}$ ，并提出如下猜想：

猜想1：k次十二面体–师连通圈网络是Hamilton图。

猜想2：任何一个3正则3连通的Hamilton图，每个顶点用一个三角形代替后得到的图一定是Hamilton图。

猜想3：一个3正则3连通平面图的每个顶点用一个三角形来代替得到的图是Hamilton图，则原图是Hamilton图。

猜想4： $D S C C (k) \times K_{2}$ 是边不交的2个Hamilton圈的并。

猜想5： $D S C C (k) \times C_{m}$ 是边不交的2个Hamilton圈和一个完美对集的并。

2. 基本概念

定义1 [4] ：图G是一点边连续交替出现的序列， $w = v_{0} e_{1} v_{1} e_{2} v_{2} \dots e_{n} v_{n}$ 称为图G的一个途径，其中分别称为途径的起点和终点，w上其余顶点称为中途点，图G中边不重复出现的途径称为迹。图G中起点和终点相同的途径称为闭途径，边不重复出现的闭途径称为闭迹(也称为回路)。中途点不重复的闭途径称为圈。

定义2 [4] ：包含图G的每个顶点的圈称为图G的Hamilton圈，具有Hamilton圈的图称为Hamilton图。

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

定义4：将十二面体连通圈网络中的每个顶点用一个三角形代替，所得到的新网络叫做1次十二面体-师连通圈网络，记为 $D S C C (1)$ ；然后再将1次十二面体–师连通圈网络中的每个顶点用一个三角形代替，得到的新网络叫做2次十二面体-师连通圈网络，记为 $D S C C (2)$ ；依次代替k次，得到的新网络叫做k次十二面体–师连通圈网络，记为 $D S C C (k)$ 。

定义5 [2] ：设 $G_{1} = (V_{1}, E_{1})$ 和 $G_{2} = (V_{2}, E_{2})$ 是两个无向图， $G_{1}$ 和 $G_{2}$ 的笛卡尔乘积是无向图，记为 $G_{1} \times G_{2}$ 。其中 $V (G_{1} \times G_{2}) = V_{1} \times V_{2} = {(v_{1}, v_{2}) | v_{1} \in V_{1} 且 v_{2} \in V_{2}}$ ，存在一条顶点 $x_{1} x_{2}$ 与顶点 $y_{1} y_{2}$ 之间的边(其中 $x_{1}, y_{1} \in V (G_{1}), x_{2}, y_{2} \in V (G_{2})$ )当且仅当或者 $x_{1} = y_{1}$ 且 $x_{2} y_{2} \in E (G_{2})$ ，或者 $x_{2} = y_{2}$ 且 $x_{1} y_{1} \in E (G_{1})$ 。类似，可以定义笛卡尔乘积 $G_{1} \times G_{2} \times \dots \times G_{n}$ 。

定义6：将k次十二面体–师连通圈网络 $D S C C (k)$ 与 $K_{2}$ 作笛卡尔乘积生成的新网络记为 $D S C C (k) \times K_{2}$ 。k次十二面体–师连通圈网络 $D S C C (k)$ 与一个长度为m的圈 $C_{m}$ 作笛卡尔乘积生成的新网络，我们记为 $D S C C (k) \times C_{m}$ $(k = 0, 1, 2, \dots, m = 3, 4, \dots)$ 。

3. 主要结果

3.1. k次十二面体–师连通圈网络

引理1 [4] ：十二面体DH是Hamilton图。

如图1、图2所示。

Figure 1. Dodecahedron DH

图1. 十二面体DH

Figure 2. The ring representation of dodecahedron DH

图2. 十二面体DH的圈表示

Hamilton圈为：1-8-9-18-19-20-16-17-7-6-15-14-13-12-11-10-2-3-4-5-1。

为了统一起见，我们用 $D S C C (0)$ 表示十二面体DH。

定理1 1次十二面体–师连通圈网络 $D S C C (1)$ 是Hamilton图。

证明：如图3、图4所示。

Figure 3. DSCC(1)

图3. DSCC(1)

Figure 4. The ring representation of DSCC(1)

图4. DSCC(1)的圈表示

由图3、图4可知，Hamilton圈为：

(1,1)-(1,3)-(1,2)-(8,1)-(8,2)-(8,3)-(9,1)-(9,3)-(9,2)-(18,1)-(18,2)-(18,3)-(19,1)-(19,3)-(19,2)-(20,1)-(20,3)-(20,2)-(16,1)-(16,3)-(16,2)-(17,1)-(17,2)-(17,3)-(7,1)-(7,2)-(7,3)-(6,1)-(6,2)-(6,3)-(15,1)-(15,3)-(15,2)-(14,1)-(14,2)-(14,3)-(13,1)-(13,3)-(13,2)-(12,1)-(12,2)-(12,3)-(11,1)-(11,3)-(11,2)-(10,1)-(10,3)-(10,2)-(2,1)-(2,3)-(2,2)-(3,1)-(3,2)-(3,3)-(4,1)-(4,2)-(4,3)-(5,1)-(5,2)-(5,3)-(1,1)。

由此可知，1次十二面体–师连通圈网络 $D S C C (1)$ 是Hamilton图。

定理2：2次十二面体–师连通圈网络 $D S C C (2)$ 是Hamilton图。

证明：如图5、图6所示。

由图5、图6可知，Hamilton圈为：

(1,1,1)-(1,1,2)-(1,1,3)-(1,3,1)-(1,3,3)-(1,3,2)-(1,2,1)-(1,2,2)-(1,2,3)-(8,1,1)-(8,1,3)-(8,1,2)-(8,2,1)-(8,2,2)-(8,2,3)-(8,3,1)-(8,3,3)-(8,3,2)-(9,1,1)-(9,1,2)-(9,1,3)-(9,3,1)-(9,3,3)-(9,3,2)-(9,2,1)-(9,2,2)-(9,2,3)-(18,1,1)-(18,1,3)-(18,1,2)-(18,2,1)-(18,2,2)-(18,2,3)-(18,3,1)-(18,3,3)-(18,3,2)-(19,1,1)-(19,1,2)-(19,1,3)-(19,3,1)-(19,3,3)-(19,3,2)-(19,2,1)-(19,2,2)-(19,2,3)-(20,1,1)-(20,1,2)-(20,1,3)-(20,3,1)-(20,3,3)-(20,3,2)-(20,2,1)-(20,2,2)-(20,2,3)-(16,1,1)-(16,1,2)-(16,1,3)-(16,3,1)-(16,3,3)-(16,3,2)-(16,2,1)-(16,2,2)-(16,2,3)-(17,1,1)-(17,1,3)-(17,1,2)-(17,2,1)-(17,2,2)-(17,2,3)-(17,3,1)-(17,3,3)-(17,3,2)-(7,1,1)-(7,1,3)-(7,1,2)-(7,2,1)-(7,2,2)-(7,2,3)-(7,3,1)-(7,3,3)-(7,3,2)-(6,1,1)-(6,1,3)-(6,1,2)-(6,2,1)-(6,2,2)-(6,2,3)-(6,3,1)-(6,3,3)-(6,3,2)-(15,1,1)-(15,1,2)-(15,1,3)-(15,3,1)-(15,3,3)-(15,3,2)-(15,2,1)-(15,2,2)-(15,2,3)-(14,1,1)-(14,1,3)-(14,1,2)-(14,2,1)-(14,2,2)-(14,2,3)-(14,3,1)-(14,3,3)-(14,3,2)-(13,1,1)-(13,1,2)-(13,1,3)-(13,3,1)-(13,3,3)-(13,3,2)-(13,2,1)-(13,2,2)-(13,2,3)-(12,1,1)-(12,1,3)-(12,1,2)-(12,2,1)-(12,2,2)-

Figure 5. DSCC(2)

图5. DSCC(2)

Figure 6. The ring representation of DSCC(2)

图6. DSCC(2)的圈表示

(12,2,3)-(12,3,1)-(12,3,3)-(12,3,2)-(11,1,1)-(11,1,2)-(11,1,3)-(11,3,1)-(11,3,3)-(11,3,2)-(11,2,1)-(11,2,2)-(11,2,3)-(10,1,1)-(10,1,2)-(10,1,3)-(10,3,1)-(10,3,3)-(10,3,2)-(10,2,1)-(10,2,2)-(10,2,3)-(2,1,1)-(2,1,2)-(2,1,3)-(2,3,1)-(2,3,3)-(2,3,2)-(2,2,1)-(2,2,2)-(2,2,3)-(3,1,1)-(3,1,3)-(3,1,2)-(3,2,1)-(3,2,2)-(3,2,3)-(3,3,1)-(3,3,3)-(3,3,2)-(4,1,1)-(4,1,3)-(4,1,2)-(4,2,1)-(4,2,2)-(4,2,3)-(4,3,1)-(4,3,)-(4,3,2)-(5,1,1)-(5,1,3)-(5,1,2)-(5,2,1)-(5,2,2)-(5,2,3)-(5,3,1)-(5,3,3)-(5,3,2)-(1,1,1)。

由此可知，2次十二面体–师连通圈网络 $D S C C (2)$ 是Hamilton图。

定理3：k次十二面体–师连通圈网络 $D S C C (k)$ 是Hamilton图。

证明：当k = 0、1、2时，由引理1、定理1、2知，是Hamilton图。

假设k − 1次十二面体–师连通圈网络 $D S C C (k - 1)$ 是Hamilton图，即存在Hamilton圈 $H_{k - 1}$ 。

设 $v_{0}$ 是k − 1次十二面体–师连通圈网络 $D S C C (k - 1)$ 中的任意一个顶点， $v_{1}, v_{2}, v_{3}$ 是与 $v_{0}$ 相邻的三个顶点，则Hamilton圈 $H_{k - 1}$ 中必含有边 $v_{0} v_{1}, v_{0} v_{2}, v_{0} v_{3}$ 中的两条边。假设Hamilton圈 $H_{k - 1}$ 中含有边 $v_{0} v_{1}, v_{0} v_{2}$ (其它情况证明类似)，如图7所示。

当用一个小三角形分别代替k − 1次十二面体–师连通圈网络 $D S C C (k - 1)$ 中的每个顶点时，我们假设用三角形 $Δ_{v_{(i, 1)} v_{(i, 2)} v_{(i, 3)}}$ 代替顶点 $v_{i} (i = 0, 1, 2, 3)$ ，则 $v_{0}, v_{1}, v_{2}, v_{3}$ 四点处变化后的图 $D S C C (k)$ 如图8所示。用路 $P_{k} = v_{(1, 1)} v_{(0, 1)} v_{(0, 3)} v_{(0, 2)} v_{(2, 1)}$ 代替Hamilton圈 $H_{k - 1}$ 中的路 $P_{k - 1} = v_{1} v_{0} v_{2}$ 后，得到的圈 $H_{k}$ 即为k次十二面体–师连通圈网络 $D S C C (k)$ 中的Hamilton圈。

综上所述，由数学归纳法知k次十二面体–师连通圈网络 $D S C C (k)$ 是Hamilton图。

定理4：k次十二面体–师连通圈网络 $D S C C (k)$ 的性质：

1) k次十二面体–师连通圈网络有 $20 \times 3^{k}$ 个顶点，有 $30 \times 3^{k}$ 条边；

2) k次十二面体–师连通圈网络 $D S C C (k)$ 是3正则3连通的；

3) k次十二面体–师连通圈网络 $D S C C (k)$ 是平面图；

4) k次十二面体–师连通圈网络是Hamilton图。

定理5：任何一个3正则3连通的平面Hamilton图 $(3, 3) - H G$ ，每个顶点用一个三角形代替后得到的图 $(3, 3) - H G C C (1)$ 一定是3正则3连通的平面Hamilton图。

Figure 7. Local graphical representation of DSCC(k-1)

图7. DSCC(k-1)的局部图示

Figure 8. Local graphical representation of DSCC(k)

图8. DSCC(k)的局部图示

证明：设 $H_{0}$ 是任意3正则3连通平面Hamilton图 $(3, 3) - H G$ 的一个Hamilton圈， $v_{1}$ 是 $(3, 3) - H G$ 中的任意一个顶点， $v_{2}, v_{3}, v_{4}$ 是与 $v_{1}$ 相邻的三个顶点。则Hamilton圈 $H_{0}$ 中必含有边 $v_{1} v_{2}, v_{1} v_{3}, v_{1} v_{4}$ 中的两条边，假设Hamilton圈 $H_{0}$ 中含有边 $v_{1} v_{2}, v_{1} v_{3}$ (其它情况同理可证)，如图9所示。

当用小三角形分别代替3正则3连通平面Hamilton图 $(3, 3) - H G$ 中的每个顶点时，我们假设用三角形 $Δ_{v_{(i, 1)} v_{(i, 2)} v_{(i, 3)}}$ 代替顶点 $v_{i} (i = 1, 2, 3, \dots)$ ，则 $v_{1}, v_{2}, v_{3}, v_{4}$ 四点处变化后的平面图 $(3, 3) - H G C C (1)$ 如图10所示。在 $H_{0}$ 中，用路 $P_{1} = v_{(2, 1)} v_{(1, 1)} v_{(1, 3)} v_{(1, 2)} v_{(3, 1)}$ 代替Hamilton圈 $H_{0}$ 中的路 $P_{0} = v_{2} v_{1} v_{3}$ 后，得到的圈 $H_{1}$ 是一个Hamilton圈。所以，任何一个3正则3连通的平面Hamilton图 $(3, 3) - H G$ 的每个顶点用一个三角形代替后，得到的图 $(3, 3) - H G C C (1)$ 是3正则3连通的平面Hamilton图。

定理6：一个3正则3连通平面图 $(3, 3) - H G P$ 的每个顶点用一个三角形来代替得到的图 $(3, 3) - H G P C C (1)$ 是Hamilton图，则：

1) 图 $(3, 3) - H G P C C (1)$ 是3正则3连通的平面图；

2) 原图 $(3, 3) - H G P$ 是Hamilton图。

证明：1)结论显然成立。

2) 设Hamilton图 $(3, 3) - H G P C C (1)$ 中的一个Hamilton圈为 $H_{1} = v_{(1, 1)} v_{(1, 2)} v_{(1, 3)} v_{(2, 1)} v_{(2, 2)} v_{(2, 3)} \dots v_{(n, 1)} v_{(n, 2)} v_{(n, 3)} v_{(1, 1)}$ ，其中 $v_{(i, 1)}, v_{(i, 2)}, v_{(i, 3)}$ 是代替顶点 $v_{i} (i = 1, 2, \dots, n)$ 的三角形的三个顶点，如图11所示。

当用一个点去代替一个三角形时(可以看作是把这个三角形缩小为一个顶点)，我们假设用点 $v_{i} (i = 1, 2, \dots, n)$ 代替顶点为 $v_{(i, 1)}, v_{(i, 2)}, v_{(i, 3)}$ 的三角形，则代替后得到的图正是原图 $(3, 3) - H G P$ ，如图12所示。在 $H_{1}$ 中，用顶点 $v_{i} (i = 1, 2, \dots, n)$ 代替 $H_{1}$ 中的路 $P_{1} = v_{(i, 1)} v_{(i, 2)} v_{(i, 3)}$ 后，得到图 $(3, 3) - H G P$ 中的圈 $H_{1} = v_{1} v_{2} \dots v_{n - 1} v_{n} v_{1}$ 是一个Hamilton圈。所以，原图 $(3, 3) - H G P$ 是Hamilton图。

Figure 9. Local graphical representation of (3,3)-HG

图9. (3,3)-HG的局部图示

Figure 10. Local graphical representation of (3,3)-HGCC(1)

图10. (3,3)-HGCC(1)的局部图示

Figure 11. Local graphical representation of (3,3)-HGPCC(1)

图11. (3,3)-HGPCC(1)的局部图示

Figure 12. Local graphical representation of (3,3)-HGP

图12. (3,3)-HGP的局部图示

3.2. 十二面体连通圈网络的3维变体

在笛卡尔乘积图中，为了方便统一起见，我们用 $D S C C (0)$ 表示十二面体DH。

猜想4： $D S C C (k) \times K_{2}$ 是边不交的2个Hamilton圈的并。

在猜想4中，当k = 0时，笛卡尔乘积图为 $D S C C (k) \times K_{2}$ ，我们得到如下结论。

定理7： $D S C C (0) \times K_{2}$ 是边不交的1个Hamilton圈和2个完美对集的并。

证明： $D S C C (0) \times K_{2}$ 如图13、图14所示，我们能够找到

Hamilton圈 $H_{1}$ 为：

01-08-09-018-019-020-016-017-07-06-015-014-013-012-011-010-02-03-04-05-15-14-13-12-110-111-112-113-114-115-16-17-117-116-120-119-118-19-18-11-01。

完美对集 $M_{1}$ 为：01-02，03-012，04-014，05-06，07-08，09-010，011-019，013-020，015-016，017-018，11-12，13-112，14-114，15-16，17-18，19-110，111-119，113-120，115-116，117-118。

完美对集 $M_{2}$ 为：01-05，11-15，02-12，03-13，04-14，05-15，06-16，07-17，08-18，09-19，010-110，011-111，012-112，013-113，014-114，015-115，016-116，017-117，018-118，019-119，020-120。

Figure 13. DSCC(0)xK₂ after DSCC(0) ring representation

图13. DSCC(0)圈表示后的DSCC(0)xK₂

Figure 14. DSCC(0)xK₂

图14. DSCC(0)xK₂

定理得证。

引理2 [2] ：设 $G_{i} (i = 1, 2, \dots, n)$ 是连通图，则

$d (G_{1} \times G_{2} \times \dots \times G_{n}) = d (G_{1}) + d (G_{2}) + \dots + d (G_{n})$ ，

这里 $d (G)$ 表示图G的直径。

引理3 [2] ：如果 $k (G_{i}) = δ (G_{i}) > 0, i = 1, 2, \dots, n$ ，那么

$k (G_{1} \times G_{2} \times \dots \times G_{n}) = k (G_{1}) + k (G_{2}) + \dots + k (G_{n})$ ，

这里 $k (G)$ 表示图G的连通度， $δ (G)$ 表示图G的最小度。

引理4 [2] ：如果对每个 $i = 1, 2, \dots, n$ ，均有 $k (G_{i}) > 0$ ， $λ (G_{i}) > 0$ ，那么

$k (G_{1} \times G_{2} \times \dots \times G_{n}) \geq k (G_{1}) + k (G_{2}) + \dots + k (G_{n})$ ；

$λ (G_{1} \times G_{2} \times \dots \times G_{n}) \geq λ (G_{1}) + λ (G_{2}) + \dots + λ (G_{n})$ ；

这里 $k (G)$ 表示图G的连通度， $λ (G)$ 表示图G的边连通度。

引理5 [2] ：设 $G_{1}$ 和 $G_{2}$ 是无向图， $G_{1} \times G_{2}$ 是Hamilton图当且仅当 $G_{1}$ 和 $G_{2}$ 之一是Hamilton图，而另一个含Hamilton路。

定理8：十二面体–师连通圈网络 $D S C C (k)$ 与 $K_{2}$ 的笛卡尔乘积网络 $D S C C (k) \times K_{2}$ 的基本性质：

1) $D S C C (k) \times K_{2}$ 有 $40 \times 3^{k}$ 个顶点，有 $80 \times 3^{k}$ 条边；

2) $D S C C (k) \times K_{2}$ 是4正则4连通的；

3) $D S C C (k) \times K_{2}$ 的连通度 $k (D S C C (k) \times K_{2}) = 4$ ，边连通度 $λ (D S C C (k) \times K_{2}) = 6$ ；

4) 当 $k = 0$ 时， $D S C C (k) \times K_{2}$ 是Hamilton图。

对于猜想4：当 $k = 0, 1, 2, \dots$ 时， $D S C C (k) \times K_{2}$ 是边不交的2个Hamilton圈的并。这个结论在此处并没有得到证明，它的正确性有待我们进一步探索。

猜想5： $D S C C (k) \times C_{m} (m \geq 3)$ 是边不交的2个Hamilton圈和一个完美对集的并。

当 $k = 0, m = 3$ 时，笛卡尔乘积网络 $D S C C (0) \times C_{3}$ 如图15所示。

注：图中内部对应点之间的部分连线未画出。

定理9： $D S C C (0) \times C_{3}$ 是Hamilton图。

证明：由图15可知，Hamilton圈为：

01-08-09-018-019-020-016-017-07-06-015-014-013-012-011-010-02-03-04-05-15-16-17-18-19-110-111-112-113-120-119-118-117-116-115-114-14-13-23-24-25-21-28-27-26-215-214-213-212-211-219-220-216-217-218-29-210-22-12-11-01。

因此， $D S C C (0) \times C_{3}$ 是Hamilton图。

当 $k = 0, m = 4$ 时，笛卡尔乘积网络 $D S C C (0) \times C_{4}$ 如图16所示。

注：图中内部对应点之间的部分连线未画出。

定理10： $D S C C (0) \times C_{4}$ 是Hamilton图。

证明：由图16可知，Hamilton圈为：

01-08-09-018-019-020-016-017-07-06-015-014-013-012-011-010-02-03-04-05-15-14-13-12-110-111-112-113-114-115-16-17-117-116-120-119-118-19-18-12-11-21-28-29-218-219-220-216-217-27-26-215-214-213-212-211-210-22-23-24-25-35-34-33-32-310-311-312-313-314-315-36-37-317-316-320-319-318-39-38-31-01。

因此， $D S C C (0) \times C_{4}$ 是Hamilton图。

我们可以得到笛卡尔乘积网络 $D S C C (k) \times C_{m} (m \geq 3)$ 的一些性质如下：

Figure 15. DSCC(0)xC₃

图15. DSCC(0)xC₃

定理11：十二面体–师连通圈网络 $D S C C (k)$ 与环网络 $C_{m}$ 的笛卡尔乘积网络 $D S C C (k) \times C_{m}$ 的基本性质：

1) $D S C C (k) \times C_{m}$ 有 $20 m \times 3^{k}$ 个顶点，有 $50 m \times 3^{k}$ 条边；

2) $D S C C (k) \times C_{m}$ 是5正则5连通的；

3) $D S C C (k) \times C_{m}$ 的连通度 $k (D S C C (k) \times C_{m}) = 5$ ，边连通度 $λ (D S C C (k) \times C_{m}) = 8$ ；

4) 当 $k = 0, m = 3, 4$ 时， $D S C C (k) \times C_{m}$ 是Hamilton图。

猜想5的结论是否正确，我们在以后的研究中有待进一步探索。

4. 结束语

本文给出了 $D S C C (k)$ 的定义以及一些重要的性质，证明了 $D S C C (k)$ 是Hamilton图，并对进一步提

Figure 16. DSCC(0)XC₄

图16. DSCC(0)XC₄

出的猜想2和猜想3做了证明。构建了笛卡尔乘积网络 $D S C C (k) \times K_{2}$ 和 $D S C C (k) \times C_{m}$ ，给出了它们的一些性质，但对猜想4和猜想5的结论有待进一步研究。

致谢

衷心感谢堵丁柱教授在1996年把我们带进超级计算机互连网络研究领域。

文章引用

师海忠,张治成. k次十二面体–师连通圈网络
K Dodecahedron-Shi Connected Cycles Networks[J]. 计算机科学与应用, 2018, 08(06): 1013-1026. https://doi.org/10.12677/CSA.2018.86113

参考文献

1. 师海忠. 正则图连通圈: 多种互连网络的统一模型[C]//中国运筹学会. 中国运筹学会第十届学术交流会论文集: 2010年卷. Hong Kong: Global-Link Informatics Limited, 2010: 202-208.

2. 徐俊明. 组合网络理论[M]. 北京: 科学出版社, 2007.

3. Xu, J.M. (2013) Combinatorial Theory in Networks. Science Press, Beijing.

4. Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan Press Ltd., London.

5. 高随祥. 图论与网络流理论[M]. 北京: 高等教育出版社, 2009.

6. 张欣, 师海忠. 交叉立方体连通圈网络的Hamilton分解[J]. 软件, 2015, 36(8): 92-98.

7. 师海忠. 几类新的笛卡尔乘积互连网络[J]. 计算机科学, 2013, 40(6A): 265-270.

8. Shi, H. and Shi, Y. (2015) A New Model for Interconnection Network: K-Hierarchical Ring and R-Layer Graph Network. http://vdisk.weibo.com/s/dlizJyferZ-Zl

9. Shi, H. and Shi, Y. (2015) A Hierarchical Ring Group-Theoretic Model for Interconnection Networks. http://vdisk.weibo.com/s/dlizJyfeBX-2J

10. Shi, H. and Shi, Y. (2015) Cell-Breading Graph Model for Interconnection Networks. http://vdisk.weibo.com/s/dlizJyfesb05y

期刊菜单