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

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

单位：中南大学信息科学与工程学院; 湖南长沙410083; 湖南农业大学信息科学技术学院; 湖南长沙410128