基于分层递阶商空间链的图连通性研究

发布时间：2018-04-17 10:26

  本文选题：分层递阶商空间链 + 图连通性　； 参考：《计算机工程与科学》2017年08期

【摘要】：图连通性的判定对于路径规划中任意两点间路径相通性判断以及连通块的划分都具有重要意义。从节点的边连通关系着手分析图的结构层次,通过构建图的分层递阶商空间链,分析不同层次商空间链中各节点分布情况,得出新的图连通性判定方法。与以往各判定方法相比,该方法具有易实现、效率高的优点,不仅能有效地判定图是否连通,还能确定图的连通分支数以及哪些节点位于同一连通分支中。
[Abstract]:The determination of graph connectivity is of great significance to the judgment of path commonality between any two points in path planning and the division of connected blocks.Starting from the edge connectivity relation of nodes, this paper analyzes the structure level of graph, and by constructing the hierarchical quotient space chain of graph, analyzes the distribution of each node in the quotient space chain of different levels, and obtains a new method of determining graph connectivity.Compared with the previous methods, this method has the advantages of easy implementation and high efficiency. It can not only effectively determine whether a graph is connected, but also determine the number of connected branches of a graph and which nodes are located in the same connected branch.
【作者单位】： 中南大学信息科学与工程学院;湖南农业大学信息科学技术学院;
【基金】：国家自然科学基金(61173052) 湖南省自然科学基金(14JJ4007) 湖南省教育厅优秀青年项目(12B061)
【分类号】：O157.5

【相似文献】

相关期刊论文 前6条

1 马睿;朱建冲;;一种有向概率图连通性仿真算法[J];舰船电子工程;2011年11期

2 胡欣;刘明;田菲;;关于树的和连通指数[J];空军雷达学院学报;2010年04期

3 王志平,赵连昌;图的离散度[J];大连海事大学学报;1999年04期

4 李学良;Balinski和Russakoff关于分配多面体图连通性猜想的证明[J];数学年刊A辑(中文版);1991年05期

5 王志平,任光,赵连昌,李彩荣,朱全英;离散度与网络图的结构[J];大连海事大学学报;2000年02期

6 欧阳克智,欧阳克毅,于文池;图的相对断裂度[J];兰州大学学报;1993年03期

相关会议论文 前1条

1 徐海涛;张绍飞;;无向图连通性的算法研究与设计[A];数学·物理·力学·高新技术研究进展——1998（7）卷——中国数学力学物理学高新技术交叉研究会第7届学术研讨会论文集[C];1998年

，

本文编号：1763205