摘要
图连通性的判定对于路径规划中任意两点间路径相通性判断以及连通块的划分都具有重要意义。从节点的边连通关系着手分析图的结构层次,通过构建图的分层递阶商空间链,分析不同层次商空间链中各节点分布情况,得出新的图连通性判定方法。与以往各判定方法相比,该方法具有易实现、效率高的优点,不仅能有效地判定图是否连通,还能确定图的连通分支数以及哪些节点位于同一连通分支中。
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.
出处
《计算机工程与科学》
CSCD
北大核心
2017年第8期1471-1475,共5页
Computer Engineering & Science
基金
国家自然科学基金(61173052)
湖南省自然科学基金(14JJ4007)
湖南省教育厅优秀青年项目(12B061)
关键词
分层递阶商空间链
图连通性
连通分支
等价划分
hierarchical quotient space chain
graph connectivity
connected component
equivalence partition