圖強度

關於圖的強度有幾種定義。

Harary 和 Palmer（1959）以及 Harary 和 Palmer（1973，p. 66）將樹的強度定義為任意頂點對之間邊的最大數量。此定義對應於樹的圖直徑。

Harary 和 Palmer（1973，p. 117）將多重圖的強度定義為連線任意兩個相鄰頂點的邊的最大數量。

Capobianco 和 Molluzzo（1979-1980）將可分圖的強度定義為 ，其中圖的強度向量 定義為向量 ，其中 是刪除頂點 後連通分量計數的增加量。例如，上面圖示的圖的 Capobianco-Molluzzo 強度向量為 。不可分圖的 Capobianco-Molluzzo 強度然後被定義為 。

簡單連通圖 的強度的最標準定義 是

其中 是連通分量的數量，最小值取自 的所有邊割 (Gusfield 1983, 1991)。在這裡，分母中減一給出了建立的額外連通分量的數量。因此，圖強度衡量了圖對邊刪除的抵抗力，因此是對網路遭受攻擊的脆弱性的度量（Cunningham 1985，Gusfield 1991），並且可以自然地推廣到邊加權圖。圖強度的計算可以在多項式時間內完成（Cunningham 1985，Trubin 1993）。

雖然人們可以將 用於不連通圖，如 Chvátal (1973) 在圖韌性的類似情況中所做的那樣，但應用邊割的定義作為增加連通分量數量的割，可以為不連通圖提供明確定義的強度。

頂點割 圖強度的類似物被稱為圖韌性。

Tutte-Nash-Williams 定理指出 ，其中 是向下取整函式，是可以包含在圖 中的邊不相交生成樹的最大數量 (Gusfield 1984, Cunningham 1985)。

圖強度與圖強積無關。