| 基于分层递阶商空间链的图连通性研究 |
| |
| 引用本文： | 周敏,王加阳,龙陈锋,陈林书.基于分层递阶商空间链的图连通性研究[J].计算机工程与科学,2017,39(8):1471-1475. |
| |
| 作者姓名： | 周敏 王加阳 龙陈锋 陈林书 |
| |
| 作者单位： | ;1.中南大学信息科学与工程学院;2.湖南农业大学信息科学技术学院 |
| |
| 基金项目： | 国家自然科学基金（61173052）；湖南省自然科学基金（14JJ4007）；湖南省教育厅优秀青年项目(12B061) |
| |
| 摘 要： | 图连通性的判定对于路径规划中任意两点间路径相通性判断以及连通块的划分都具有重要意义。从节点的边连通关系着手分析图的结构层次,通过构建图的分层递阶商空间链,分析不同层次商空间链中各节点分布情况,得出新的图连通性判定方法。与以往各判定方法相比,该方法具有易实现、效率高的优点,不仅能有效地判定图是否连通,还能确定图的连通分支数以及哪些节点位于同一连通分支中。
|
| 关 键 词： | 分层递阶商空间链 图连通性 连通分支 等价划分 |
| 收稿时间： | 2015-09-29 |
| 修稿时间： | 2017-08-25 |
Graph connectivity based on hierarchical
quotient space chain |
| |
| ZHOU Min,WANG Jia-yang,LONG Chen-feng,CHEN Lin-shu.Graph connectivity based on hierarchical
quotient space chain[J].Computer Engineering & Science,2017,39(8):1471-1475. |
| |
| Authors: | ZHOU Min WANG Jia-yang LONG Chen-feng CHEN Lin-shu |
| |
| Affiliation: | （1.School of Information Science and Engineering,Central South University,Changsha 410083；
2.School of Information Science Technology,Hunan Agricultural University,Changsha 410128,China）
|
| |
| 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. |
| |
| Keywords: | hierarchical quotient space chain graph connectivity connected component equivalence partition |
|
| 点击此处可从《计算机工程与科学》浏览原始摘要信息 |
|
点击此处可从《计算机工程与科学》下载全文 |
|
