几个著名网络的限长路径

设给出了（h,ψ）-η限长路径问题是图论中的Menger定理的变形和推广，在实时容错网络设计和分析中有重要意义。对于给定的正整数d,Ad(D)表示网络D中任何距离至少为2的两顶点之间内点不交且长度都不超过d的路的最大条数；Bd(D)表示D的顶点子集B中的最小顶点数使得D－B的直径大于d.已证明确定Ad(D)的问题是NPC问题，而且显然有不等式Ad(D)≤Bd(D)。本文考虑D为超立方体网络、De Bruijn网络和Kautz网络，对d的不同值确定了Ad(D)及Bd(D),而且均有Ad(D)=Bd(D)。

On Bounded Paths in Some Networks

The problem of paths with bounded length, being a variation and a generalization of Menger's theorem, is of very important significance in the design and analysis of real-time or fault-tolerant interconnection networks. For a given positive integer d, the symbol Ad(D) denotes the maximum number of internally disjoint paths of length at most d between any two vertices with distance at least two in the network D; the symbol Bd(D) denotes the minimum number of vertices whose deletion results in diameter larger than d. Obviously, Ad(D) ≤ Bd(D) and it has been shown to determine the value of Ad(D) is NP-complete. In the present paper, three well-known networks, hypercubes, de Bruijn and Kautz, are considered and the values of Ad(D) and Bd(D) are determined, which show Ad(D) = Bd(D).