这是用户在 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}

C C CC 表示一个对函数最小值没有任何影响的常数。
  一阶导数是：
(i) d ( G ) s 2 ′ = 1 2 − w s 2 2 (ii) d ( G ) s 2 ′ = w 2 ( w 2 − s 2 ) 2 − 1  (i)  d ( G ) s 2 ′ = 1 2 − w s 2 2  (ii)  d ( G ) s 2 ′ = w 2 w 2 − s 2 2 − 1 {:[" (i) "d(G)_(s_(2))^(')=(1)/(2)-(w)/(s_(2)^(2))],[" (ii) "d(G)_(s_(2))^(')=(w)/(2((w)/(2)-s_(2))^(2))-1]:}\begin{aligned} \text { (i) } d(G)_{s_{2}}^{\prime} & =\frac{1}{2}-\frac{w}{s_{2}^{2}} \\ \text { (ii) } d(G)_{s_{2}}^{\prime} & =\frac{w}{2\left(\frac{w}{2}-s_{2}\right)^{2}}-1 \end{aligned}

图 6：近似 484 个节点的弦环中最大直径分布的函数图示

所以这些函数达到最小值的条件是：
(i) s 2 = | 2 w | (ii) s 2 = w 2 − | w 2 |  (i)  s 2 = | 2 w |  (ii)  s 2 = w 2 − w 2 {:[" (i) "s_(2)=|sqrt(2w)|],[" (ii) "s_(2)=(w)/(2)-|sqrt((w)/(2))|]:}\begin{aligned} & \text { (i) } s_{2}=|\sqrt{2 w}| \\ & \text { (ii) } s_{2}=\frac{w}{2}-\left|\sqrt{\frac{w}{2}}\right| \end{aligned}

为了说明公设 2，分析了具有 484 个节点的弦环。在这种情况下，常数 C C CC 等于-10.25，但结果如下：
(i) (ii)
  计算的弦长 31.11 226.44
  计算的直径值 20.86 20.86
  实际绳长 31 227
  实际直径值 21 21
(i) (ii) Computed chord length 31.11 226.44 Computed diameter value 20.86 20.86 Real cord length 31 227 Real diameter value 21 21| | (i) | (ii) | | :---: | :---: | :---: | | Computed chord length | 31.11 | 226.44 | | Computed diameter value | 20.86 | 20.86 | | Real cord length | 31 | 227 | | Real diameter value | 21 | 21 |

最小直径 d ( G ) d ( G ) d(G)d(G) 等于 19，分别在 G 3 ( 484 , 1 , 51 ) G 3 ( 484 , 1 , 51 ) G_(3)(484,1,51)\mathbf{G}_{3}(484,1,51) 和 G 3 ( 484 , 1 , 57 ) G 3 ( 484 , 1 , 57 ) G_(3)(484,1,57)\mathbf{G}_{3}(484,1,57) 中获得。图 7 依次显示了平均路径长度与弦直径的分布。该图与图 5 中显示的直径分布具有类似的特征（梳状函数）。

公设 3 在 3 度弦环中，弦长 s 2 s 2 s_(2)s_{2} 的选择等于
(i) s 2 = | 1.8182 w | or (ii) s 2 = w 2 − 0.4545 w  (i)  s 2 = | 1.8182 w |  or (ii)  s 2 = w 2 − 0.4545 w {:[" (i) "s_(2)=|sqrt(1.8182 w)|],[" or (ii) "s_(2)=(w)/(2)-sqrt(0.4545 w)]:}\begin{aligned} \text { (i) } s_{2} & =|\sqrt{1.8182 w}| \\ \text { or (ii) } s_{2} & =\frac{w}{2}-\sqrt{0.4545 w} \end{aligned}

保证该图中路径的平均长度将接近参考图中存在的该参数的值。

图 7：484 个节点的和弦环中路径的平均长度与和弦长度的关系

证明：近似函数表示为：
(i) d max ( s 2 ) = 0.275 s 2 + w 2 s 2 + C (ii) d max ( s 2 ) = 0.55 ( w 2 − s 2 ) + w 4 ( w 2 − s 2 ) + C  (i)  d max s 2 = 0.275 s 2 + w 2 s 2 + C  (ii)  d max s 2 = 0.55 w 2 − s 2 + w 4 w 2 − s 2 + C {:[" (i) "d_(max)(s_(2))=0.275s_(2)+(w)/(2s_(2))+C],[" (ii) "d_(max)(s_(2))=0.55((w)/(2)-s_(2))+(w)/(4((w)/(2)-s_(2)))+C]:}\begin{aligned} & \text { (i) } d_{\max }\left(s_{2}\right)=0.275 s_{2}+\frac{w}{2 s_{2}}+C \\ & \text { (ii) } d_{\max }\left(s_{2}\right)=0.55\left(\frac{w}{2}-s_{2}\right)+\frac{w}{4\left(\frac{w}{2}-s_{2}\right)}+C \end{aligned}

并且它们达到 (i) s 2 = | 1.8182 w | s 2 = | 1.8182 w | s_(2)=|sqrt(1.8182 w)|s_{2}=|\sqrt{1.8182 w}| 或 (ii) s 2 = w 2 − 0.4545 w s 2 = w 2 − 0.4545 w s_(2)=(w)/(2)-sqrt(0.4545 w)s_{2}=\frac{w}{2}-\sqrt{0.4545 w} 的最小值

图 8：具有 484 个节点的弦环中逼近函数的图示

为了说明公设 3，分析了具有 484 个节点的弦环。在这种情况下，常数 C C CC 等于-4.25，但结果如下：
(i) (ii)
  计算的弦长 29.66 227.17

计算的平均长度路径值		 12.06 12.06
  实际绳长 29 227

实际平均长度路径值		 12.21 12.10
  直径 21 21
(i) (ii) Computed chord length 29.66 227.17 Computed average length path value 12.06 12.06 Real cord length 29 227 Real average length path value 12.21 12.10 Diameter 21 21| | (i) | (ii) | | :---: | :---: | :---: | | Computed chord length | 29.66 | 227.17 | | Computed average length path value | 12.06 | 12.06 | | Real cord length | 29 | 227 | | Real average length path value | 12.21 | 12.10 | | Diameter | 21 | 21 |

最小平均长度路径是 d av = 12.02 d av = 12.02 d_(av)=12.02d_{\mathrm{av}}=12.02 对于 G 3 ( 484 , 1 , 51 ) G 3 ( 484 , 1 , 51 ) G_(3)(484,1,51)\mathbf{G}_{3}(484,1,51) 和 G 3 ( 484 , 1 , 57 ) G 3 ( 484 , 1 , 57 ) G_(3)(484,1,57)\mathbf{G}_{3}(484,1,57) 。

下表中是使用所提供的方法和其他方法选择弦长的结果，并给出了这些图形的参数与参考图形的参数的比较。

节点 数字
Nodes number| Nodes | | :---: | | number |

和弦 长度
Chord Length| Chord | | :---: | | Length |
   直径

平均 长度
Average length| Average | | :---: | | length |

和弦 长度
Chord length| Chord | | :---: | | length |
   直径

平均 长度
Average length| Average | | :---: | | length |
50 9 7 3.94 19 7 3.98
100 15 9 5.52 43 10 5.95
500 31 22 12.44 235 21 12.30
1000 45 30 17.52 477 30 17.46
1600 57 41 22.39 771 38 22.13
2000 63 42 24.64 969 42 24.57
3000 77 56 30.59 1461 51 30.16
4000 89 64 35.30 1955 59 34.82
5000 99 67 38.89 2451 74 39.48
s 2 =∣ 2 w s 2 =∣ 2 w s_(2)=∣sqrt(2w)s_{2}=\mid \sqrt{2 w} s 2 = w 2 − s 2 = w 2 − s_(2)=(w)/(2)-s_{2}=\frac{w}{2}-
w 2 w 2 sqrt((w)/(2))\sqrt{\frac{w}{2}}
"Nodes number" "Chord Length" Diameter "Average length" "Chord length" Diameter "Average length" 50 9 7 3.94 19 7 3.98 100 15 9 5.52 43 10 5.95 500 31 22 12.44 235 21 12.30 1000 45 30 17.52 477 30 17.46 1600 57 41 22.39 771 38 22.13 2000 63 42 24.64 969 42 24.57 3000 77 56 30.59 1461 51 30.16 4000 89 64 35.30 1955 59 34.82 5000 99 67 38.89 2451 74 39.48 s_(2)=∣sqrt(2w) s_(2)=(w)/(2)- sqrt((w)/(2)) | Nodes <br> number | Chord <br> Length | Diameter | Average <br> length | Chord <br> length | Diameter | Average <br> length | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 50 | 9 | 7 | 3.94 | 19 | 7 | 3.98 | | 100 | 15 | 9 | 5.52 | 43 | 10 | 5.95 | | 500 | 31 | 22 | 12.44 | 235 | 21 | 12.30 | | 1000 | 45 | 30 | 17.52 | 477 | 30 | 17.46 | | 1600 | 57 | 41 | 22.39 | 771 | 38 | 22.13 | | 2000 | 63 | 42 | 24.64 | 969 | 42 | 24.57 | | 3000 | 77 | 56 | 30.59 | 1461 | 51 | 30.16 | | 4000 | 89 | 64 | 35.30 | 1955 | 59 | 34.82 | | 5000 | 99 | 67 | 38.89 | 2451 | 74 | 39.48 | | | $s_{2}=\mid \sqrt{2 w}$ | | | | $s_{2}=\frac{w}{2}-$ | | | $\sqrt{\frac{w}{2}}$ | | | | | | |

表 4：使用公设 2 获得的结果。

节点 数字
Nodes number| Nodes | | :---: | | number |

和弦 长度
Chord Length| Chord | | :---: | | Length |
   直径

平均 长度
Average length| Average | | :---: | | length |

和弦 长度
Chord length| Chord | | :---: | | length |
   直径

平均 长度
Average length| Average | | :---: | | length |
50 9 7 3.94 21 7 3.97
100 13 9 5.52 43 10 5.95
500 31 22 12.44 235 21 12.30
1000 43 30 17.46 479 30 17.44
1600 53 38 22.10 773 38 22.06
2000 61 42 24.65 969 42 24.57
3000 73 54 30.38 1463 51 30.15
4000 85 64 35.15 1957 59 34.81
5000 95 67 38.91 2453 70 39.22
s 2 = 1.8182 w s 2 = 1.8182 w s_(2)=sqrt(1.8182 w)s_{2}=\sqrt{1.8182 w} s 2 = w 2 − 0.4545 w s 2 = w 2 − 0.4545 w s_(2)=(w)/(2)-sqrt(0.4545 w)s_{2}=\frac{w}{2}-\sqrt{0.4545 w}
"Nodes number" "Chord Length" Diameter "Average length" "Chord length" Diameter "Average length" 50 9 7 3.94 21 7 3.97 100 13 9 5.52 43 10 5.95 500 31 22 12.44 235 21 12.30 1000 43 30 17.46 479 30 17.44 1600 53 38 22.10 773 38 22.06 2000 61 42 24.65 969 42 24.57 3000 73 54 30.38 1463 51 30.15 4000 85 64 35.15 1957 59 34.81 5000 95 67 38.91 2453 70 39.22 s_(2)=sqrt(1.8182 w) s_(2)=(w)/(2)-sqrt(0.4545 w) | Nodes <br> number | Chord <br> Length | Diameter | Average <br> length | Chord <br> length | Diameter | Average <br> length | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 50 | 9 | 7 | 3.94 | 21 | 7 | 3.97 | | 100 | 13 | 9 | 5.52 | 43 | 10 | 5.95 | | 500 | 31 | 22 | 12.44 | 235 | 21 | 12.30 | | 1000 | 43 | 30 | 17.46 | 479 | 30 | 17.44 | | 1600 | 53 | 38 | 22.10 | 773 | 38 | 22.06 | | 2000 | 61 | 42 | 24.65 | 969 | 42 | 24.57 | | 3000 | 73 | 54 | 30.38 | 1463 | 51 | 30.15 | | 4000 | 85 | 64 | 35.15 | 1957 | 59 | 34.81 | | 5000 | 95 | 67 | 38.91 | 2453 | 70 | 39.22 | | | $s_{2}=\sqrt{1.8182 w}$ | | | | $s_{2}=\frac{w}{2}-\sqrt{0.4545 w}$ | |

表 5：使用公设 3 获得的结果。

节点 数字
Nodes number| Nodes | | :---: | | number |

和弦 长度
Chord Length| Chord | | :---: | | Length |
   直径

平均 长度
Average length| Average | | :---: | | length |

和弦 长度
Chord length| Chord | | :---: | | length |
   直径

平均 长度
Average length| Average | | :---: | | length |
50 11 7 3.94 13 7 4.14
100 13 9 5.51 15 9 5.51
500 25 22 12.58 27 21 12.41
1000 35 31 17.83 37 32 17.65
1600 43 39 22.74 45 39 22.47
2000 47 44 25.60 49 43 25.28
3000 55 55 31.89 57 54 31.46
4000 65 63 36.49 67 62 36.11
5000 73 70 40.73 75 69 40.35
s 2 = | w | + 3 s 2 = | w | + 3 s_(2)=|sqrtw|+3s_{2}=|\sqrt{w}|+3 s 2 = | w | + 5 s 2 = | w | + 5 s_(2)=|sqrtw|+5s_{2}=|\sqrt{w}|+5
"Nodes number" "Chord Length" Diameter "Average length" "Chord length" Diameter "Average length" 50 11 7 3.94 13 7 4.14 100 13 9 5.51 15 9 5.51 500 25 22 12.58 27 21 12.41 1000 35 31 17.83 37 32 17.65 1600 43 39 22.74 45 39 22.47 2000 47 44 25.60 49 43 25.28 3000 55 55 31.89 57 54 31.46 4000 65 63 36.49 67 62 36.11 5000 73 70 40.73 75 69 40.35 s_(2)=|sqrtw|+3 s_(2)=|sqrtw|+5 | Nodes <br> number | Chord <br> Length | Diameter | Average <br> length | Chord <br> length | Diameter | Average <br> length | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 50 | 11 | 7 | 3.94 | 13 | 7 | 4.14 | | 100 | 13 | 9 | 5.51 | 15 | 9 | 5.51 | | 500 | 25 | 22 | 12.58 | 27 | 21 | 12.41 | | 1000 | 35 | 31 | 17.83 | 37 | 32 | 17.65 | | 1600 | 43 | 39 | 22.74 | 45 | 39 | 22.47 | | 2000 | 47 | 44 | 25.60 | 49 | 43 | 25.28 | | 3000 | 55 | 55 | 31.89 | 57 | 54 | 31.46 | | 4000 | 65 | 63 | 36.49 | 67 | 62 | 36.11 | | 5000 | 73 | 70 | 40.73 | 75 | 69 | 40.35 | | | $s_{2}=\|\sqrt{w}\|+3$ | | | | $s_{2}=\|\sqrt{w}\|+5$ | |

表 6：使用文献[8]中给出的定理获得的结果。

节点 数字
Nodes number| Nodes | | :---: | | number |
   直径

平均 长度
Average length| Average | | :---: | | length |

和弦 长度
Chord length| Chord | | :---: | | length |
   直径

平均 长度
Average length| Average | | :---: | | length |
50 6 3.87 9 7 3.94
100 8 5.45 13 9 5.51
500 18 12.17 59 20 12.24
1000 26 17.22 269 27 17.23
1600 33 21.77 97 33 21.78
2000 37 24.34 611 39 24.38
133 48 29.99
45 29.81 9 3 3 9 3 3 933\mathbf{9 3 3} 4 9 4 9 49\mathbf{4 9} 2 9 . 8 7 2 9 . 8 7 29.87\mathbf{2 9 . 8 7}
4000 52 34.43 151 53 34.46
5000 58 38.49 1293 59 38.50

参考图表 (理论)
Reference graphs (theory)| Reference graphs | | :---: | | (theory) |
   参考图表
"Nodes number" Diameter "Average length" "Chord length" Diameter "Average length" 50 6 3.87 9 7 3.94 100 8 5.45 13 9 5.51 500 18 12.17 59 20 12.24 1000 26 17.22 269 27 17.23 1600 33 21.77 97 33 21.78 2000 37 24.34 611 39 24.38 133 48 29.99 45 29.81 933 49 29.87 4000 52 34.43 151 53 34.46 5000 58 38.49 1293 59 38.50 "Reference graphs (theory)" Reference graphs | Nodes <br> number | Diameter | Average <br> length | Chord <br> length | Diameter | Average <br> length | | :---: | :---: | :---: | :---: | :---: | :---: | | 50 | 6 | 3.87 | 9 | 7 | 3.94 | | 100 | 8 | 5.45 | 13 | 9 | 5.51 | | 500 | 18 | 12.17 | 59 | 20 | 12.24 | | 1000 | 26 | 17.22 | 269 | 27 | 17.23 | | 1600 | 33 | 21.77 | 97 | 33 | 21.78 | | 2000 | 37 | 24.34 | 611 | 39 | 24.38 | | | | | 133 | 48 | 29.99 | | | 45 | 29.81 | $\mathbf{9 3 3}$ | $\mathbf{4 9}$ | $\mathbf{2 9 . 8 7}$ | | 4000 | 52 | 34.43 | 151 | 53 | 34.46 | | 5000 | 58 | 38.49 | 1293 | 59 | 38.50 | | | Reference graphs <br> (theory) | Reference graphs | | | |

表 7：参考图和真实最佳图参数。


3 四度和弦环


四阶和弦环由一个环和长度为 s 的弦组成，这些弦连接网络中的两个不同节点。四阶和弦环具有一些特性，使它们

非常适合构建互连网络。四阶和弦环的基本特征是它们能够将其中一些物理实现为最优图，而大多数则实现为理想图（这些图的定义将在本文后面给出）。这种类型的互连结构在[12, 13, 14]中得到了广泛讨论，以及在[15]中，其中这种结构被用于构建用于图像处理应用的传输器网络。

四度和弦环 ( d ( V ) = 4 ) ( d ( V ) = 4 ) (d(V)=4)(d(V)=4) 表示为 G ( w ; 1 , s ) G ( w ; 1 , s ) G(w;1,s)G(w ; 1, s) ，其中 w w ww 表示节点数量， s s ss 表示弦长，形成两个不相交的图类（例如在图 1 ) 1 ) 1)1) 中所示）：

  • 连接节点 i i ii 和 j j jj 的弦所在的类，其中 j = i ⊕ s mod w j = i ⊕ s mod w j=i o+s mod wj=i \oplus s \bmod w 生成哈密顿循环 - 哈密顿循环显然是由环的边缘形成的；

  • 在这个图中，只有一个哈密尔顿环是由环的边形成的。

定理 2 在四度的弦环 G ( w ; 1 , s ) G ( w ; 1 , s ) G(w;1,s)G(w ; 1, s) 中，任意两个节点 v i v i v_(i)v_{i} 和 v j v j v_(j)v_{j} 之间的最短路径长度（定义为边的数量）可以按如下方式计算：
d ( v i , v j ) = min { ( | k − j | div ( s ) + { ( k − j ) − [ | k − j | div ( s ) × s ] } ) ( | w + j − k | div ( s ) + { [ ( w + k ) − ( | w + j − k | div ( s ) × s ] − k } ) ( | k − j | div ( s ) + 1 ) + { [ ( j + ( | k − j | div ( s ) + 1 ) × s ] ) − k } ) ( ( | w + j − k | div ( s ) + 1 ) + [ ( k − ( ( w + k ) − ( | w + j − k | div ( s ) + 1 ) × s ) ] ) } d v i , v j = min { ( | k − j | div ( s ) + { ( k − j ) − [ | k − j | div ( s ) × s ] } ) ( | w + j − k | div ( s ) + { [ ( w + k ) − ( | w + j − k | div ( s ) × s ] − k } ) ( | k − j | div ( s ) + 1 ) + { [ ( j + ( | k − j | div ( s ) + 1 ) × s ] ) − k } ) ( ( | w + j − k | div ( s ) + 1 ) + [ ( k − ( ( w + k ) − ( | w + j − k | div ( s ) + 1 ) × s ) ] ) } {:[d(v_(i),v_(j))=min{(|k-j|div(s)+{(k-j)-[|k-j|div(s)xx s]})],[(|w+j-k|div(s)+{[(w+k)-(|w+j-k|div(s)xx s]-k})],[(|k-j|div(s)+1)+{[(j+(|k-j|div(s)+1)xx s])-k})],[((|w+j-k|div(s)+1)+[(k-((w+k)-(|w+j-k|div(s)+1)xx s)])}]:}\begin{aligned} d\left(v_{i}, v_{j}\right) & =\min \{(|k-j| \operatorname{div}(s)+\{(k-j)-[|k-j| \operatorname{div}(s) \times s]\}) \\ & (|w+j-k| \operatorname{div}(s)+\{[(w+k)-(|w+j-k| \operatorname{div}(s) \times s]-k\}) \\ & (|k-j| \operatorname{div}(s)+1)+\{[(j+(|k-j| \operatorname{div}(s)+1) \times s])-k\}) \\ & ((|w+j-k| \operatorname{div}(s)+1)+[(k-((w+k)-(|w+j-k| \operatorname{div}(s)+1) \times s)])\} \end{aligned}

证明：要找到和弦环中两个节点之间的最短路径，必须计算从节点 v i v i v_(i)v_{i} 到节点 v j v j v_(j)v_{j} 的所有可能路径。显然，在可能的情况下，路径使用长跳跃（长跳跃 = 和弦长度 s s ss ）。这条路径可以在节点 v j v j v_(j)v_{j} 的左侧或右侧结束。从我们通过长跳跃到达的节点出发，我们必须沿着环的边缘前进。到达和弦环节点的四条路径确实存在：

  • 向右移动长跳（最后一个节点的数字小于 j j jj ），

  • 向右移动长跳（最后一个节点的数字大于 j j jj ），

  • 向左移动长跳（最后一个节点的编号小于 j j jj ），

  • 向左移动长跳（最后一个节点的数字大于 j j jj ）。

要搜索图的直径，无需检查所有对 ( v j , v k ) v j , v k (v_(j),v_(k))\left(v_{j}, v_{k}\right) 的最大值，因为和弦环是对称结构。只需检查所有路径。

从一个节点到所有其他节点的长度。对于和弦环来说，一个非常重要的图参数是路径的平均长度。该参数显示了在任何两个节点之间进行通信时，平均路由需要跨越的边的数量。在和弦环中，层 ω d ω d omega_(d)\omega_{d} 包含所有可以通过长度为 d d dd 的最短路径从源节点到达的节点。层 ω d ω d omega_(d)\omega_{d} 中的节点数量（层的基数）将用 w d w d w_(d)w_{d} 表示。

路径的平均长度（平均距离） d av d av d_(av)d_{\mathrm{av}} 定义为：
d av = ∑ d = 1 d ( G ) d w d w − 1 d av = ∑ d = 1 d ( G )   d w d w − 1 d_(av)=(sum_(d=1)^(d(G))dw_(d))/(w-1)d_{\mathrm{av}}=\frac{\sum_{d=1}^{d(G)} d w_{d}}{w-1}

其中 w d w d w_(d)w_{d} 表示层 ω d ω d omega_(d)\omega_{d} 的基数， d d dd 表示层 ω d ω d omega_(d)\omega_{d} 的节点与源节点之间的距离。

在和弦环 G ( 16 ; 1 , 5 ) G ( 16 ; 1 , 5 ) G(16;1,5)G(16 ; 1,5) 中，从源节点（零节点）通过使用 d d dd 长度路径连接的节点由三个重叠层 ω d ω d omega_(d)\omega_{d} 组成（在 ω 3 ω 3 omega_(3)\omega_{3} 中，已经出现在下层的节点用粗体字表示）：

  • 层 ω 1 ω 1 omega_(1)\omega_{1} 包含通过长度为 d = 1 d = 1 d=1d=1 的路径连接的节点，即来自子集 { 1 , 5 , 11 , 15 } { 1 , 5 , 11 , 15 } {1,5,11,15}\{1,5,11,15\} 的索引节点。

  • 层 ω 2 ω 2 omega_(2)\omega_{2} 包含通过长度为 d = 2 d = 2 d=2d=2 的路径连接的节点，即来自子集 { 2 , 4 , 6 , 6 , 10 , 10 , 12 , 14 } { 2 , 4 , 6 , 6 , 10 , 10 , 12 , 14 } {2,4,6,6,10,10,12,14}\{2,4,6,6,10,10,12,14\} 的索引节点。

  • 层 ω 3 ω 3 omega_(3)\omega_{3} 包含通过长度为 d = 3 d = 3 d=3d=3 的路径连接的节点，即索引来自子集 { 3 , 3 , 7 , 7 , 9 , 9 , 13 , 13 , 1 , 5 , 1 1 , 1 5 } { 3 , 3 , 7 , 7 , 9 , 9 , 13 , 13 , 1 , 5 , 1 1 , 1 5 } {3,3,7,7,9,9,13,13,1,5,11,15}\{3,3,7,7,9,9,13,13, \mathbf{1}, \mathbf{5}, \mathbf{1 1}, \mathbf{1 5}\} 的节点。

图 9：图 G ( 16 ; 1 , 6 ) G ( 16 ; 1 , 6 ) G(16;1,6)G(16 ; 1,6) 的节点分布表，粗体表示出现在下层的节点

为了构建互连网络，我们应该选择一种网络结构拓扑，使得直径和平均路径长度达到最小值。很容易得出结论，这些参数的最小值存在于和弦环中。

所有层 ω d ω d omega_(d)\omega_{d} 是不相交的。这种类型的和弦环被称为最优图。在和弦环中，生成的层可以通过所谓的“原子”模型来描述。和弦环 G ( 25 ; 1 , 7 ) G ( 25 ; 1 , 7 ) G(25;1,7)G(25 ; 1,7) 的“原子”模型示例如图 10 所示。

图 10：最佳和弦环 G ( 25 ; 1 , 7 ) G ( 25 ; 1 , 7 ) G(25;1,7)G(25 ; 1,7) 及其“原子”模型示例

在本文的下一部分，将展示四阶弦环的最优性取决于节点数量、环的直径和弦长 s > 1 s > 1 s > 1s>1 。作为一个节点度为四、直径为 3 的最优图的例子，可以取一个具有 25 个节点和弦长为 7 的图。该图的连续层如下：
ω 1 = { 1 , 7 , 18 , 24 } ω 2 = { 2 , 6 , 8 , 11 , 14 , 17 , 19 , 23 } ω 3 = { 3 , 4 , 5 , 9 , 10 , 12 , 13 , 15 , 16 , 20 , 21 , 22 } ω 1 = { 1 , 7 , 18 , 24 } ω 2 = { 2 , 6 , 8 , 11 , 14 , 17 , 19 , 23 } ω 3 = { 3 , 4 , 5 , 9 , 10 , 12 , 13 , 15 , 16 , 20 , 21 , 22 } {:[omega_(1)={1","7","18","24}],[omega_(2)={2","6","8","11","14","17","19","23}],[omega_(3)={3","4","5","9","10","12","13","15","16","20","21","22}]:}\begin{aligned} & \omega_{1}=\{1,7,18,24\} \\ & \omega_{2}=\{2,6,8,11,14,17,19,23\} \\ & \omega_{3}=\{3,4,5,9,10,12,13,15,16,20,21,22\} \end{aligned}

各层中出现的节点数量构成算术序列。序列中的第一个表达式 a 0 − a 0 − a_(0)-a_{0}- 对应于第一层的节点数量，而差值——对应于各层节点数量的增加——均为 4。因此，可以通过解决作为算术序列求和公式的不等式来估计这个环的直径。
w − 1 ≤ d ( G ) 2 [ 2 a 0 + r ( d ( G ) − 1 ) ] w − 1 ≤ d ( G ) 2 2 a 0 + r ( d ( G ) − 1 ) w-1 <= (d(G))/(2)[2a_(0)+r(d(G)-1)]w-1 \leq \frac{d(G)}{2}\left[2 a_{0}+r(d(G)-1)\right]

通过替换 a 0 = 4 a 0 = 4 a_(0)=4a_{0}=4 和 r = 4 r = 4 r=4r=4 我们得到主要公式：
w − 1 ≤ d ( G ) [ 4 + 2 ( d ( G ) − 1 ) ] or 2 d ( G ) 2 + 2 d ( G ) + 1 ≥ w w − 1 ≤ d ( G ) [ 4 + 2 ( d ( G ) − 1 ) ]  or  2 d ( G ) 2 + 2 d ( G ) + 1 ≥ w w-1 <= d(G)[4+2(d(G)-1)]quad" or "2d(G)^(2)+2d(G)+1 >= ww-1 \leq d(G)[4+2(d(G)-1)] \quad \text { or } 2 d(G)^{2}+2 d(G)+1 \geq w


3.1 理想和最优图


每层出现的最大节点数形成数字序列。节点的总数由以下公式确定：
w i = 1 + w 1 + w 2 + … + w d ( G ) − 1 + w d ( G ) = 1 + ∑ d = 1 d ( G ) − 1 w d + w d ( G ) w i = 1 + w 1 + w 2 + … + w d ( G ) − 1 + w d ( G ) = 1 + ∑ d = 1 d ( G ) − 1   w d + w d ( G ) w_(i)=1+w_(1)+w_(2)+dots+w_(d(G)-1)+w_(d(G))=1+sum_(d=1)^(d(G)-1)w_(d)+w_(d(G))w_{i}=1+w_{1}+w_{2}+\ldots+w_{d(G)-1}+w_{d(G)}=1+\sum_{d=1}^{d(G)-1} w_{d}+w_{d(G)}

其中 w d ( G ) w d ( G ) w_(d(G))w_{d(G)} 等于最后一层的节点编号。

定义 3 满足公式(23)的和弦环，在假设编号为 1 到 d ( G ) − 1 d ( G ) − 1 d(G)-1d(G)-1 的两个层是互不相交的情况下，最后一层包含其余节点，被称为理想图。

定义 4 最后一层达到最大值的理想和弦环称为最优图。

在最优图中，节点的总数以以下形式表示：
w o = 1 + ∑ d = 1 d ( G ) w d w o = 1 + ∑ d = 1 d ( G )   w d w_(o)=1+sum_(d=1)^(d(G))w_(d)w_{o}=1+\sum_{d=1}^{d(G)} w_{d}

但平均路径长度等于：
d avo = ∑ d = 1 d ( G ) d w d w − 1 d avo = ∑ d = 1 d ( G )   d w d w − 1 d_(avo)=(sum_(d=1)^(d(G))dw_(d))/(w-1)d_{\mathrm{avo}}=\frac{\sum_{d=1}^{d(G)} d w_{d}}{w-1}

公式 (24) 和 (25) 允许以以下形式定义理想图参数：
w i = w o ( d ( G ) − 1 ) + w d ( G ) d avi = d avo ( d ( G ) − 1 ) + d ( G ) w d ( G ) w − 1 w i = w o ( d ( G ) − 1 ) + w d ( G ) d avi = d avo ( d ( G ) − 1 ) + d ( G ) w d ( G ) w − 1 {:[w_(i)=w_(o(d(G)-1))+w_(d(G))],[d_(avi)=d_(avo(d(G)-1))+(d(G)w_(d(G)))/(w-1)]:}\begin{aligned} w_{i} & =w_{o(d(G)-1)}+w_{d(G)} \\ d_{\mathrm{avi}} & =d_{\operatorname{avo}(d(G)-1)}+\frac{d(G) w_{d(G)}}{w-1} \end{aligned}

上述理想图构成了估计所研究的和弦环结构的参考点。表达式（22）描述了节点数量与和弦环直径之间的依赖关系，允许确定节点数量达到最大值的四阶和弦环。

定义 5 在四阶最优和弦环中，节点编号 w o w o w_(o)w_{o} 可以表示为直径 d ( G ) d ( G ) d(G)d(G) 的函数，形式如下：
w o = 2 d ( G ) 2 + 2 d ( G ) + 1 w o = 2 d ( G ) 2 + 2 d ( G ) + 1 w_(o)=2d(G)^(2)+2d(G)+1w_{o}=2 d(G)^{2}+2 d(G)+1

对于具有 wo 节点的最佳和弦环，直径等于：
d ( G ) = 2 w o − 1 − 1 2 d ( G ) = 2 w o − 1 − 1 2 d(G)=(sqrt(2w_(o)-1)-1)/(2)d(G)=\frac{\sqrt{2 w_{o}-1}-1}{2}

对最优和弦环的研究表明，只有在一个和弦值下才能获得最优结构，本文称之为最优和弦 − s o − s o -s_(o)-s_{o} 。在表 8 中，展示了最优和弦环的节点数量，以及不同直径的最优和弦 d ( G ) d ( G ) d(G)d(G) 。
d ( G ) d ( G ) d(G)d(G) 1 2 3 4 5 6 7 8
w o w o w_(o)w_{o} 5 13 25 41 61 85 113 145
s o s o s_(o)s_{o} 3 5 7 9 11 13 15 17
d(G) 1 2 3 4 5 6 7 8 w_(o) 5 13 25 41 61 85 113 145 s_(o) 3 5 7 9 11 13 15 17| $d(G)$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | $w_{o}$ | 5 | 13 | 25 | 41 | 61 | 85 | 113 | 145 | | $s_{o}$ | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 |
  表 8

在确定最佳和弦之前，将定义上限和下限。

定理 3 对于最优和弦环，最优和弦的界限如下：
2 d ( G ) + 2 ≥ s o ≥ 2 d ( G ) 2 d ( G ) + 2 ≥ s o ≥ 2 d ( G ) 2d(G)+2 >= s_(o) >= 2d(G)2 d(G)+2 \geq s_{o} \geq 2 d(G)

证明：在最优和弦环中，每个节点可以通过最多 d ( G ) d ( G ) d(G)d(G) 条和弦从任何其他节点到达。在环中，有些节点可以通过 d ( G ) d ( G ) d(G)d(G) 条长度为 s o s o s_(o)s_{o} 的和弦从起始节点到达。因此，在最优环中，任何两个节点之间的最大距离不能大于节点数量的一半，即：
s × d ( G ) < w s × d ( G ) < w s xx d(G) < ws \times d(G)<w

另一方面，使用 d ( G ) + 1 d ( G ) + 1 d(G)+1d(G)+1 长度为 s o s o s_(o)s_{o} 的和弦，可以通过整个环，因此表达式：
s o × [ d ( G ) + 1 ] > w s o × [ d ( G ) + 1 ] > w s_(o)xx[d(G)+1] > ws_{o} \times[d(G)+1]>w

是正确的。通过将最优和弦环的节点数放入表达式 s o × d ( G ) < w s o × d ( G ) < w s_(o)xx d(G) < ws_{o} \times d(G)<w 中，可以得到：
s o × d ( G ) < w = 2 d ( G ) 2 + 2 d ( G ) + 1 s o × d ( G ) < w = 2 d ( G ) 2 + 2 d ( G ) + 1 s_(o)xx d(G) < w=2d(G)^(2)+2d(G)+1s_{o} \times d(G)<w=2 d(G)^{2}+2 d(G)+1

由于所有计算都是在整数集合中进行的，因此以下是正确的：
s o × d ( G ) ≤ d ( G ) 2 + 2 d ( G ) s o × d ( G ) ≤ d ( G ) 2 + 2 d ( G ) s_(o)xx d(G) <= d(G)^(2)+2d(G)s_{o} \times d(G) \leq d(G)^{2}+2 d(G)

因此表达式 (29) 的左侧得到了满足。依次变换表达式 s o × [ d ( G ) + 1 ] > w s o × [ d ( G ) + 1 ] > w s_(o)xx[d(G)+1] > ws_{o} \times[d(G)+1]>w ，我们得到：
s o × [ d ( G ) + 1 ] > 2 d ( G ) 2 + 2 d ( G ) + 1 s o × [ d ( G ) + 1 ] > 2 d ( G ) 2 + 2 d ( G ) + 1 s_(o)xx[d(G)+1] > 2d(G)^(2)+2d(G)+1s_{o} \times[d(G)+1]>2 d(G)^{2}+2 d(G)+1
  和下一个：
s o × [ d ( G ) + 1 ] > 2 d ( G ) 2 + 2 d ( G ) s o × [ d ( G ) + 1 ] > 2 d ( G ) 2 + 2 d ( G ) s_(o)xx[d(G)+1] > 2d(G)^(2)+2d(G)s_{o} \times[d(G)+1]>2 d(G)^{2}+2 d(G)

所以 s o > 2 d ( G ) s o > 2 d ( G ) s_(o) > 2d(G)s_{o}>2 d(G) 。获得的表达式证明了定理 3。

找到最优弦的下界和上界后，可以找到其真实值。该值由定理 4 定义。

定理 4 在四阶最优和弦环中，最优和弦的长度等于：
s o = 2 d ( G ) + 1 s o = 2 d ( G ) + 1 s_(o)=2d(G)+1s_{o}=2 d(G)+1

证明：为了证明定理 4，必须表明在源节点（为了简化，假设其编号为 0）和弦的最终节点（编号 s o s o s_(o)s_{o} ）之间存在的所有节点，可以通过至多 d ( G ) d ( G ) d(G)d(G) 个弦从起始节点到达。到达这些节点存在三条路径：

  • 通过顺时针移动，使用长度为 1 的 d ( G ) d ( G ) d(G)d(G) 弦，这些节点的编号为 1 , … , d ( G ) 1 , … , d ( G ) 1,dots,d(G)1, \ldots, d(G) ;

  • 通过使用一个长度为 ( d ( G ) − 1 ) ( d ( G ) − 1 ) (d(G)-1)(d(G)-1) 的顺时针弦和长度为 1 − 1 − 1-1- 的逆时针弦的节点数量 s o − [ d ( G ) − 1 ] , … , s o s o − [ d ( G ) − 1 ] , … , s o s_(o)-[d(G)-1],dots,s_(o)s_{o}-[d(G)-1], \ldots, s_{o} ;

  • 通过使用 d ( G ) d ( G ) d(G)d(G) 逆时针方向的长度为 s o s o s_(o)s_{o} 的弦，达到的节点编号等于 d ( G ) + 1 d ( G ) + 1 d(G)+1d(G)+1 。

让我们考虑最后一条路线。由于我们从节点 0 开始逆时针移动，以下表达式得以满足：
w − s o × d ( G ) = d ( G ) + 1 w − s o × d ( G ) = d ( G ) + 1 w-s_(o)xx d(G)=d(G)+1w-s_{o} \times d(G)=d(G)+1

将 w w ww 替换为 2 d ( G ) 2 + 2 d ( G ) + 1 2 d ( G ) 2 + 2 d ( G ) + 1 2d(G)^(2)+2d(G)+12 d(G)^{2}+2 d(G)+1 ，我们得到：
2 d ( G ) 2 + 2 d ( G ) + 1 − s o × d ( G ) = d ( G ) + 1 2 d ( G ) 2 + 2 d ( G ) + 1 − s o × d ( G ) = d ( G ) + 1 2d(G)^(2)+2d(G)+1-s_(o)xx d(G)=d(G)+12 d(G)^{2}+2 d(G)+1-s_{o} \times d(G)=d(G)+1

最后 s o = 2 d ( G ) + 1 s o = 2 d ( G ) + 1 s_(o)=2d(G)+1s_{o}=2 d(G)+1 证明了定理 4。

定理 4 的证明也在[12]中展示过。为了证明，作者构建了平面（图 11），并分析了连接起始节点与其他节点的所有向量。从这个表中，他们得出结论，最优弦长的唯一值等于 s o = 2 d ( G ) + 1 s o = 2 d ( G ) + 1 s_(o)=2d(G)+1s_{o}=2 d(G)+1 。这个弦使得能够排列单元格，从而得到图 G ( 2 d ( G ) 2 + 2 d ( G ) + 1 ; 1 , s o ) G 2 d ( G ) 2 + 2 d ( G ) + 1 ; 1 , s o G(2d(G)2+2d(G)+1;1,s_(o))G\left(2 d(G) 2+2 d(G)+1 ; 1, s_{o}\right) 。

定理 5 四阶最优和弦环由两个哈密顿循环组成。
* 14) 214 21 2 2 C.i 24 1 2 3 4 i
. 12 13 14 IS 16 17 18 19. 20. 21 22 23
4 5 6 7 5 9 10 11 12 1.3 14 15 10
2: 2.5 2.1 1 2 3 1 3 0 7 K 9
. 16 1: 18 1) 20) 21 -- 2:) 24 1 2
R 9 10 11 12 13 |1 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13
9 30 3.1 22 73 ? 4 I ? i 1 5 幺
∵ 2 ∵ 2 :'2\because 2 1.3 1. 1.5 16 17 18 19 0 21 22 2.3 次
b. 6 ; 8 * 10 11 12 1? 14 13 16 1 : 1 : 1:1:
23 24 1 2 3 1 5 6 7 8 9 10
6 17 12 19 30 31 37 75 ? 4 1 ? 7
9 10 11 12 13 19 1.5 1 < 1 1 < 1 1 < 11<1 17 14 111 20 21
2 ∴ ∴ :.\therefore 4 3 ริ 8 j) 10 11 12 1.1 1.4
20 21 22 23 24 1 2 3 4 5 6 7
* 14) 214 21 2 2 C.i 24 1 2 3 4 i . 12 13 14 IS 16 17 18 19. 20. 21 22 23 4 5 6 7 5 9 10 11 12 1.3 14 15 10 2: 2.5 2.1 1 2 3 1 3 0 7 K 9 . 16 1: 18 1) 20) 21 -- 2:) 24 1 2 R 9 10 11 12 13 |1 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 11 12 13 9 30 3.1 22 73 ? 4 I ? i 1 5 幺 :'2 1.3 1. 1.5 16 17 18 19 0 21 22 2.3 次 b. 6 ; 8 * 10 11 12 1? 14 13 16 1: 23 24 1 2 3 1 5 6 7 8 9 10 6 17 12 19 30 31 37 75 ? 4 1 ? 7 9 10 11 12 13 19 1.5 1 < 1 17 14 111 20 21 2 :. 4 3 ริ 8 j) 10 11 12 1.1 1.4 20 21 22 23 24 1 2 3 4 5 6 7| * | 14) | 214 | 21 | 2 2 | C.i | 24 | | 1 | 2 | 3 | 4 | i | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | . | 12 | 13 | 14 | IS | 16 | 17 | 18 | 19. | 20. | 21 | 22 | 23 | | 4 | 5 | 6 | 7 | 5 | 9 | 10 | 11 | 12 | 1.3 | 14 | 15 | 10 | | 2: | 2.5 | 2.1 | | 1 | 2 | 3 | 1 | 3 | 0 | 7 | K | 9 | | . | 16 | 1: | 18 | 1) | 20) | 21 | -- | 2:) | 24 | | 1 | 2 | | R | 9 | 10 | 11 | 12 | 13 | \|1 | 15 | 16 | 17 | 18 | 19 | 20 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | 9 | 30 | 3.1 | 22 | 73 | ? 4 | | I | ? | i | 1 | 5 | 幺 | | $\because 2$ | 1.3 | 1. | 1.5 | 16 | 17 | 18 | 19 | 0 | 21 | 22 | 2.3 | 次 | | b. | 6 | ; | 8 | * | 10 | 11 | 12 | 1? | 14 | 13 | 16 | $1:$ | | 23 | 24 | | 1 | 2 | 3 | 1 | 5 | 6 | 7 | 8 | 9 | 10 | | 6 | 17 | 12 | 19 | 30 | 31 | 37 | 75 | ? 4 | | 1 | ? | 7 | | 9 | 10 | 11 | 12 | 13 | 19 | 1.5 | $1<1$ | 17 | 14 | 111 | 20 | 21 | | 2 | $\therefore$ | 4 | 3 | ริ | | 8 | j) | 10 | 11 | 12 | 1.1 | 1.4 | | 20 | 21 | 22 | 23 | 24 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 |

图 11：论文[12]中使用的补充表格

证明：由于长度为 1 的弦环是哈密顿循环，因此只需证明长度为的最优弦也生成哈密顿循环。要证明这一点，只需表明节点数 w o w o w_(o)w_{o} 和最优弦长度 s o s o s_(o)s_{o} 是互质的。通过转换表达式（27），定义最优弦环中的节点数，我们得到：
w o = 2 d ( G ) 2 + 2 d ( G ) + 1 = s o 2 + 1 2 w o = 2 d ( G ) 2 + 2 d ( G ) + 1 = s o 2 + 1 2 w_(o)=2d(G)^(2)+2d(G)+1=(s_(o)^(2)+1)/(2)w_{o}=2 d(G)^{2}+2 d(G)+1=\frac{s_{o}^{2}+1}{2}

我们需要证明不存在一个（不同于 1 的）数字可以整除数字 ( s o 2 + 1 ) s o 2 + 1 (s_(o)^(2)+1)\left(s_{o}^{2}+1\right) 和 s o s o s_(o)s_{o} 。如果 s o s o s_(o)s_{o} 是一个质数，那么定理总是成立。因此我们假设 s o s o s_(o)s_{o} 不是一个质数，并且存在一个数字 p p pp ，它可以整除 s o s o s_(o)s_{o} 。我们将证明 p p pp 不能整除 ( s o 2 + 1 ) s o 2 + 1 (s_(o)^(2)+1)\left(s_{o}^{2}+1\right) 。由于 s o s o s_(o)s_{o} 必须是奇数，因此 p p pp 也必须是奇数。让我们将 s o s o s_(o)s_{o} 写成形式为 p × q p × q p xx qp \times q 的乘积。因此 ( s o 2 + 1 ) = p 2 × q 2 + 1 s o 2 + 1 = p 2 × q 2 + 1 (s_(o)^(2)+1)=p^(2)xxq^(2)+1\left(s_{o}^{2}+1\right)=p^{2} \times q^{2}+1 。这个表达式的第一个元素被 p p pp 整除，但其余等于 1 的部分不能被 p p pp 整除。因此 ( s o 2 + 1 ) s o 2 + 1 (s_(o)^(2)+1)\left(s_{o}^{2}+1\right) 不能被 p p pp 整除，这证明了定理 5。

四阶最优和弦环的平均路径长度以以下形式表示：
d avo = 1 w o − 1 ∑ j = 0 w o − 1 d min ( v 0 , v j ) = 4 ∑ j = 1 d ( G ) j 2 w o − 1 d avo = 1 w o − 1 ∑ j = 0 w o − 1   d min v 0 , v j = 4 ∑ j = 1 d ( G )   j 2 w o − 1 d_(avo)=(1)/(w_(o)-1)sum_(j=0)^(w_(o)-1)d_(min)(v_(0),v_(j))=4(sum_(j=1)^(d(G))j^(2))/(w_(o)-1)d_{\mathrm{avo}}=\frac{1}{w_{o}-1} \sum_{j=0}^{w_{o}-1} d_{\min }\left(v_{0}, v_{j}\right)=4 \frac{\sum_{j=1}^{d(G)} j^{2}}{w_{o}-1}

通过替换表达式 ∑ j = 1 d ( G ) j 2 ∑ j = 1 d ( G )   j 2 sum_(j=1)^(d(G))j^(2)\sum_{j=1}^{d(G)} j^{2} 的值和 w o w o w_(o)w_{o} 的值，我们得到：
d avo = 4 d ( G ) [ d ( G ) + 1 ] [ 2 d ( G ) + 1 ] 6 [ 2 d ( G ) 2 + 2 d ( G ) ] = 2 d ( G ) + 1 3 = s o 3 d avo = 4 d ( G ) [ d ( G ) + 1 ] [ 2 d ( G ) + 1 ] 6 2 d ( G ) 2 + 2 d ( G ) = 2 d ( G ) + 1 3 = s o 3 d_(avo)=4(d(G)[d(G)+1][2d(G)+1])/(6[2d(G)^(2)+2d(G)])=(2d(G)+1)/(3)=(s_(o))/(3)d_{\mathrm{avo}}=4 \frac{d(G)[d(G)+1][2 d(G)+1]}{6\left[2 d(G)^{2}+2 d(G)\right]}=\frac{2 d(G)+1}{3}=\frac{s_{o}}{3}

最佳和弦环只能为特定数量的节点构建。正如我们之前所解释的，这些环形成了一组特定的理想图，可以扩展到任意数量的节点。理想图可以视为参考图——用于分析结构的虚拟或真实图，因为该图的参数，即其直径和平均路径长度，是分析结构参数的下限。

定义 6 如果和 w i w i w_(i)w_{i} 节点的弦环满足以下条件，则称其为理想图：

  • 图直径 d ( G ) i d ( G ) i d(G)_(i)d(G)_{i} 表示为：
d ( G ) i = ⌈ 2 w i − 1 − 1 2 ⌉ d ( G ) i = 2 w i − 1 − 1 2 d(G)_(i)=|~(sqrt(2w_(i)-1)-1)/(2)~|d(G)_{i}=\left\lceil\frac{\sqrt{2 w_{i}-1}-1}{2}\right\rceil

  • 在层 d 中，节点数量 w d i w d i w_(di)w_{d i} 以以下形式定义：
if d ≠ d ( G ) ⇒ w d i = 4 d if d = d ( G ) ⇒ w d i = w i − w o  if  d ≠ d ( G ) ⇒ w d i = 4 d  if  d = d ( G ) ⇒ w d i = w i − w o {:[" if "d!=d(G)quad=>quadw_(di)=4d],[" if "d=d(G)quad=>quadw_(di)=w_(i)-w_(o)]:}\begin{aligned} & \text { if } d \neq d(G) \quad \Rightarrow \quad w_{d i}=4 d \\ & \text { if } d=d(G) \quad \Rightarrow \quad w_{d i}=w_{i}-w_{o} \end{aligned}

在哪里： w i − w i − w_(i)-w_{i}- 理想图中的节点数量， w o − w o − w_(o)-w_{o}- 直径为 d ( G ) i d ( G ) i d(G)_(i)d(G)_{i} 的最优图中的节点数量？1，

  • 平均路径长度用以下形式表示：
d a v i = 2 [ d ( G ) i − 1 ] + 1 3 ( w o − 1 ) + d ( G ) i ( w i − w o ) w i − 1 = d avo w o − 1 w i − 1 + d ( G ) i w i − w o w i − 1 d a v i = 2 d ( G ) i − 1 + 1 3 w o − 1 + d ( G ) i w i − w o w i − 1 = d avo  w o − 1 w i − 1 + d ( G ) i w i − w o w i − 1 {:[d_(avi)=((2[d(G)_(i)-1]+1)/(3)(w_(o)-1)+d(G)_(i)(w_(i)-w_(o)))/(w_(i)-1)],[=d_("avo ")(w_(o)-1)/(w_(i)-1)+d(G)_(i)(w_(i)-w_(o))/(w_(i)-1)]:}\begin{aligned} d_{a v i} & =\frac{\frac{2\left[d(G)_{i}-1\right]+1}{3}\left(w_{o}-1\right)+d(G)_{i}\left(w_{i}-w_{o}\right)}{w_{i}-1} \\ & =d_{\text {avo }} \frac{w_{o}-1}{w_{i}-1}+d(G)_{i} \frac{w_{i}-w_{o}}{w_{i}-1} \end{aligned}

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

在表 9 中描绘了一些理想图的结果。

  4 结论


在本文中，讨论了三阶和四阶和弦环的性质。根据论文第一部分所示的结果，可以得出以下结论：和弦环中路径的平均长度对呼叫拒绝概率的值影响大于直径。所提出的公式给出的直径值和路径的平均长度与可获取文献中的结果相似或更好。在[16]中，提出了选择具有最佳传输能力的结构的另一种方法。在论文的第二部分，定义了两类四阶环，即理想图和最优图。实际上，最优和弦环的类别属于
w w ww s s ss d c r d c r d_(cr)d_{c r} d ( C ) d ( C ) d(C)d(C)
12 4 1.727273 3
13 5 1.666667 2
14 4 1.769231 3
15 16 1.857113 3
16 6 1.93333 3
17 457 2 3
18 457 2.658824 3
19 1578 2.111111 3
20 8 2.157595 3
21 68 2.2 3
22 6 2.238095 1
23 59 2.272727 3
24 10 2.391304 4
25 7 2.333333 3
w s d_(cr) d(C) 12 4 1.727273 3 13 5 1.666667 2 14 4 1.769231 3 15 16 1.857113 3 16 6 1.93333 3 17 457 2 3 18 457 2.658824 3 19 1578 2.111111 3 20 8 2.157595 3 21 68 2.2 3 22 6 2.238095 1 23 59 2.272727 3 24 10 2.391304 4 25 7 2.333333 3| $w$ | $s$ | $d_{c r}$ | $d(C)$ | | :---: | :---: | :---: | :---: | | 12 | 4 | 1.727273 | 3 | | 13 | 5 | 1.666667 | 2 | | 14 | 4 | 1.769231 | 3 | | 15 | 16 | 1.857113 | 3 | | 16 | 6 | 1.93333 | 3 | | 17 | 457 | 2 | 3 | | 18 | 457 | 2.658824 | 3 | | 19 | 1578 | 2.111111 | 3 | | 20 | 8 | 2.157595 | 3 | | 21 | 68 | 2.2 | 3 | | 22 | 6 | 2.238095 | 1 | | 23 | 59 | 2.272727 | 3 | | 24 | 10 | 2.391304 | 4 | | 25 | 7 | 2.333333 | 3 |
  表 9

理想环的类别。最优弦环具有严格定义的节点数量（取决于环的直径 d ( G ) d ( G ) d(G)d(G) ），并且仅存在一条长度为 2 d ( G ) + 1 2 d ( G ) + 1 2d(G)+12 d(G)+1 的最优弦，可以构建最优弦环。还证明了四阶最优弦环可以通过两个哈密顿循环构建。理想弦环则被引入作为参考图（有时仅为虚拟，例如当图具有 2 d ( G ) 2 + 2 d ( G ) 2 d ( G ) 2 + 2 d ( G ) 2d(G)^(2)+2d(G)2 d(G)^{2}+2 d(G) 个节点时 - 表 9），用于比较任何分析的弦环的属性。

  参考文献


www.alcatel.com/products.

www.alcatel.pl/technology/ngn.html。

[3] L. N. Bhuyan, “并行和分布式处理的互连网络,” IEEE 计算机, 第 20 卷, 第 6 期, 第 9-12 页, 1987.

[4] G. Kotsis, “并行处理系统的互连拓扑和路由,” 技术报告 ACPC/TR92-19, ACPC, 1992.

[5] C. Gavoille, “关于内部路由的调查。”

[6] W. Arden 和 H. Lee, “和弦环网络分析,” IEEE 计算机学报, 第 30 卷, 第 4 期, 第 291-295 页, 1981.

[7] P. Morillo, F. Comellas, 和 M. Fiol, “和弦环网络的优化,” 在通讯技术 (Q. Yasheng 和 W. Xiuying, 编), 第 295-299 页, 世界科学, 1987.

[8] M. Freire 和 H. da Silva, “波长路由和弦环网络,” 收录于《商业简报：全球光通信》，第 151-154 页，2001 年。

[9] M. Freire 和 H. da Silva, “具有和弦环和网格-环拓扑的波长路由光网络的性能比较,” ICN, 第 1 卷, 第 358-367 页, 2001.

[10] M. Freire 和 H. da Silva, “弦长对波长路由弦环网络阻塞性能的影响,” 在第五届光网络设计与建模工作会议 (ONDM?2001), (维也纳).

[11] S. Brandt, “数据分析中的统计和计算方法，”技术报告，Wydawnictwo Naukowe PWN，华沙，2002。

[12] L. Narayanan 和 J. Opatrny, “四度和弦环上的紧凑路由,” Algorithmica, 第 23 卷, 第 72-96 页, 1999.

[13] L. Narayanan, J. Opatrny, 和 D. Sotteau, “在 4 度和弦环中的全到全光路由,” Algorithmica, 第 31 卷, 第 155-178 页, 2001.

[14] A. L. Liestman, J. Opatrny, 和 M. Zaragoza, “双固定步图和三固定步图的网络属性,” 国际计算机科学基础期刊, 第 9 卷, 第 57-76 页, 1998 年。

[15] R. Browne 和 R. Hodgson, “对称四度和弦环网络,” IEEE 会议录, 第 137 卷, 第 4 期, 1990.

[16] S. Bujnowski, 分析 E 2 E 2 E^(2)\mathcal{E}^{2} 合成均匀结构网络连接通信模块。博士论文，ATR 比得哥什，2003 年。

  1. *Inst. Telekom. ATR 波兰。电子邮件：antoni.zabludowski@atr.bydgoszcz.pl