一种笛卡尔乘积网络的泛圈性研究

The Pancyclicity Study of a Cartesian Product Network

摘要: 网络中子图的可嵌入性是度量网络性能的一个重要指标。圈作为网络拓扑中一类重要的子图，其可嵌入性可通过图的泛圈性来衡量。笛卡尔乘积网络DSCC(k)×C_m是在2018年被提出的一种新互连网络。在之前文献研究结果的基础上，文中进一步研究得到DSCC(0)×C₃是泛圈的，DSCC(0)×C₃(m>3)是边偶泛圈的，DSCC(k)×C_m(k>0,m≥3)是泛圈的。

Abstract: The embeddability of neutron graph is an important index to measure the performance of network. As an important kind of subgraphs of network topology, the embeddability of circles can be measured by the pancyclicity property of graphs. Cartesian product network DSCC(k)×C_m is a new interconnecting network proposed in 2018. Based on the results of previous literature, this paper further finds that DSCC(0)×C₃ is pancyclic, DSCC(0)×C₃(m>3) is edge bipancyclic and DSCC(k)×C_m(k>0,m≥3) is pancyclic.

1. 引言

互连网络是超级计算机的重要组成部分，互连网络的结构和性质是超级计算机研究的重要课题。在设计和选择一个互连网络的拓扑结构时，Hamilton性，泛圈性，连通度，直径等指标对分析网络性能发挥了重要作用 [1]。随着系统性能的需求越来越高，处理器核之间的互连架构必须能够提供具有较低延迟和高吞吐率的服务，并且具有良好的可扩展性 [2]。传统的互连架构已经难以满足现今系统的性能需求，所以片上互连网络便成为当前研究的热点课题之一。

在分析网络拓扑结构时，我们通常将互连网络拓扑结构模型化为一个无向图，图的顶点对应处理器，图的边对应网络的通讯链路 [1] [2] [3]。因而在研究互连网络的拓扑结构时，往往通过研究一个无向图来深入研究互连网络。互连网络拓扑的性能可以通过图的性能和指标来度量，如Hamilton性、嵌入性、容错性、泛圈性等 [1] - [14]。因此，图论是设计和分析互连网络最基本且强有力的工具。十二面体最早是随着哈密尔顿问题引起人们关注的，起源于1859年爱尔兰数学家威廉·哈密尔顿(Sir William Hamilton)提出一种名为“周游世界”的游戏。将十二面体投影到平面上：十二面体的顶点与棱分别对应图的顶点和边，就得到一个正十二面体图。十二面体有许多好的性质，比如它是三正则三连通图、是Hamilton图等。笛卡尔乘积图是一类重要的互连网络拓扑，由于它具有较好的正则性、连通性、点可迁性、Hamilton性等，从而在大规模互连网络研究中得到了广泛的关注 [7]。

图嵌入是一个客图到一个主图的映射，它保留了一些被要求的性质。如果一个客图能够嵌入到一个主图，那就意味着在客图网络上能够执行的算法同样能够在主图网络上模拟执行。在众多的互连网络拓扑中，路和圈是最为基础，也最为重要的两种网络拓扑结构。在路和圈网络中，容易设计出简单而又高效的路由算法。因此，在设计和选择互连网络时路和圈的可嵌入性是一个非常重要的考虑因素。邦迪提出了泛圈性问题，即寻找所有可能长度的圈。泛圈性是判断一个网络拓扑是否适合将不同长度的圈映射到其上的重要测量值。圈的嵌入是对互连网络的图嵌入问题研究的重点之一，它可以用图的泛圈性和边泛圈性来衡量 [2]。

在大规模并行系统中，互连网络在硬件成本、通信性能、高效算法和容错能力方面扮演着重要的角色。近年来，学者们提出了许多互连网络拓扑。笛卡尔乘积网络 $DSCC\left(k\right)\times C_m$ 是师海忠提出的一类重要的互连网络拓扑，由于它具有较好的正则性、连通性、Hamilton性等性质，从而为大规模超级计算机系统和互连网络的优化设计提供了理论参考价值，得到了广泛的关注和研究。

2. 基本概念

定义1 [1] [2]：图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中起点和终点相同的途径称为闭途径，边不重复出现的闭途径称为闭迹(也称为回路)。中途点不重复的闭途径称为圈。

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

定义3 [2]：设G是n阶图，如果G中存在任意长为 $l\left(3\le l\le n\right)$ 的圈，则称G是泛圈的；如果在G中，对于任意一个顶点v，存在任意长为 $l\left(3\le l\le n\right)$ 的包含v的圈，则G称为点泛圈的；如果在G中，对于任意一条边e，存在任意长为 $l\left(3\le l\le n\right)$ 的包含e的圈，则G称为边泛圈的。在一个n阶二部图G中，如果G中存在任意长为偶数 $l\left(4\le l\le n\right)$ 的圈，则G称为偶泛圈的；如果在G中，对于任意一个顶点v，存在任意长为偶数 $l\left(4\le l\le n\right)$ 的包含v的圈，则G称为点偶泛圈的；如果在G中，对于任意一条边e，存在任意长为偶数 $l\left(4\le l\le n\right)$ 的包含e的圈，则G称为边偶泛圈的。

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

定义5 [7]：设 $G_1=\left(V_1,E_1\right)$ 和 $G_2=\left(V_2,E_2\right)$ 是两个无向图， $G_1$ 和 $G_2$ 的笛卡尔乘积是无向图，记为 $G_1\times G_2$。其中 $V\left(G_1\times G_2\right)=V_1\times V_2=\left\{\left(v_1,v_2\right)|v_1\in V_1且v_2\in V_2\right\}$，存在一条顶点 $x_1{x}_2$ 与顶点 $y_1{y}_2$ 之间的边(其中 $x_1,y_1\in V\left(G_1\right),x_2,y_2\in V\left(G_2\right)$ )当且仅当或者 $x_1=y_1$ 且 $x_2{y}_2\in E\left(G_2\right)$，或者 $x_2=y_2$ 且 $x_1{y}_1\in E\left(G_1\right)$。类似，可以定义笛卡尔乘积 $G_1\times G_2\times \cdots \times G_n$。

定义6 [7]：将k次十二面体-师连通圈网络 $DSCC\left(k\right)$ 与一个长度为m的圈 $C_m$ 作笛卡尔乘积生成的新网络，我们记为 $DSCC\left(k\right)\times C_m\left(k=0,1,2,\cdots ,m=3,4,\cdots \right)$。

3. 主要结果

引理1 [7]： $DSCC\left(0\right)\times C_3$ 是边偶泛圈的。

引理2 [7]： $DSCC\left(k\right)\times C_m$ 是边偶泛圈的。

在引理1和引理2的基础上，我们进一步探究得到笛卡尔乘积网络 $DSCC\left(k\right)\times C_m$ 的泛圈性如下：

定理1： $DSCC\left(0\right)\times C_3$ 是泛圈的。

证明： $DSCC\left(0\right)\times C_3$ 如图1所示，在 $DSCC\left(0\right)\times C_3$ 中存在任意长为 $l\left(3\le l\le 60\right)$ 的圈 $C_l$ 如下：

$C_3$ ：01-21-11-01；

$C_4$ ：将 $C_3$ 中的21变为02~12；

$C_5$ ：将 $C_4$ 中的12变为22-21；

$C_6$ ：在 $C_5$ 中02~22之间增加顶点12；

$C_7$ ：将 $C_6$ 中的12变为03-23；

$C_8$ ：在 $C_7$ 中03~23之间增加顶点13；

$C_9$ ：将 $C_8$ 中的13变为04~24；

$C_{10}$ ：在 $C_9$ 中04~24之间增加顶点14；

$C_{11}$ ：将 $C_{10}$ 中的14变为05~25；

$C_{12}$ ：在 $C_{11}$ 中05~25之间增加顶点15；

$C_{13}$ ：将 $C_{12}$ 中的15变为06~26；

$C_{14}$ ：在 $C_{13}$ 中06~26之间增加顶点16；

$C_{15}$ ：将 $C_{14}$ 中的16变为07~27；

$C_{16}$ ：在 $C_{15}$ 中07~27之间增加顶点17；

$C_{17}$ ：将 $C_{16}$ 中的17变为08~28；

$C_{18}$ ：在 $C_{17}$ 中08~28之间增加顶点18；

$C_{19}$ ：将 $C_{18}$ 中的18变为09~29；

$C_{20}$ ：在 $C_{19}$ 中09~29之间增加顶点19；

Figure 1. DSCC(0) × C₃

图1. DSCC(0) × C₃

$C_{21}$ ：将 $C_{20}$ 中的19变为010~210；

$C_{22}$ ：在 $C_{21}$ 中010~210之间增加顶点110；

$C_{23}$ ：将 $C_{22}$ 中的110变为011~211；

$C_{24}$ ：在 $C_{23}$ 中011~211之间增加顶点111；

$C_{25}$ ：将 $C_{24}$ 中的111变为012~212；

$C_{26}$ ：在 $C_{25}$ 中012~212之间增加顶点112；

$C_{27}$ ：将 $C_{26}$ 中的112变为013~213；

$C_{28}$ ：在 $C_{27}$ 中013~213之间增加顶点113；

$C_{29}$ ：将 $C_{28}$ 中的113变为014~214；

$C_{30}$ ：在 $C_{29}$ 中014~214之间增加顶点114；

$C_{31}$ ：将 $C_{30}$ 中的114变为015~215；

$C_{32}$ ：在 $C_{31}$ 中015~215之间增加顶点115；

$C_{33}$ ：将 $C_{32}$ 中的115变为016~216；

$C_{34}$ ：在 $C_{33}$ 中016~216之间增加顶点116；

$C_{35}$ ：将 $C_{34}$ 中的116变为017~217；

$C_{36}$ ：在 $C_{35}$ 中017~217之间增加顶点117；

$C_{37}$ ：将 $C_{36}$ 中的117变为018~218；

$C_{38}$ ：在 $C_{37}$ 中018~218之间增加顶点118；

$C_{39}$ ：将 $C_{38}$ 中的118变为019~219；

$C_{40}$ ：在 $C_{39}$ 中019~219之间增加顶点119；

$C_{41}$ ：将 $C_{40}$ 中的119变为020~220；

$C_{42}$ ：在 $C_{41}$ 中020~220之间增加顶点120；

$C_{43}$ ：01-08-09-018-019-020-016-017-07-06-015-014-013-012-011-010-02-03-04-05-15-11-12-22-210-

211-219-220-216-217-218-29-28-27-26-215-214-213-212-23-24-25-21-01；

$C_{44}$ ：将 $C_{43}$ 中的11变为14-13；

$C_{45}$ ：01-08-09-018-019-020-016-017-07-06-015-014-013-012-011-010-02-03-04-05-15-14-13-23-212-

213-220-216-217-218-219-211-210-29-28-27-26-215-214-24-25-21-22-12-11-01；

$C_{46}$ ：01-08-09-018-019-020-016-017-07-06-015-014-013-012-011-010-02-03-04-05-15-16-17-18-11-12-

22-210-211-219-220-216-217-218-29-28-27-26-215-214-213-212-23-24-25-21-01；

$C_{47}$ ：将 $C_{46}$ 中的11变为19~110；

$C_{48}$ ：将 $C_{47}$ 中的18变为117~118；

$C_{49}$ ：将 $C_{48}$ 中的19变为119-111；

$C_{50}$ ：将 $C_{49}$ 中118变为116~120；

$C_{51}$ ：将 $C_{50}$ 中的111变为118-19；

$C_{52}$ ：将 $C_{51}$ 中的17-117-116-120变为115-114-113-112-111；

$C_{53}$ ：将 $C_{52}$ 中的112-111-119-118-19变为120-116-117-118-119-111；

$C_{54}$ ：将 $C_{53}$ 中的16-115-114-113-120-116-117-118-119-11变为14-13-112-113-114-115-16-17-117-118-

19；

$C_{55}$ ：将 $C_{54}$ 中的114变为120-116；

$C_{56}$ ：将 $C_{55}$ 中的113-120-116-115-16-17-117-118 变为111-119-120-113-114-115-16-17-18；

$C_{57}$ ：将 $C_{56}$ 中的18变为117~118；

$C_{58}$ ：将 $C_{57}$ 中的14-13-112-111-119-120-113-114-115-16-17-117-118-19变为11-18-19-118-119-120-

116-117-17-16-115-114-113-112-111；

$C_{59}$ ：将 $C_{58}$ 中的19-118-119-120-116-117-17-16-115-114-113-112变为17-16-115-114-14-13-112-113-

120-116-117-118-119；

$C_{60}$ ：01-08-09-018-019-020-016-017-07-06-015-014-013-012-011-010-02-03-04-05-15-14-13-23-212-

213-220-216-217-218-219-211-210-29-28-27-26-215-214-24-25-21-22-12-110-111-112-113-114-115-16-17-

117-116-120-119-118-19-18-11-01。

所以， $DSCC\left(k\right)\times C_m$ 是泛圈的。

定理2： $DSCC\left(0\right)\times C_m\left(m>3\right)$ 是边偶泛圈的。

证明： 由引理2知，显然 $DSCC\left(0\right)\times C_m\left(m>3\right)$ 是边偶泛圈的。

定理3： $DSCC\left(k\right)\times C_m\left(k>0,m\ge 3\right)$ 是泛圈的。

证明： 由泛圈性的定义知，我们只需证明在 $DSCC\left(k\right)\times C_m\left(k>0,m\ge 3\right)$ 中存在任意长为 $l\left(3\le l\le 20m\times 3^k\right)$ 的圈即可。根据l的奇偶性，我们对l进行分情况讨论：

情形1：当l为偶数时，令 $l=p$。

下面证明 $DSCC\left(k\right)\times C_m\left(k>0,m\ge 3\right)$ 中存在任意长为偶数 $p\left(3\le p\le 20m\times 3^k\right)$ 的偶圈。根据引理2，我们知道 $DSCC\left(k\right)\times C_m$ 是边偶泛圈的，故也是偶泛圈的，所以在 $DSCC\left(k\right)\times C_m$ 中任意长为偶数p的偶圈都是存在的。

情形2：当l为奇数时，令 $l=q$。

下面证明 $DSCC\left(k\right)\times C_m\left(k>0,m\ge 3\right)$ 中存在任意长为奇数 $q\left(3\le q\le 20m\times 3^k\right)$ 的奇圈。

当 $q=3$ 时，因为 $k>0$，所以在 $DSCC\left(k\right)\times C_m$ 中显然存在3长的圈 $C_3$。

当 $q>3$ 时，我们来证明在 $DSCC\left(k\right)\times C_m$ 中存在长为 $q\left(5\le q\le 20m\times 3^k-1\right)$ 的任意奇圈 $C_q$。由情形1知， $DSCC\left(k\right)\times C_m$ 中任意长为偶数p的偶圈都存在，我们任取其中一个偶圈 $C_p$，通过 $C_p$ 来构造奇圈 $C_q=C_{p+1}$。首先，因为 $DSCC\left(k\right)\times C_m$ 中的每个顶点都是某一个三角形的顶点，所以偶圈 $C_p$ 中的每个顶点也都属于某一个三角形。其次，在构造偶圈 $C_p$ 时，我们总能找到只包含某一个三角形中两个顶点的偶圈 $C_p$ 存在。假设 $C_p$ 包含某个三角形的顶点 $v_1$ 和 $v_2$，现在我们把该三角形的另一个顶点 $v_3$ 嵌入到 $v_1$ 和 $v_2$ 之间，于是就得到奇圈 $C_q=C_{p+1}$。由p的任意性知，故在 $DSCC\left(k\right)\times C_m$ 中能找到任意长为 $q\left(5\le q\le 20m\times 3^k-1\right)$ 的奇圈。

综合以上两种情形， $DSCC\left(k\right)\times C_m\left(k>0,m\ge 3\right)$ 中任意长度的圈 $l\left(3\le l\le 20m\times 3^k\right)$ 均存在，故 $DSCC\left(k\right)\times C_m\left(k>0,m\ge 3\right)$ 是泛圈的。

4. 结束语

本文在文献 [7] 研究结论的基础上，通过进一步讨论，对笛卡尔乘积网络 $DSCC\left(k\right)\times C_m$ 的泛圈性给出了更完善的结果。最终证明得到 $DSCC\left(0\right)\times C_3$ 是泛圈的， $DSCC\left(0\right)\times C_m\left(m>3\right)$ 是边偶泛圈的， $DSCC\left(k\right)\times C_m\left(k>0,m\ge 3\right)$ 是泛圈的。关于该网络的泛圈性和其他性质，还需要我们进一步更深层次的探讨和研究，来拓宽对这个网络的认识。

参考文献