判斷一個無向圖是否連通圖的方法
摘要：判斷圖的連通性質是一個經典的圖論問題,也是應用圖挖掘和圖分解的重要子問題。除了圖分解,圖的連通性質也被運用于追蹤疾病的傳播、大型系統設計、社交網絡分析和＂Cayley圖＂的一些理論研究。首先綜述幾種重要的判斷無向圖是否是連通圖的方法,例如廣度優先搜索、深度優先搜索和圖的拉普拉斯矩陣的特征值。此外,提出一些新方法,例如鄰接矩陣的指數和及邏輯和,其中邏輯和是基于搜索方法的計算形式。在隨機生成的超過10 000個頂點的圖上測試了所有方法,結果顯示廣度優先搜索和邏輯和方法在超過100個頂點的大圖上效果最好,邏輯和最快。
注: 保護知識產權,如需閱讀全文請聯系中國科學院大學學報雜志社
相關推薦
更多
