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

计算机工程与科学

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

周敏1，王加阳1，龙陈锋2，陈林书1

（1.中南大学信息科学与工程学院，湖南长沙 410083;2.湖南农业大学信息科学技术学院，湖南长沙 410128）

收稿日期:2015-09-29 修回日期:2016-03-25 出版日期:2017-08-25 发布日期:2017-08-25
基金资助:
国家自然科学基金（61173052）；湖南省自然科学基金（14JJ4007）；湖南省教育厅优秀青年项目(12B061)

Graph connectivity based on hierarchical

quotient space chain

ZHOU Min1，WANG Jia-yang1，LONG Chen-feng2，CHEN Lin-shu1

（1.School of Information Science and Engineering,Central South University,Changsha 410083；

2.School of Information Science Technology,Hunan Agricultural University,Changsha 410128,China）

Received:2015-09-29 Revised:2016-03-25 Online:2017-08-25 Published:2017-08-25

摘要/Abstract

摘要：

图连通性的判定对于路径规划中任意两点间路径相通性判断以及连通块的划分都具有重要意义。从节点的边连通关系着手分析图的结构层次，通过构建图的分层递阶商空间链，分析不同层次商空间链中各节点分布情况，得出新的图连通性判定方法。与以往各判定方法相比，该方法具有易实现、效率高的优点，不仅能有效地判定图是否连通，还能确定图的连通分支数以及哪些节点位于同一连通分支中。

关键词: 分层递阶商空间链, 图连通性, 连通分支, 等价划分

Abstract:

Judgment of graph connectivity is significant for judging the connectivity between any two points and the division of the connecting block in path planning. We analyze graph hierarchy by starting from edge connectivity relationship, and obtain the distribution of each node on different levels in the chain by constructing a graph hierarchical quotient space chain, thus achieving a new method of judging graph connectivity. Compared with conventional methods, it has the advantages of high efficiency and is easy to implement. It can not only effectively determine graph connectivity but also the branch number, and identify which node is located in the same connected component in the graph.

Key words: hierarchical quotient space chain, graph connectivity, connected component, equivalence partition

周敏1，王加阳1，龙陈锋2，陈林书1. 基于分层递阶商空间链的图连通性研究[J]. 计算机工程与科学.

ZHOU Min1，WANG Jia-yang1，LONG Chen-feng2，CHEN Lin-shu1.

Graph connectivity based on hierarchical

quotient space chain

[J]. Computer Engineering & Science.