本文選題：分層遞階商空間鏈 + 圖連通性　； 參考：《計算機工程與科學(xué)》2017年08期

【摘要】：圖連通性的判定對于路徑規(guī)劃中任意兩點間路徑相通性判斷以及連通塊的劃分都具有重要意義。從節(jié)點的邊連通關(guān)系著手分析圖的結(jié)構(gòu)層次,通過構(gòu)建圖的分層遞階商空間鏈,分析不同層次商空間鏈中各節(jié)點分布情況,得出新的圖連通性判定方法。與以往各判定方法相比,該方法具有易實現(xiàn)、效率高的優(yōu)點,不僅能有效地判定圖是否連通,還能確定圖的連通分支數(shù)以及哪些節(jié)點位于同一連通分支中。
[Abstract]:The determination of graph connectivity is of great significance to the judgment of path commonality between any two points in path planning and the division of connected blocks.Starting from the edge connectivity relation of nodes, this paper analyzes the structure level of graph, and by constructing the hierarchical quotient space chain of graph, analyzes the distribution of each node in the quotient space chain of different levels, and obtains a new method of determining graph connectivity.Compared with the previous methods, this method has the advantages of easy implementation and high efficiency. It can not only effectively determine whether a graph is connected, but also determine the number of connected branches of a graph and which nodes are located in the same connected branch.
【作者單位】： 中南大學(xué)信息科學(xué)與工程學(xué)院;湖南農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院;
【基金】：國家自然科學(xué)基金(61173052) 湖南省自然科學(xué)基金(14JJ4007) 湖南省教育廳優(yōu)秀青年項目(12B061)
【分類號】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前6條

1 馬睿;朱建沖;;一種有向概率圖連通性仿真算法[J];艦船電子工程;2011年11期

2 胡欣;劉明;田菲;;關(guān)于樹的和連通指數(shù)[J];空軍雷達(dá)學(xué)院學(xué)報;2010年04期

3 王志平,趙連昌;圖的離散度[J];大連海事大學(xué)學(xué)報;1999年04期

4 李學(xué)良;Balinski和Russakoff關(guān)于分配多面體圖連通性猜想的證明[J];數(shù)學(xué)年刊A輯(中文版);1991年05期

5 王志平,任光,趙連昌,李彩榮,朱全英;離散度與網(wǎng)絡(luò)圖的結(jié)構(gòu)[J];大連海事大學(xué)學(xué)報;2000年02期

6 歐陽克智,歐陽克毅,于文池;圖的相對斷裂度[J];蘭州大學(xué)學(xué)報;1993年03期

相關(guān)會議論文 前1條

1 徐海濤;張紹飛;;無向圖連通性的算法研究與設(shè)計[A];數(shù)學(xué)·物理·力學(xué)·高新技術(shù)研究進(jìn)展——1998（7）卷——中國數(shù)學(xué)力學(xué)物理學(xué)高新技術(shù)交叉研究會第7屆學(xué)術(shù)研討會論文集[C];1998年

，

本文編號：1763205