-
摘要: 针对无向网络拓扑设计中存在的定义适用性差或设计目标单一等问题, 本文得到如下主要结果: 1)给出一种新的网络能量定义; 据此并结合Wiener指数, 给出一种新的网络效率定义. 2)给出简单无向连通图的对称性定义及其度量指标; 首次给出无向高效网络和无向$ k{\text{-}}$连通高效网络的定义, 证明了这两种网络的存在性, 并证明了无向$ k{\text{-}}$连通高效网络是连通度和效率均为最大值且边数达到最小值的网络. 3)给出设计无向$ k{\text{-}}$连通高效网络的若干指导原则, 并构造一组无向$ k{\text{-}}$连通高效网络. 上述创新性成果可为无向网络的拓扑结构优化设计提供理论依据和技术支撑.Abstract: In response to the problems of poor definition applicability or single design objective existing in the undirected network topology design, this paper obtains the following main results: 1) A new definition of network energy is proposed; based on which and according to the Wiener index, a new definition of network efficiency is proposed. 2) The definition and measurement indicator of the symmetry of simple undirected connected graphs are presented; The definitions of undirected efficient network and undirected $k{\text{-}} $connected efficient network are proposed for the first time, whose existences are proved, and the conclusion that the undirected $ k{\text{-}} $connected efficient network is such a network, whose connectivity and efficiency are both maximized while the number of its edges is minimized, is proved. 3) Several guiding principles are given to design the undirected $ k{\text{-}} $connected efficient network, on which basis a set of these networks is constructed. The above innovative results can provide theoretical basis and technical support for the topology optimization design of undirected networks.
-
图 1 Harary图$H_{k,\; n}$和$k{\text{-}} $连通高效网络$W_{k,\; n}$示例图
Fig. 1 Harary graph $H_{k,\; n} $ and example diagram $W_{k,\; n} $ of $k{\text{-}} $connected efficient network
表 1 $ {H}_{k,\;n} $相关参数列表
Table 1 The relevant parameters of $ {H}_{k,\;n} $
$ n $ $ k $ $ d({H}_{k,\;n}) $ $ w({H}_{k,\;n}) $ $ {e}_{w}({H}_{k,\;n})\, (\%)$ $ \psi ({H}_{k,\;n}) $ 10 3 3 170 52.9 1 11 3 3 216 50.9 3 12 3 3 276 47.8 1 13 3 4 342 45.6 4 14 3 4 434 41.9 1 15 3 4 516 40.7 4 10 4 3 150 60.0 1 11 4 3 198 55.6 1 12 4 3 252 52.4 1 13 4 3 312 50.0 1 14 4 4 392 46.4 1 15 4 4 480 43.8 1 
下载: 导出CSV
表 2 $ {W}_{k,\;n} $相关参数列表
Table 2 The relevant parameters of $ {W}_{k,\;n} $
$ n $ $ k $ $ d({W}_{k,\;n}) $ $ w({W}_{k,\;n}) $ $ {e}_{w}({W}_{k,\;n})\,(\%) $ $ \psi ({W}_{k,\;n}) $ 10 3 2 150 60.0 1 11 3 3 196 56.1 4 12 3 3 256 51.6 2 13 3 3 316 49.4 3 14 3 3 378 48.1 1 15 3 3 442 47.5 3 10 4 2 140 64.3 1 11 4 2 176 62.5 1 12 4 2 216 61.1 1 13 4 2 260 60.0 1 14 4 3 314 58.0 2 15 4 3 390 53.8 1
下载: 导出CSV
表 3 $ {e}_{w}({W}_{k,\;n}) $的计算结果 (%)
Table 3 Calculation results of $ {e}_{w}({W}_{k,\;n}) $ (%)
$ n $ $ {e}_{w}({W}_{1,\;n}) $ $ {e}_{w}({W}_{2,\;n}) $ $ {e}_{w}({W}_{n/2,\;n}) $ 10 55.6 36.0 69.2 20 52.6 19.0 67.9 30 51.7 12.9 67.4 40 51.3 9.8 67.2 50 51.0 7.8 67.1 60 50.8 6.6 67.0
下载: 导出CSV
-
[1] Elspas B. Topological constraints on interconnection-limited logic. In: Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design. Princeton, USA: IEEE, 1964. 133−137 [2] Erdös P, Fajtlowicz S, Hoffman A J. Maximum degree in graphs of diameter 2. Networks, 1980, 10(1): 87−90 [3] West D B. Introduction to Graph Theory (Second edition). Upper Saddle River: Prentice-Hall, Inc., 2001. [4] Gutman I. Bounds for total ${\pi}{\text{-}}{{\mathrm{electron}}}$ energy. Chemical Physics Letters, 1974, 24(2): 283−285 [5] Mowshowitz A. The characteristic polynomial of a graph. Journal of Combinatorial Theory, Series B, 1972, 12(2): 177−193 [6] Koolen J H, Moulton V. Maximal energy graphs. Advances in Applied Mathematics, 2001, 26(1): 47−52 [7] Latora V, Marchiori M. Efficient behavior of small-world networks. Physical Review Letters, 2001, 87(19): Article No. 198701 [8] 张胜, 戴维凯, 吴锋, 蓝文祥. 基于分形特性的复杂网络全局效率估计方法. 通信学报, 2020, 41(7): 204−212Zhang Sheng, Dai Wei-Kai, Wu Feng, Lan Wen-Xiang. Global efficiency estimation method of complex network based on fractal property. Journal on Communications, 2020, 41(7): 204−212 [9] Avena-Koenigsberger A, Misic B, Sporns O. Communication dynamics in complex brain networks. Nature Reviews Neuroscience, 2018, 19(1): 17−33 [10] 王树禾. 图论. 北京: 科学出版社, 2004.Wang Shu-He. Graph Theory. Beijing: Science Press, 2004. [11] 殷剑宏, 吴开亚. 图论及其算法. 合肥: 中国科学技术大学出版社, 2003.Yin Jian-Hong, Wu Kai-Ya. Graph Theory and Its Algorithm. Hefei: University of Science and Technology of China Press, 2003. [12] 王卓, 王成红. 简单无向图的同构判定方法. 自动化学报, 2023, 49(9): 1878−1888Wang Zhuo, Wang Cheng-Hong. Isomorphism determination methods for simple undirected graphs. Acta Automatica Sinica, 2023, 49(9): 1878−1888 [13] 陈景良, 陈向晖. 特殊矩阵. 北京: 清华大学出版社, 2001.Chen Jing-Liang, Chen Xiang-Hui. Special Matrices. Beijing: Tsinghua University Press, 2001. [14] 匡继昌. 常用不等式. 第2版. 长沙: 湖南教育出版社, 1993.Kuang Ji-Chang. Applied Inequalities (Second edition). Changsha: Hunan Education Publishing House, 1993. [15] Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 1989, 38(4): 555−566 -
下载:
图(1) / 表(3)
计量
- 文章访问数: 101
- HTML全文浏览量: 34
- PDF下载量: 6
- 被引次数: 0
