主題
Search

雙連通圖


雙連通圖是一個連通圖,它沒有割點(Skiena 1990, p. 175)。 對於頂點數多於兩個的圖,一個等價的定義是圖G頂點連通度κ(G)≥2

BiconnectedGraphs

頂點數為 n=1, 2, ... 的雙連通簡單圖的數量分別是 0, 0, 1, 3, 10, 56, 468, ... (參見 OEIS A002218)。 上面展示了這些圖的前幾個。

頂點數大於等於 2 的極大連通圖被稱為或不可分圖(參見 Harary 1994, p. 26)。 雙連通圖與密切相關。 如果一個的頂點數多於兩個,那麼它是雙連通的(West 2000, p. 155)。 反之,頂點數大於等於 2 的雙連通圖是

NotBiconnectedGraph

上面展示了一些連通但不雙連通的圖。 這樣的圖被稱為 1-連通圖,頂點數為 n=1, 2, ... 的 1-連通圖的數量分別為 1, 1, 1, 3, 11, 56, 385, ... (OEIS A052442)。

可以使用 Wolfram 語言測試圖的雙連通性,使用KVertexConnectedGraphQ[g, 2] 或VertexConnectivity[g] >1。 可以使用以下命令獲取雙連通圖的集合GraphData["Biconnected].

任何包含度為 1 的節點的圖都不可能是雙連通的。 所有哈密頓圖都是雙連通的(Skiena 1990, p. 177),但反之不一定成立。 特別是,非雙連通圖自動是非哈密頓圖,這可以透過注意到如果刪除一個割點後留下哈密頓路徑,這將意味著不連通的圖是連通的。 下表總結了一些雙連通但非哈密頓的命名圖。


參見

割點, , 連通圖, k-連通圖

在 中探索

參考文獻

Harary, F. 圖論。 Reading, MA: Addison-Wesley, 1994.Skiena, S. 實現離散數學:使用 Mathematica 的組合數學和圖論。 Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. 序列 A002218/M2873 和 A052442,來自“整數序列線上百科全書”。

在 上被引用

雙連通圖

請引用本文為

Weisstein, Eric W. “雙連通圖。” 來自 Web 資源。 https://mathworld.tw/BiconnectedGraph.html

學科分類