連通性 (圖論)
在數學與計算機科學中,連通性是圖論的一個基本概念:它是需要移除的元素(節點或邊)的最小數量,使得剩餘的節點分離成兩個或多個獨立的子圖。[1]它與網絡流問題的理論密切相關。圖的連通性是衡量其作為網絡的韌性的重要標準。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Network_Community_Structure.svg/220px-Network_Community_Structure.svg.png)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cb/Sample-graph.jpg/220px-Sample-graph.jpg)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/9/97/UndirectedDegrees.svg/220px-UndirectedDegrees.svg.png)
連通節點和連通圖
在無向圖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).