蝴蝶网络的抗毁性研究
Research on Invulnerability of Butterfly Network
摘要: 一个非完全连通图G的毁裂度定义为r(G)=max{ω(G−X)-|X|-τ(G−X):X⊂V(G),ω(G−X)>1}，其中ω(G−X)为G−X的分支数，τ(G−X)为G−X最大分支的阶数。作为网络抗毁性参数之一，毁裂度r(G)既能反映网络图G的破坏难度，又可反映破坏程度。在某种程度上，它代表了破坏网络所需的工作和破坏网络的严重程度之间的平衡。在本文中，我们确定了蝴蝶网络与增广蝴蝶网络的毁裂度。
Abstract:
The destruction degree of an incompletely connected graph G is defined as r(G)=max{ω(G−X)-|X|-τ(G−X):X⊂V(G),ω(G−X)>1}, where ω(G−X) is the number of branches of G−X, and τ(G−X) is the order of the largest branch of G−X. As one of the pa-rameters of network invulnerability, the degree of destruction r(G) can reflect the network. The damage difficulty of graph G can reflect the degree of damage. To some extent, it represents the balance between the work required to destroy the network and the severity of the damage to the network. In this paper, we determine the butterfly network and augmented disintegration of butterfly network.
参考文献
|
[1]
|
Li, F. and Li, X. (2004) Computing the Rupture Degrees of Graphs. Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN, Hong Kong, 368-373.
|
|
[2]
|
Li, Y., Zhang, S. and Li, X. (2005) The Rupture Degree of Graphs. International Journal of Computer Mathematics, 82,793-803. [Google Scholar] [CrossRef]
|
|
[3]
|
Li, Y. (2006) An Algorithm for Computing the Rupture Degree of Tree. Computer Engineering and Applications, 42, 52-54.
|
|
[4]
|
Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan London and Elsevier, New York. [Google Scholar] [CrossRef]
|
|
[5]
|
Lakshmivarahan, S., Jwo, J.S. and Dhall, S.K. (1993) Symmetry in Interconnection Networks Based on Cayley Graphs of Permutation Groups. Survey, Parallel Computing, 19, 361-407. [Google Scholar] [CrossRef]
|
|
[6]
|
Biggs, N. (1992) Algebraic Graph Theory. Cambridge University Press, New York.
|