連通性 (圖論)
在數學與計算機科學中，連通性是圖論的一個基本概念：它是需要移除的元素（節點或邊）的最小數量，使得剩餘的節點分離成兩個或多個獨立的子圖。[1]它與網絡流問題的理論密切相關。圖的連通性是衡量其作為網絡的韌性的重要標準。
連通節點和連通圖
[編輯]在無向圖G中，如果G包含一條從u到v的路徑，則兩個頂點u和v被稱為是連通的。否則，它們被稱為是非連通的。如果這兩個頂點由一條長度為1的路徑連接，即由一條邊連接，則這兩個頂點被稱為是相鄰的。
如果圖中的每一對頂點都是連通的，則稱該圖為連通的。這意味着，每一對頂點之間都有一條路徑。因此，如果一個無向圖G中存在兩個頂點，使得G中沒有任何路徑以這兩個頂點為端點，那麼這個無向圖就是非連通的。只有一個頂點的圖是連通的。有兩個或更多頂點的無邊圖是非連通的。
如果將一個有向圖的所有有向邊替換成無向邊，會產生一個連通（無向）圖，那麼這個有向圖被稱為是弱連通的。如果對於每一對頂點u和v，它包含一條從u到v的有向路徑，或者從v到u的有向路徑，那麼它就是單向連通的（也稱為半連通）。[2]如果對於每一對頂點u和v，它都包含一條從u到v的有向路徑和一條從v到u的有向路徑，那它就是強連通的。
分量與割
[編輯]連通分量是無向圖的極大連通子圖。每個頂點和每條邊都僅屬於一個連通分量。當且僅當一個圖有且僅有一個連通分量時，原圖就是連通的。
強連通分量是有向圖的極大強連通子圖。
連通圖G的點割集是一組頂點，除去這些頂點會使G變得不連通。點連通度κ(G)（其中G不是完全圖）是最小點割集的大小。如果一個圖的點連通度為k或更大，則該圖被稱為k-點連通的。
更確切地說，任何圖G（無論是否完全）如果至少包含k+1個頂點，但不包含一個由k-1個頂點組成的集合，使得移除該集合的點會使圖不連通，則稱其為k-點連通的；而κ(G)的定義是使G是k-點連通的最大的k。特別的，一個有n個頂點的完整圖，表示為Kn，根本沒有點割集，但κ(Kn) = n − 1。
對兩個頂點u和v，u到v的點割集是一個頂點的集合，從圖中移除這些頂點會使u和v不連通。局部點連通度κ(u, v)是u到v的最小點割集的大小。對於無向圖來說，局部點連通度是對稱的；也就是說，κ(u, v) = κ(v, u)。此外，除了完全圖，κ(G)等於在所有不相鄰的頂點對u到v上κ(u, v)的最小值。
2-點連通也被稱為點雙連通。一個連通但不是2-點連通的圖G有時被稱為可分離的。
類似地，以上概念可以被定義為邊的概念。在簡單情況下，切割一條特定的邊會使圖不連通，這條邊被稱為橋。更一般地，G的邊割集是一組邊，去除這些邊會使圖不連通。邊連通度λ(G)是最小的邊割集的大小，兩個頂點u到v的局部邊連通度λ(u, v)是u到v最小的邊割集的大小，同樣，局部邊連通度是對稱的。如果一個圖的邊連通度為k或更大，則稱該圖為k-邊連通的。
如果一個圖的點連通性等於其最小度數，則稱該圖為最大點連通的。如果一個圖的邊連通性等於其最小度數，則稱該圖為最大邊連通的。[3]
參考資料
[編輯]- ^ Diestel, R. Graph Theory, Electronic Edition: 12. 2005 [2022-08-25]. （原始內容存檔於2019-12-16）.
- ^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition (PDF). [2022-08-25]. （原始內容存檔 (PDF)於2020-01-10）.
- ^ Gross, Jonathan L.; Yellen, Jay. Handbook of graph theory. CRC Press. 2004: 335 [2022-08-25]. ISBN 978-1-58488-090-5. （原始內容存檔於2021-08-14）.