跳至內容

連通性 (圖論)

維基百科,自由的百科全書
當左邊灰色區域中最右邊的節點被移除時,這個圖就變得不連通了
當虛線邊被移除時,這個圖就會不連通。

數學計算機科學中,連通性圖論的一個基本概念:它是需要移除的元素(節點或邊)的最小數量,使得剩餘的節點分離成兩個或多個獨立的子圖[1]它與網絡流問題的理論密切相關。圖的連通性是衡量其作為網絡的韌性的重要標準。

有頂點0,這個圖就是非連通的。該圖的其餘部分是連通的。

連通節點和連通圖

無向圖G中,如果G包含一條從uv路徑,則兩個頂點uv被稱為是連通的。否則,它們被稱為是非連通的。如果這兩個頂點由一條長度為1的路徑連接,即由一條邊連接,則這兩個頂點被稱為是相鄰的。

如果中的每一對頂點都是連通的,則稱該圖為連通的。這意味著,每一對頂點之間都有一條路徑。因此,如果一個無向圖G中存在兩個頂點,使得G中沒有任何路徑以這兩個頂點為端點,那麼這個無向圖就是非連通的。只有一個頂點的圖是連通的。有兩個或更多頂點的無邊圖非連通的。

如果將一個有向圖的所有有向邊替換成無向邊,會產生一個連通(無向)圖,那麼這個有向圖被稱為是弱連通的。如果對於每一對頂點uv,它包含一條從uv的有向路徑,或者從vu的有向路徑,那麼它就是單向連通的(也稱為半連通)。[2]如果對於每一對頂點uv,它都包含一條從uv的有向路徑和一條從vu的有向路徑,那它就是強連通的。

分量與割

連通分量是無向圖的極大連通子圖。每個頂點和每條邊都僅屬於一個連通分量。若且唯若一個圖有且僅有一個連通分量時,原圖就是連通的。

強連通分量是有向圖的極大強連通子圖。

連通圖G點割集英語Cut (graph theory)是一組頂點,除去這些頂點會使G變得不連通。點連通度英語k-vertex-connected graphκ(G)(其中G不是完全圖)是最小點割集的大小。如果一個圖的點連通度為k或更大,則該圖被稱為k-點連通的。

更確切地說,任何圖G(無論是否完全)如果至少包含k+1個頂點,但不包含一個由k-1個頂點組成的集合,使得移除該集合的點會使圖不連通,則稱其為k-點連通的;而κ(G)的定義是使Gk-點連通的最大的k。特別的,一個有n個頂點的完整圖,表示為Kn,根本沒有點割集,但κ(Kn) = n − 1

對兩個頂點u和v,uv點割集是一個頂點的集合,從圖中移除這些頂點會使uv不連通。局部點連通度κ(u, v)uv的最小點割集的大小。對於無向圖來說,局部點連通度是對稱的;也就是說,κ(u, v) = κ(v, u)。此外,除了完全圖,κ(G)等於在所有不相鄰的頂點對uvκ(u, v)的最小值。

2-點連通也被稱為點雙連通。一個連通但不是2-點連通的圖G有時被稱為可分離的。

類似地,以上概念可以被定義為邊的概念。在簡單情況下,切割一條特定的邊會使圖不連通,這條邊被稱為。更一般地,G的邊割集是一組邊,去除這些邊會使圖不連通。邊連通度英語k-edge-connected graphλ(G)是最小的邊割集的大小,兩個頂點uv的局部邊連通度λ(u, v)uv最小的邊割集的大小,同樣,局部邊連通度是對稱的。如果一個圖的邊連通度為k或更大,則稱該圖為k-邊連通的。

如果一個圖的點連通性等於其最小度數,則稱該圖為最大點連通的。如果一個圖的邊連通性等於其最小度數,則稱該圖為最大邊連通的。[3]

參考資料

  1. ^ Diestel, R. Graph Theory, Electronic Edition: 12. 2005 [2022-08-25]. (原始內容存檔於2019-12-16). 
  2. ^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition (PDF). [2022-08-25]. (原始內容存檔 (PDF)於2020-01-10). 
  3. ^ 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). 

參見