主題
Search

邊連通度

圖的邊連通度，也稱為線連通度，是從圖 G 中刪除後會使 G 斷開連線的最小邊數 lambda(G)。換句話說，它是最小邊割的大小。非連通圖的邊連通度因此為 0，而具有圖橋的連通圖的邊連通度為 1。

設 kappa(G) 為圖 G 的頂點連通度，delta(G) 為其最小度，則對於任何圖，

kappa(G)<=lambda(G)<=delta(G)

(Whitney 1932, Harary 1994, p. 43)。

連通無橋圖是 2-邊連通的。

圖的邊連通度可以使用 Wolfram 語言中的以下命令確定EdgeConnectivity[g]。 許多命名圖的預計算邊連通度可以使用以下命令獲得GraphData[graph，"EdgeConnectivity"].

另請參見

連通圖、迴圈邊連通度、非連通圖、邊割、k-邊連通圖、最小邊割、頂點連通度

使用 探索

參考文獻

Harary, F. 圖論。 Reading, MA: Addison-Wesley, p. 43, 1994。Skiena, S. 離散數學實施：使用 Mathematica 的組合數學和圖論。 Reading, MA: Addison-Wesley, pp. 177-178, 1990。Whitney, H. “全等圖和圖的連通性。” Amer. J. Math. 54, 150-168, 1932。

在 上被引用

邊連通度

請引用為

Weisstein, Eric W. “邊連通度。” 來自 —— 資源。 https://mathworld.tw/EdgeConnectivity.html

主題分類