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

Graph connectivity based on hierarchical quotient space chain

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

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.