多维环面网络的生成花边连通性

《Symmetry》：On the Spanning Laceability of Multi-Dimensional Torus Networks

　　

一对一的不相交路径路由构成了一种基本的流量模型，其中一个服务器可通过若干内部顶点不相交的路径向另一服务器传输数据包。由于该模型有助于提升容错能力、负载均衡和拥塞控制，已被深入研究。若对于任意??∈??₀和??∈??₁，存在k条连接u与v且其并集覆盖H所有顶点的内部顶点不相交路径，则具有二部划分??₀和??₁的二部图H被称为??^?-花边可连通的。设u为G的一个顶点，??={??₁,??₂,…,??_??}为??(??)?{??}的子集。生成(??,??)-扇是G中的一组内部顶点不相交路径{??₁,??₂,…,??_??}，使得对于每个1≤??≤??，??_??连接u与??_??，且?_??=1^????(??_??)=??(??)。多维环面网络作为超立方体的自然推广，是一种被广泛研究的具有高度对称性的网络。本文证明二部环面容许生成(??,??)-扇，由此可推出n维二部环面??(??₁,??₂,…,??_??)对于每个1≤??≤2??均为??^?-花边可连通的。该结果相对于环面的度是最优的。

研究背景：在大规模并行系统中，互连网络至关重要，它决定了硬件成本、通信性能、算法潜力与容错能力。互连网络的拓扑结构可用图G建模，其中顶点表示处理器，边表示通信链路。在互连网络中嵌入哈密尔顿路径十分关键，多播和广播等多种通信任务均依赖于建立一条遍历每个节点的路径；此外，在网络多播路由算法中引入哈密尔顿路径可有效缓解或防止死锁与拥塞。哈密尔顿性与连通性是图论的两个基本主题，生成连通性（spanning connectivity）作为结合并推广这两者的概念近年来被提出并研究。Simmons提出了哈密尔顿花边连通性（Hamiltonian laceability）的概念，Chang等将其推广为二部图的??^?-花边连通性，生成花边连通性（spanning laceability）定义为使H对所有??均??^?-花边可连通的最大整数k，若该值等于图的度则称H为超生成花边可连通的（super spanning-laceable）。除一对一情形外，多对多不相交路径覆盖问题也已被研究。然而，多播问题——给定源顶点和一组目的顶点，将消息从源传输至每个目的——在并行与分布式计算系统中对实现可靠广播和安全消息传递至关重要，而容器方法和不相交路径覆盖框架均不适用于此问题；该问题可自然地用图论中的生成扇建模。多维环面作为超立方体的自然扩展，是广泛使用的互连网络，n维环面??(??₁,??₂,…,??_??)对应于n个环??_??1,??_??2,…,??_????的笛卡尔积。已有研究探索了环面上的容错哈密尔顿性质、二维非二部环面的生成连通性与二维二部环面的生成花边连通性、多维非二部环面的生成连通性以及带故障边环面的成对二不相交路径覆盖。然而，关于多维二部环面生成花边连通性的结果文献中报道甚少。本文证明n维二部环面容许生成(??,??)-扇（|S|≤2n），由此推出n维二部环面对所有1≤??≤2??均为??^?-花边可连通的，该结果相对于环面的度是最优的。

研究人员开展的研究及结论与意义：研究人员证明了n维二部环面T容许生成(??,??)-扇（|S|≤2n），由此得出二部环面是超生成花边可连通的，即n维二部环面对每个1≤??≤2??均为??^?-花边可连通的。由于环面的度为2n，该结果相对于度是最优的。这一结果的重要意义在于为多播问题提供了可行策略，并推广了环面网络在容错路由与负载均衡方面的理论成果。

关键技术方法（不超过250字）：研究人员主要采用以下技术方法：利用网格图（grid graph）中角顶点到异色顶点的哈密尔顿路径存在性（Lemma 1）；利用??(??,??)的1-顶点故障双哈密尔顿连通性（bihamiltonian connected，Lemma 2）；利用??(??,??)的1-边故障哈密尔顿花边连通性（Lemma 3）；利用平衡顶点集间非成对2-不相交路径覆盖（2-DPC，Lemma 4）；利用n维二部环面的哈密尔顿花边连通性、成对2-DPC及1-顶点故障双哈密尔顿连通性（Lemma 5-7及其推论）；并采用对维数n和参数m的归纳法，结合沿某一维将环面分割为子环面（torus）与??(??,??)等子结构进行分情形构造性证明。研究未涉及样本队列来源。

研究结果：
1. 预备结果：通过Lemma 5-7及其推论（Corollary 1-3），研究人员建立了n维二部环面沿第r维分割所得子图的哈密尔顿花边连通性、成对2-DPC存在性以及1-顶点故障双哈密尔顿连通性，为后续归纳构造奠定基础。
2. 环面??(??,??)的生成扇（Lemma 8-12）：通过分情形构造并利用Lemma 1-4，研究人员证明了??(??,??)（m,n为偶数）对|S|≤3容许生成(??,??)-扇（Lemma 8-9），进而证明了对|S|≤4容许生成(??,??)-扇（Lemma 12）；期间还建立了??(??,??)中非成对3-DPC与2-DPC的存在性（Lemma 10-11）。
3. 递归构造（Lemma 13-14）：通过沿某一维分割并利用推论及归纳假设，研究人员证明了若两个子环面分别容许相应生成扇，则其组合环面容许生成(??,??)-扇（Lemma 13-14）。
4. 主要定理（Theorem 1-2）：通过综合运用Lemma 5、Lemma 14、Lemma 15及推论1-3，研究人员证明了n维二部环面容许生成(??,??)-扇（|S|≤2n）（Theorem 1），并由此推出n维二部环面对每个1≤??≤2??均为??^?-花边可连通的（Theorem 2）。

讨论部分总结与结论翻译：本文证明n维二部环面T容许生成(??,??)-扇（|S|≤2n），该结果是最优的，因为|S|≤2n；由此可知二部环面是超生成花边可连通的。为说明这些结果，文中考察了二部环面??(4,4)和??(4,4,4)，并以表格形式给出了??(4,4)中针对各种顶点集S的生成(??,??)-扇示例，以及??(4,4,4)中的一个生成(??,??)-扇图示。然而，本文仅证明了二部环面中生成扇的存在性，并未提供此类扇的算法构造，这可能是未来研究的一个方向。此外，二部环面的边容错生成花边连通性以及非二部环面的边容错生成连通性也是未来可能的研究课题。研究结论翻译：本文证明二部环面容许生成(??,??)-扇，由此可推出n维二部环面??(??₁,??₂,…,??_??)对于每个1≤??≤2??均为??^?-花边可连通的，且该结果相对于环面的度是最优的。