• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

Graph connectivity based on hierarchical
quotient space chain

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

  1. (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:

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