圖論 - 連通性
能否從一個頂點遍歷到另一個頂點取決於圖的連線方式。連通性是圖論中的一個基本概念。連通性定義了圖是連通的還是不連通的。它根據邊和頂點有子主題，稱為邊連通性和頂點連通性。讓我們詳細討論一下。
連通性
如果每對頂點之間存在一條路徑，則稱該圖是連通的。從每個頂點到任何其他頂點，都應該存在一些路徑可以遍歷。這就是所謂的圖的連通性。具有多個不連通頂點和邊的圖被稱為不連通圖。
示例1
在下面的圖中，可以從一個頂點移動到任何其他頂點。例如，可以使用路徑“a-b-e”從頂點“a”遍歷到頂點“e”。
示例2
在下面的例子中，無法從頂點“a”遍歷到頂點“f”，因為它們之間沒有直接或間接的路徑。因此，它是一個不連通圖。
割點
設“G”是一個連通圖。如果“G-V”（從“G”中刪除“V”）導致一個不連通圖，則頂點V ∈ G被稱為“G”的割點。從圖中移除割點會將其分成兩個或多個圖。
注意 - 刪除割點可能會使圖不連通。
一個連通圖“G”最多可能有(n-2)個割點。
示例
在下面的圖中，頂點“e”和“c”是割點。
移除“e”或“c”後，圖將變成不連通圖。
沒有“g”，頂點“c”和頂點“h”以及許多其他頂點之間沒有路徑。因此，它是一個不連通圖，割點為“e”。類似地，“c”也是上述圖的割點。
割邊（橋）
設“G”是一個連通圖。如果“G-e”導致一個不連通圖，則邊“e”∈ G被稱為割邊。
如果移除圖中的一條邊會導致兩個或多個圖，則該邊稱為割邊。
示例
在下面的圖中，割邊是[(c, e)]。
從圖中移除邊(c, e)後，它將變成不連通圖。
在上圖中，移除邊(c, e)將圖分成兩部分，這實際上是一個不連通圖。因此，邊(c, e)是該圖的割邊。
注意 - 設“G”是一個具有“n”個頂點的連通圖，則
當且僅當邊“e”不是G中任何迴圈的一部分時，割邊e ∈ G。
可能的割邊最大數量為“n-1”。
只要存在割邊，也存在割點，因為割邊的至少一個頂點是割點。
如果存在割點，則割邊可能存在也可能不存在。
圖的割集
設“G”= (V, E)是一個連通圖。如果從G中刪除E’的所有邊使得G不連通，則E的子集E’稱為G的割集。
如果從圖中刪除一定數量的邊使其不連通，則這些被刪除的邊稱為該圖的割集。
示例
看一下下面的圖。它的割集是E1 = {e1, e3, e5, e8}。
從圖中移除割集E1後，它將顯示如下：
類似地，還有其他割集可以使圖不連通：
E3 = {e9} – 圖的最小割集。
E4 = {e3, e4, e5}
邊連通性
設“G”是一個連通圖。移除最少數量的邊使得“G”不連通，這個最小數量的邊稱為G的邊連通性。
記號 - λ(G)
換句話說，G的最小割集中的邊數稱為G的邊連通性。
如果“G”有一條割邊，則λ(G)為1。（G的邊連通性。）
示例
看一下下面的圖。透過移除兩條最小邊，連通圖變得不連通。因此，它的邊連通性(λ(G))為2。
以下是透過移除兩條邊來使圖不連通的四種方法：
頂點連通性
設“G”是一個連通圖。移除最少數量的頂點使得“G”變得不連通或將“G”簡化為平凡圖，這個最小數量的頂點稱為它的頂點連通性。
記號 - K(G)
示例
在上圖中，移除頂點“e”和“i”使得圖不連通。
如果G有一個割點，則K(G) = 1。
記號 - 對於任何連通圖G，
K(G) ≤ λ(G) ≤ δ(G)
頂點連通性(K(G))，邊連通性(λ(G))，G的最小度數(δ(G))。
示例
計算下列圖的λ(G)和K(G)：
解答
從圖中，
δ(G) = 3
K(G) ≤ λ(G) ≤ δ(G) = 3 (1)
K(G) ≥ 2 (2)
刪除邊{d, e}和{b, h}，我們可以使G不連通。
因此，
λ(G) = 2
2 ≤ λ(G) ≤ δ(G) = 2 (3)
從(2)和(3)，頂點連通性K(G) = 2