无向<i>k</i>　-连通高效网络

王卓; 王成红

doi:10.16383/j.aas.c250547

无向k　-连通高效网络

doi: 10.16383/j.aas.c250547

王卓^1,,
王成红^2,

1.
北京航空航天大学仪器科学与光电工程学院北京 100191
2.
中国自动化学会理事会北京 100190

基金项目: 广东省重点领域研发计划(2021B0101410005), 国家自然科学基金(61673041)资助

详细信息

作者简介:
王卓：北京航空航天大学仪器科学与光电工程学院教授. 2013年获得美国伊利诺伊大学芝加哥分校电子与计算机工程系博士学位. 主要研究方向为基于数据的系统分析与控制方法和网络理论. 本文通信作者. E-mail: zhuowang@buaa.edu.cn

王成红：中国自动化学会常务委员会研究员. 1997年获博士学位. 主要研究方向为运筹学与控制论, 图论及其应用. E-mail: chenghwang@163.com

计量
- 文章访问数: 8
- HTML全文浏览量: 4
- 被引次数: 0
出版历程
- 收稿日期: 2025-10-15
- 录用日期: 2026-03-16
- 网络出版日期: 2026-06-30

Undirected k　-Connected Efficient Network

WANG Zhuo^1
,,
WANG Cheng-Hong^2
,

1.
School of Instrumentation and Optoelectronic Engineering, Beihang University, Beijing 100191
2.
Council of Chinese Association of Automation, Beijing 100190

Funds: Supported by Key Area Research and Development Program of Guangdong Province (2021B0101410005) and National Natural Science Foundation of China (61673041)

More Information

Author Bio:
WANG Zhuo　Professor at the School of Instrumentation and Optoelectronic Engineering, Beihang University. He received his Ph.D. degree in Electrical and Computer Engineering Department, University of Illinois at Chicago, USA in 2013. His main research interest covers data-based system analysis and control methods, as well as network theory. Corresponding author of this paper

WANG Cheng-Hong Fellow Researcher of the Council of Chinese Association of Automation. He received the Ph.D. degree in 1997. His main research interest covers operational research and cybernetics, as well as graph theory and its applications

摘要

摘要: 针对无向网络拓扑设计中存在着定义适用性差或设计目标单一等问题, 本文得到了如下主要结果1)给出了一种新的网络能量定义; 借此并基于Wiener指数, 给出了一种新的网络效率定义; 2)给出了简单无向连通图的对称性定义及其度量指标; 首次给出了无向高效网络和无向$ k{\text{-}}$连通高效网络的定义, 证明了这两种网络的存在性, 并证明了无向$ k{\text{-}}$连通高效网络是连通度和效率均为最大值且边数达到最小值的网络; 3)给出了设计无向$ k{\text{-}}$连通高效网络的若干指导原则, 并构造了一组无向$ k{\text{-}}$连通高效网络. 上述创新性成果可为无向网络的拓扑结构优化设计提供理论依据和技术支撑.
- 无向网络拓扑设计 /
- Wiener指数 /
- 网络效率 /
- 图的对称性 /
- k　-连通高效网络
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.
- Undirected network topology design /
- Wiener index /
- network efficiency /
- symmetry of the graph /
- k　-connected efficient network

HTML全文

图 1 Harary图$H_{k,\; n}$和$k $-连通高效网络$W_{k,\; n}$示例图

第1列: $H_{3,\;10},\;H_{3,\;11},\, H_{3,\;12},\;H_{3,\;13},\;H_{3,\;14},\;H_{3,\;15}$; 第2列: $H_{3,\;10},\;H_{3,\;11},\, H_{3,\;12},\;H_{3,\;13},\;H_{3,\;14},\;H_{3,\;15} $; 第3列: $H_{3,\;10},\;H_{3,\;11},\, H_{3,\;12},\;H_{3,\;13},\;H_{3,\;14},\;H_{3,\;15} $; 第4列: $H_{3,\;10},\;H_{3,\;11},\, H_{3,\;12},\;H_{3,\;13},\;H_{3,\;14},\;H_{3,\;15} $.

Fig. 1 Harary Graph $H_{k,\; n} $ and example diagram $W_{k,\; n} $ of $k $-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 result 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

参考文献(15)

[1]	B. Elspas. Topological constraints on interconnection-limited logic. In proceedings of the 5^th Annual symposium on Switching Circuit Theory and Logic Design, 1964, 5: 133−147 doi: 10.1109/swct.1964.27
[2]	P. Erdo-s, S. Fajtlowicz and A. J. Homan. Maximum degree in graphs of diameter2. Networks, 1980, 10: 87−90
[3]	Douglas B West. Introduction to Graph Theory. Second Edition. Upper Saddle River, New Jersey 07458: Pearson Education, Inc., 2018
[4]	I. Gutman. Bounds for total ${ \pi} $-electron energy. 1974, 24: 283−285
[5]	Jack H. Koolen. Maximal energy graphs. Advances in Applied Mathematics, 2001, 26: 47−52 doi: 10.1006/aama.2000.0705
[6]	Mowshowitz A. The characteristic polynomial of a graph. Journal of Combinatorial Theory Series B, 1972, 12(2): 177−193 doi: 10.1016/0095-8956(72)90023-8
[7]	V. Latora, M. Marchiori. Efficient behavior of small-world networks. Physical Review Letters, 2001, 87(19): 3−6 doi: 10.1103/physrevlett.87.198701
[8]	张胜, 戴维凯, 吴锋, 蓝文祥. 基于分形特性的复杂网络全局效率估计方法. 通信学报, 2020, 41(7) Zhang 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
[9]	Avena-Koenigsberger A, Misic B, Sporns O. Communi-cation dynamics in complex brain networks. Nature Reviews Neuroscience, 2018, 19(1): 17−33
[10]	王树禾. 图论. 北京市东城区东皇城根北街16号: 科学出版社, 2004 Wang Shu-He. Graph Theory. 16 Donghuangcheng gen North Street, Dongcheng District, Beijing: Science Press, 2004 (in Chinese)
[11]	殷剑宏, 吴开亚. 图论及其算法. 安徽省合肥市金寨路70号: 中国科学技术大学出版社, 2003 Yin Jian-Hong, Wu Kai-Ya. Graph Theory and Its Algorithms. 70 Jinzhai Road, Hefei City, Anhui Province: Press of University of Science and Technology of China, 2003 (in Chinese)
[12]	王卓, 王成红. 简单无向图的同构判定方法. 自动化学报, 2023, 49(9): 1878−1888 doi: 10.16383/j.aas.c230025 Wang Zhuo, Wang Cheng-Hong. Isomorphism determination methods for simple undirected graphs. Acta Automatica Sinica, 2023, 49(9): 1878−1888 doi: 10.16383/j.aas.c230025
[13]	陈景良, 陈向晖. 特殊矩阵. 北京市海淀区清华园街道双清路30号: 清华大学出版社, 2001 Chen Jing-Liang, Chen Xiang-Hui. Special Matrices. 30 Shuangqing Road, Haidian District, Beijing: Tsinghua University Press, 2001 (in Chinese)
[14]	匡继昌. 常用不等式. 湖南教育出版社, 1993 Kuang Ji-Chang. Applied Inequalities. Hunan Education Publishing Press, 1993 (in Chinese)
[15]	S. B. Akers, B. Krishnamurthy. A group-theoretic method for symmetric interconnection networks. IEEE Transactions on Computers, 1989, 38: 555−565