这是用户在 2024-12-21 13:17 为 https://app.immersivetranslate.com/pdf-pro/aa8395c1-11f2-41fb-8ac6-452d5e15fdc8 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？


和弦环的分析

Slawomir Bujnowski* Bozydar Dubalski* Antoni Zabludowski*

  摘要


在本文中，分析了三阶和四阶和弦环。在论文的第一部分，讨论了一些文献中存在的和弦环的定义。第二部分的主要目标是寻找描述三阶和弦环中和弦长度的一般公式。这个和弦给出了描述通信网络的图，具有最小直径和平均路径长度。获得的结果与理论上获得的值进行了对比，这些值确定了这些参数的下限，以及在检查实际结构时获得的结果。与四阶图相关的主要结果在论文的第三部分中进行了展示。定义了两类和弦环，即理想图和最优图。已证明最优和弦环具有严格定义的节点数量，对于这些结构仅存在一个长度为 2 d ( G ) + 1 2 d ( G ) + 1 2d(G)+12 d(G)+1 的最优和弦，最优和弦环是通过使用两个哈密顿循环 ( d ( G ) ( d ( G ) (d(G)(d(G) 构建的，这意味着图的直径。 理想的和弦环（真实或虚拟）可以被视为任何分析的和弦环的下界。


关键词：和弦环，图的直径，平均路径长度。

  1 引言


作为在比得哥什技术与农业大学电信研究所进行的研究项目的一部分，针对交换系统进行了电信服务器的分布式结构分析。分布式电信服务器由多个相同的、复杂的交换模块组成，这些模块通过互连网络相互通信。最近，一些领先的电信设备制造商在其产品中实施了这样的解决方案[1, 2]。显然，电信服务器为其用户提供与大型交换机相同的功能和服务。在分析这些系统的过程中出现的主要问题是选择连接电信模块的互连网络结构。起初，来自分布式计算机系统的解决方案，特别是互连网络结构的解决方案被考虑。

对电信服务器的研究已经进行。分布式计算系统的开发旨在提高工程和科学应用的计算能力，基于并行处理的概念，通过一组使用特定互连网络连接的处理器实现。实际上，分布式计算系统在概念上与研究的分布式电信服务器非常相似。显然，互连网络的拓扑结构决定了整个系统的效率[3]，无论是在分布式计算系统还是分布式电信服务器中。互连网络结构应提供非常高的可靠性以及服务质量水平。在分析的互连结构中（即超立方体、网格、凯利图、环等），环是最便宜且最容易实现的，但它们的连通性最低，直径最高[4]。因此，这些网络的传输特性（我们将呼叫拒绝的概率视为质量参数）与其他图相比非常差。 改善互连结构传输特性的最简单方法是使用称为弦的额外边缘，这些边缘以特定方式连接环的节点。文献中将连接节点的额外边缘的环称为弦环。

定义 1 和弦环是一个长度为 1 的循环图。它由对 ( w , S ) ( w , S ) (w,S)(w, S) 定义，其中 w w ww 表示环的节点数量， S S SS 是和弦的集合 S ⊆ { 2 , … , ⌊ w / 2 ⌋ } S ⊆ { 2 , … , ⌊ w / 2 ⌋ } S sube{2,dots,|__ w//2__|}S \subseteq\{2, \ldots,\lfloor w / 2\rfloor\} 。每个和弦 s ∈ S s ∈ S s in Ss \in S 连接环中距离 s s ss 的每对节点。这个结构用符号 G ( w ; s 1 , … , s i ) , s 1 < … < s i G w ; s 1 , … , s i , s 1 < … < s i G(w;s_(1),dots,s_(i)),s_(1) < dots < s_(i)G\left(w ; s_{1}, \ldots, s_{i}\right), s_{1}<\ldots<s_{i} 表示，由 ( w , { s 1 , … , s i } ) w , s 1 , … , s i (w,{s_(1),dots,s_(i)})\left(w,\left\{s_{1}, \ldots, s_{i}\right\}\right) 定义的和弦环。 G ( w ; s 1 , … , s i ) G w ; s 1 , … , s i G(w;s_(1),dots,s_(i))G\left(w ; s_{1}, \ldots, s_{i}\right) 的维度是 i + 1 i + 1 i+1i+1 。一般来说，当存在长度为 w / 2 w / 2 w//2w / 2 的和弦时，和弦环的度数是 2 i 2 i 2i2 i ，在这种情况下 w w ww 是偶数，环的度数是 2 i − 1 2 i − 1 2i-12 i-1 [5]。

图 1：三度和四度和弦环的示例 G ( 16 ; 1 , 8 ) , G ( 16 ; 1 , 4 ) G ( 16 ; 1 , 8 ) , G ( 16 ; 1 , 4 ) G(16;1,8),G(16;1,4)G(16 ; 1,8), G(16 ; 1,4) 和 G ( 16 ; 1 , 5 ) G ( 16 ; 1 , 5 ) G(16;1,5)G(16 ; 1,5)

和弦环一词在许多论文中也指代节点度数为三的规则图。

定义 2 和弦环是一种环状结构网络，其中每个节点都有一个额外的链接，称为和弦，连接网络中的其他某个节点。在环中，每个奇数编号的节点 i = { 1 , 3 , 5 , … , w − 1 } i = { 1 , 3 , 5 , … , w − 1 } i={1,3,5,dots,w-1}i=\{1,3,5, \ldots, w-1\} 与编号为 ( i + s ) mod w ( i + s ) mod w (i+s)mod w(i+s) \bmod w 的节点相连，其中 s s ss 是奇数，因此编号为 ( i + s ) ( i + s ) (i+s)(i+s) 的节点是偶数。因此，在和弦环中，每个偶数编号的节点 j = { 0 , 2 , 4 , … , w − 2 } j = { 0 , 2 , 4 , … , w − 2 } j={0,2,4,dots,w-2}j=\{0,2,4, \ldots, w-2\} 与奇数编号的节点 ( j − s ) ( j − s ) (j-s)(j-s) 模 w w ww 相连，其中 s ≥ w / 2 s ≥ w / 2 s >= w//2s \geq w / 2 表示和弦的长度， w w ww 表示节点的数量。和弦的长度是正数且为奇数。[6]

为了描述由定义 2 定义的三度和弦环，我们将引入额外的索引 G 3 G 3 G_(3)\mathbf{G}_{3} 。

图 2：三次函数的图形示例 G 3 ( 16 ; 1 , 3 ) , G 3 ( 16 ; 1 , 5 ) G 3 ( 16 ; 1 , 3 ) , G 3 ( 16 ; 1 , 5 ) G_(3)(16;1,3),G_(3)(16;1,5)\mathbf{G}_{3}(16 ; 1,3), \mathbf{G}_{3}(16 ; 1,5)

在我们开始对和弦环的分析之前，我们回顾一下基本的图参数，这些参数将用于图的比较。
  网络直径：
d ( G ) = max v i v j { d min ( v i , v j ) } d ( G ) = max v i v j   d min v i , v j d(G)=max_(v_(i)v_(j)){d_(min)(v_(i),v_(j))}d(G)=\max _{v_{i} v_{j}}\left\{d_{\min }\left(v_{i}, v_{j}\right)\right\}

是所有节点对之间所有最短路径长度中的最大值。

所有节点对之间路径的平均长度由以下公式定义：
d av = 1 w ( w − 1 ) ∑ i = 0 w − 1 ∑ j = 0 w − 1 d min ( v i , v j ) d av = 1 w ( w − 1 ) ∑ i = 0 w − 1   ∑ j = 0 w − 1   d min v i , v j d_(av)=(1)/(w(w-1))sum_(i=0)^(w-1)sum_(j=0)^(w-1)d_(min)(v_(i),v_(j))d_{\mathrm{av}}=\frac{1}{w(w-1)} \sum_{i=0}^{w-1} \sum_{j=0}^{w-1} d_{\min }\left(v_{i}, v_{j}\right)

上述定义的参数将作为分析网络通信能力的主要衡量标准。在本文的下一部分，我们将推导出给出近似最佳弦值的公式。然而，在我们能够定义这些公式之前，我们应该描述可以视为理想的弦环，这些弦环不一定在现实中存在。


2 第三度冠状环


正如我们已经解释的，弦环作为连接分布模块的通信结构（通信网络）非常有用。分析这种网络的唯一问题是确定描述环的属性的参数，这些参数应该被考虑。在大多数论文中，作者使用弦环的直径作为描述环属性的主要参数[7]。他们声称，这个参数决定了该结构在设计多计算机、多处理器或电信网络中的有用性。根据获得的结果，他们进一步建议，弦长等于 w + 3 w + 3 sqrtw+3\sqrt{w}+3 或 w + 5 w + 5 sqrtw+5\sqrt{w}+5 时，弦环的直径最短，基于这种环的拓扑结构的网络具有比其他网络更好的传输能力 [ 6 , 8 , 9 , 10 ] [ 6 , 8 , 9 , 10 ] [6,8,9,10][6,8,9,10] 。

然而，我们观察到，弦环的直径并不是分析通信网络属性的充分参数，因为该参数并不能决定网络的传输能力。我们研究了几百个由 3 度弦环（以及更高节点度数）确定的网络，并观察到，具有相同直径的网络在传递电信流量方面的能力往往不同。为了检验网络的传输能力，我们使用了蒙特卡洛方法的计算机模拟测试。以下假设已被考虑：

  • 对具有相同节点数和链路传输能力的不同和弦环（互连网络）进行了比较；

  • 在节点之间的多商品流（泊松，指数）已被研究；

  • 每个节点生成的流量强度的值已增加。对于固定的流量值，进行了数千次尝试；

  • 在每次尝试中，固定流量值的源节点和目标节点是采用均匀分布的；

  • 在源和目的地之间选择了最短路径来承载流量。如果节点之间存在多条可能的路径，则选择负载最少的路径；

  • 由公式描述的呼叫拒绝概率
p c r = ∑ P N ∑ G P p c r = ∑ P N ∑ G P p_(cr)=(sum PN)/(sum GP)p_{c r}=\frac{\sum P N}{\sum G P}
  哪里
∑ P N − rejected call number, ∑ G P − total call number, ∑ P N −  rejected call number,  ∑ G P −  total call number,  {:[ sum PN-" rejected call number, "],[ sum GP-" total call number, "]:}\begin{aligned} & \sum P N-\text { rejected call number, } \\ & \sum G P-\text { total call number, } \end{aligned}
  已被计算。

作为例子，我们将讨论两个网络的通信特性？第一个网络有 30 个节点，第二个网络有 56 个节点。对于这些网络获得的仿真结果如图 3 所示。对于 30 个节点的和弦环，所有环的直径相同，均为 5，但对于 56 个节点的环，图 G 3 ( 56 , 1 , 13 ) G 3 ( 56 , 1 , 13 ) G_(3)(56,1,13)\mathbf{G}_{3}(56,1,13) 的直径为 7，图 G 3 ( 56 , 1 , 11 ) G 3 ( 56 , 1 , 11 ) G_(3)(56,1,11)\mathbf{G}_{3}(56,1,11) 的直径为 8（最佳图 G 3 ( 56 , 1 , 9 ) G 3 ( 56 , 1 , 9 ) G_(3)(56,1,9)\mathbf{G}_{3}(56,1,9) 的直径为 7）。

图 3：仿真结果。 T i T i T_(i)T_{i} - 每个节点生成的总流量值， P c r − P c r − P_(cr)-P_{c r}- 拒绝呼叫的概率

分析的和弦环的呼叫拒绝概率是不同的。对于具有 30 个节点的图（我们提醒所有图的直径相同），呼叫拒绝的概率（对于固定的流量值）在和弦长度等于 7 时达到最小值，但对于具有 56 个节点的和弦环，直径较大的环的呼叫拒绝概率小于直径较小的环。从上述讨论可以得出结论，为了找到具有更好通信流量承载能力且呼叫拒绝概率最小的和弦环，我们应该选择能够最小化与图的直径完全不同的参数的和弦。然而，对和弦环的更详细检查表明，和弦环的通信能力受到所有节点对之间最短路径平均长度 d av d av d_(av)d_{\mathrm{av}} 的最大影响。因此，提出了以下公设：

公设 1 在三度弦环中，呼叫拒绝的概率取决于所有节点对之间路径的平均长度。

因此，和弦环的分析应关注环的两个基本参数，即网络直径和所有节点对之间路径的平均长度。

回到分析的例子，计算图 G 3 ( 30 , 1 , 7 ) G 3 ( 30 , 1 , 7 ) G_(3)(30,1,7)\mathbf{G}_{3}(30,1,7) 的路径平均值为 d av = 3.07 d av = 3.07 d_(av)=3.07d_{\mathrm{av}}=3.07 ，而对于 G 3 ( 30 , 1 , 9 ) G 3 ( 30 , 1 , 9 ) G_(3)(30,1,9)\mathbf{G}_{3}(30,1,9) 或 G 3 ( 30 , 1 , 11 ) G 3 ( 30 , 1 , 11 ) G_(3)(30,1,11)\mathbf{G}_{3}(30,1,11) ， d av = 3.14 d av = 3.14 d_(av)=3.14d_{\mathrm{av}}=3.14 。对于具有 56 个节点的环， G 3 ( 56 , 1 , 11 ) G 3 ( 56 , 1 , 11 ) G_(3)(56,1,11)\mathbf{G}_{3}(56,1,11) （直径为 8）， d av = 4.25 d av = 4.25 d_(av)=4.25d_{\mathrm{av}}=4.25 和 G 3 ( 56 , 1 , 13 ) G 3 ( 56 , 1 , 13 ) G_(3)(56,1,13)\mathbf{G}_{3}(56,1,13) （直径为 7） − d av = 4.29 − d av = 4.29 -d_(av)=4.29-d_{\mathrm{av}}=4.29 。最佳图 G 3 ( 56 , 1 , 9 ) G 3 ( 56 , 1 , 9 ) G_(3)(56,1,9)\mathrm{G}_{3}(56,1,9) 的直径为 7 和 d av = 4.18 d av = 4.18 d_(av)=4.18d_{\mathrm{av}}=4.18 。


2.1 最优和理想的度为 3 的和弦环


在本文的这一部分，将定义两种类型的和弦环，第一种称为最优和弦环，第二种称为理想图。这些环将用于比较“理想”和实际获得的结构。

在定义理想图之前（即将用于比较被检查图的参数的图），应定义最优图。

最优图是具有以下特征的和弦环：

  1. 在第 d d dd 层中的节点数量 w d w d w_(d)w_{d} （该层是指从任何源节点通过 d d dd 边到达的节点子集），由以下公式给出：
w d o = 3 d w d o = 3 d w_(do)=3dw_{d o}=3 d

图 4：前三层的节点分布

图中直径为 d ( G ) d ( G ) d(G)d(G) 的节点总数 w o w o w_(o)w_{o} 为：
w 0 = 1 + 3 ∑ d = 1 d ( G ) d = 1 + 3 d ( G ) [ d ( G ) + 1 ] 2 w 0 = 1 + 3 ∑ d = 1 d ( G )   d = 1 + 3 d ( G ) [ d ( G ) + 1 ] 2 w_(0)=1+3sum_(d=1)^(d(G))d=1+3(d(G)[d(G)+1])/(2)w_{0}=1+3 \sum_{d=1}^{d(G)} d=1+3 \frac{d(G)[d(G)+1]}{2}

  1. 图中 w o w o w_(o)w_{o} 个节点的直径为：
d ( G ) o = 24 w o − 15 − 3 6 d ( G ) o = 24 w o − 15 − 3 6 d(G)_(o)=(sqrt(24w_(o)-15)-3)/(6)d(G)_{o}=\frac{\sqrt{24 w_{o}-15}-3}{6}

  1. 路径的平均长度等于：
d avo = 3 ∑ d = 1 d ( G ) d 2 w o − 1 = d ( G ) [ d ( G ) + 1 ] [ 2 d ( G ) + 1 ] 2 ( w o − 1 ) = 2 d ( G ) + 1 3 d avo = 3 ∑ d = 1 d ( G )   d 2 w o − 1 = d ( G ) [ d ( G ) + 1 ] [ 2 d ( G ) + 1 ] 2 w o − 1 = 2 d ( G ) + 1 3 d_(avo)=3(sum_(d=1)^(d(G))d^(2))/(w_(o)-1)=d(G)([d(G)+1][2d(G)+1])/(2(w_(o)-1))=(2d(G)+1)/(3)d_{\mathrm{avo}}=3 \frac{\sum_{d=1}^{d(G)} d^{2}}{w_{o}-1}=d(G) \frac{[d(G)+1][2 d(G)+1]}{2\left(w_{o}-1\right)}=\frac{2 d(G)+1}{3}

在下表中，给出了节点数量、路径的平均长度与直径的关系。
d ( G ) d ( G ) d(G)d(G) 1 2 3 4 5 6 7 8
w o w o w_(o)w_{o} 4 10 19 31 46 64 85 109
d avo d avo  d_("avo ")d_{\text {avo }} 1 1.67 2.33 3 3.67 4.33 5 5.67
d(G) 1 2 3 4 5 6 7 8 w_(o) 4 10 19 31 46 64 85 109 d_("avo ") 1 1.67 2.33 3 3.67 4.33 5 5.67| $d(G)$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | $w_{o}$ | 4 | 10 | 19 | 31 | 46 | 64 | 85 | 109 | | $d_{\text {avo }}$ | 1 | 1.67 | 2.33 | 3 | 3.67 | 4.33 | 5 | 5.67 |

定理 1 不存在直径为 4 j 4 j 4j4 j 或 4 j − 1 ( j = 1 , 2 , … ) 4 j − 1 ( j = 1 , 2 , … ) 4j-1(j=1,2,dots)4 j-1(j=1,2, \ldots) 的度为 3 的最优和弦环。

证明：在假设的前提下，图存在的必要条件是节点数为偶数。理想图 d ( G ) d ( G ) d(G)d(G) 的直径中存在的节点总数等于
w o = 1 + 3 d ( G ) [ d ( G ) + 1 ] 2 w o = 1 + 3 d ( G ) [ d ( G ) + 1 ] 2 w_(o)=1+3(d(G)[d(G)+1])/(2)w_{o}=1+3 \frac{d(G)[d(G)+1]}{2}
  所以
3 d ( G ) [ d ( G ) + 1 ] 2 3 d ( G ) [ d ( G ) + 1 ] 2 3(d(G)[d(G)+1])/(2)3 \frac{d(G)[d(G)+1]}{2}

必须为每个 d ( G ) d ( G ) d(G)d(G) 值带来一个奇数。通过在上述公式中使用值 4 j 4 j 4j4 j 和 4 j − 1 4 j − 1 4j-14 j-1 ，我们得到
3 4 j ( 4 j + 1 ) 2 3 4 j ( 4 j + 1 ) 2 3(4j(4j+1))/(2)3 \frac{4 j(4 j+1)}{2}
  和
3 ( 4 j − 1 ) 4 j 2 3 ( 4 j − 1 ) 4 j 2 3((4j-1)4j)/(2)3 \frac{(4 j-1) 4 j}{2}

分别地。由于任何数字乘以偶数都会得到偶数，因此所描述图中的节点总数将是奇数。

唯一一个真正的最优图是一个具有 4 个节点和直径 d ( G ) = 1 d ( G ) = 1 d(G)=1d(G)=1 的图，简单来说，它是一个完全图。并没有说明应该存在任何实际构建直径为 d ( G ) > 1 d ( G ) > 1 d(G) > 1d(G)>1 的理想图的可能性。最优图是理想图的特殊组。理想图是一个理论上的和弦环，依次满足以下条件：

  1. 理想图的直径与 w i w i w_(i)w_{i} 个节点相等：
d ( G ) i = ⌈ 24 w − 15 − 3 6 ⌉ d ( G ) i = 24 w − 15 − 3 6 d(G)_(i)=|~(sqrt(24 w-15)-3)/(6)~|d(G)_{i}=\left\lceil\frac{\sqrt{24 w-15}-3}{6}\right\rceil

  1. 第 d d dd 层的节点数量 w d i w d i w_(di)w_{d i} 是：
if d ≠ d ( G ) ⇒ w d i = 3 d if d = d ( G ) ⇒ w d i = w − w o { d ( G ) r − 1 }  if  d ≠ d ( G ) ⇒ w d i = 3 d  if  d = d ( G ) ⇒ w d i = w − w o d ( G ) r − 1 {:[" if "d!=d(G)=>w_(di)=3d],[" if "d=d(G)=>w_(di)=w-w_(o{d(G)_(r)-1})]:}\begin{aligned} & \text { if } d \neq d(G) \Rightarrow w_{d i}=3 d \\ & \text { if } d=d(G) \Rightarrow w_{d i}=w-w_{o\left\{d(G)_{r}-1\right\}} \end{aligned}

其中： w w ww - 理想图中的节点数， w o { d ( G ) i − 1 } w o d ( G ) i − 1 w_(o{d(G)_(i)-1})w_{o\left\{d(G)_{i}-1\right\}} - 直径为 d ( G ) i − 1 d ( G ) i − 1 d(G)_(i)-1d(G)_{i}-1 的最优图中的节点数。

3. 路径的平均长度等于：
d avi = d ( G ) i [ d ( G ) i − 1 ] [ 2 d ( G ) i − 1 ] + 2 ( w − w o { d ( G ) i − 1 } 2 ( w − 1 ) d avi = d ( G ) i d ( G ) i − 1 2 d ( G ) i − 1 + 2 w − w o d ( G ) i − 1 2 ( w − 1 ) d_(avi)=d(G)_(i)([d(G)_(i)-1][2d(G)_(i)-1]+2(w-w_(o{d(G)_(i)-1}))/(2(w-1))d_{\mathrm{avi}}=d(G)_{i} \frac{\left[d(G)_{i}-1\right]\left[2 d(G)_{i}-1\right]+2\left(w-w_{o\left\{d(G)_{i}-1\right\}}\right.}{2(w-1)}

理想图的参数决定了直径和平均长度路径的下限，并且它们是评估在检查真实结构时获得的结果的基础。


2.2 弦计算的近似方法


在弦环度数为 3 的直径分布与弦长的关系中，得到了下图所示的典型图表。


图 5：三度弦图的直径与弦长 - 484 个节点

公设 2 在三度弦环中，选择弦长 s 2 s 2 s_(2)s_{2} 等于
s 2 = | 2 w | or s 2 = w 2 − | w 2 | s 2 = | 2 w |  or  s 2 = w 2 − w 2 s_(2)=|sqrt(2w)|quad" or "quads_(2)=(w)/(2)-|sqrt((w)/(2))|s_{2}=|\sqrt{2 w}| \quad \text { or } \quad s_{2}=\frac{w}{2}-\left|\sqrt{\frac{w}{2}}\right|

保证该图的直径与参考图的直径接近。

证明：在获得的图表中，我们可以观察到两个范围，在这些范围内，分布达到了局部最小值。

最大直径值与弦长的分布近似函数（我们使用最小二乘法 [11]）由以下公式给出：
(i) d ( G ) s 2 = s 2 2 + w s 2 + C (ii) d ( G ) s 2 = w 2 − s 2 + w 2 ( w 2 − s 2 ) + C  (i)  d ( G ) s 2 = s 2 2 + w s 2 + C  (ii)  d ( G ) s 2 = w 2 − s 2 + w 2 w 2 − s 2 + C {:[" (i) "d(G)_(s_(2))=(s_(2))/(2)+(w)/(s_(2))+C],[" (ii) "d(G)_(s_(2))=(w)/(2)-s_(2)+(w)/(2((w)/(2)-s_(2)))+C]:}\begin{aligned} \text { (i) } d(G)_{s_{2}} & =\frac{s_{2}}{2}+\frac{w}{s_{2}}+C \\ \text { (ii) } d(G)_{s_{2}} & =\frac{w}{2}-s_{2}+\frac{w}{2\left(\frac{w}{2}-s_{2}\right)}+C \end{aligned}<