連通圖(英語:Connected graph)是圖論中最基本概念之一,其定義基於連通的概念。在一個無向圖G中,若從頂點到頂點有路徑相連(從也一定有路徑),則稱是連通的。如果G有向圖,那麼連接的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的,那麼圖被稱作連通圖。圖的連通性是圖的基本性質。連通度是指為了讓圖分解成孤立的子圖所要刪除的頂點數的最小值。連通度是刻畫網絡的一個重要指標。

嚴格定義

對一個圖G= (V,E)中的兩點  ,若存在交替的頂點和邊的序列 (在有向圖中要求有向邊 屬於E),則兩點  是連通的。 是一條  的連通路徑,  分別是起點和終點。當 時, 被稱為迴路。如果通路 中的邊兩兩不同,則 是一條簡單通路,否則為一條複雜通路。如果圖G中每兩點間皆連通,則G連通圖

一個有向圖被稱作弱連通(weakly connected)的,如果將所有有向邊替換為無向邊之後的無向圖是連通的,如果對於任意一對頂點  ,或者存在一條從  的有向路徑,或者存在一條從  的有向路徑,則該圖是單連通(unilaterally conncected)的[1],如果對於如果對於任意一對頂點  ,同時存在一條從  的有向路徑和一條從  的有向路徑,則該圖是強連通(strongly connected)的。

分量和割

無向圖G的一個極大連通子圖稱為G的一個連通分量(或連通分支)。每一個頂點和每一條邊都屬於唯一的一個連通分量,連通圖只有一個連通分量,即其自身;非連通的無向圖有多個連通分量。

有向圖中的強連通分量是其極大的強連通子圖。強連通圖只有一個強連通分量,即是其自身;非強連通的有向圖有多個強連通分量。

連通圖 割點是指一個由頂點組成的集合,在 刪除了這些點之後,會變得不連通。點連通度 是割點集階數的最小值。如果圖 不是完全圖,且 ,則圖  -點連通的。更確切地來說,如果圖 (不論是否完全)可以在刪除了 個點之後變得不連通,卻不能在刪除 個點之後變得不連通,則圖  -點連通的,特別地,階數為 的完全圖是 -點連通的。

一對端點 , 割點是是指一個由頂點組成的集合,在 刪除了這些點之後, , 會變得不連通。局部連通度  , 的最小割點集的階數。在無向圖上,局部連通度是對稱的,也就是說, ,另外,除了完全圖之外, 為所有不相鄰的點對 , 的局部聯通度中的最小值。

類似的概念可以用來定義邊連通度。如果在 上刪除一條邊可以導致不連通性,則這條邊被稱作。更一般地,割邊是指一個由邊組成的集合,在 在 刪除了這些邊之後,會變得不連通。邊連通度在 是最小的割邊集的大小,局部邊連通度 

如果圖 的邊連通度大於等於 ,則它被稱作 -邊連通的。

在一個圖上,以下的不等式成立: ,其中  的最小度(minimum degree)[2]。 如果圖 的點連通度等於其最小度,則被稱作極大連通的,如果它的邊連通度等於其最小度,則它被稱作極大邊連通的[3]

Super- and hyper-連通

如果圖 上,每一個最小的割點集都能孤立一個頂點,則圖 被稱作super-connected或者 super-κ。如果 刪除了每一個最小的割點集之後圖都會分成兩個連通分量,並且其中一個是單點,那麼圖 被稱作hyper-connectedhyper-κ。 如果圖上刪除了每一個最小的割點集之後都分成了兩個連通分量,則圖 被稱作semi-hyper-connectedsemi-hyper-κ[4]

一個割點集 被稱作non-trivial的,如果對於任意不屬於 的頂點 ,其鄰域 都不包含在 中。 superconnectivity可以被表示成:  = min{|X| : X is a non-trivial cutset}.

一個non-trivial 割邊和edge-superconnectivity λ1(G)可以被類似地定義。[5]


門格爾定理

圖論中關於連通性最重要的定理之一門格爾定理,它用頂點之間獨立路徑的個數刻畫了圖點連通和邊連通度。令   為圖 的兩個頂點,一系列連接  的路徑被稱作點獨立的,如果它們之間除了  之外,不會有相同的頂點。類似地,它們被稱作邊獨立的,如果它們不會有相同的邊。  點獨立的路徑的個數被記作 ,邊獨立的路徑的個數被記作 。 門格爾定理告訴我們,若  不相同,則 ,若  不相同且不相鄰,則  [6][7] 。 事實上,這其實是最大流最小割定理的特殊情況。

連通度的計算方面

判斷兩個頂點是否連通這一問題可以被搜索算法迅速的解決,例如廣度優先算法。更一般地,判斷一個圖是否連通,以及一個圖連通分量的計數問題可以被較快地解決(例如使用併查集,一個簡單算法的偽代碼可以寫成:

  1.  的任意一個頂點開始
  2. 使用深度優先或廣度優先搜索所有與該頂點連通的頂點,並計數
  3. 搜索完成,如果計數等於 的階數,則 是連通的,否則 不連通。

根據門格爾定理,在連通圖 上,對於任意一對頂點    可以通過最大流最小割算法迅速的計算,因此, 的邊連通度和點聯通度分別作為  的最小值,可以被迅速地計算。

連通圖的個數

 階(小於等於16)的不同的連通圖的個數在 On-Line Encyclopedia of Integer Sequences中被記錄在 A001187中,前幾個份量是

n 個數
2 1
3 4
4 38
5 728
6 26704
7 1866256
8 251548592

一些例子

  • 不連通圖的邊連通度和點連通度均為 
  • 1-點連通等價於階數大於等於 的圖的連通性。
  •  階完全圖的邊連通度是 ,其他類型的 階圖的邊連通度嚴格小於 
  • 中,任意兩個頂點之間的局部邊連通度都是 

其他性質

  • 連通性被圖同態保持
  • 如果 是連通的,則它的線圖 也是連通的
  •  是2-邊連通的,若且唯若它有一個定向,且是強連通的。
  • 根據G. A. Dirac的結論,如果圖  -點連通的,且 ,則對於每k個頂點組成的集合,存在一個環經過這個集合上所有的頂點。[8][9] 時,反過來亦成立。
  • 一個無向圖G= (V,E)是連通的,那麼邊的數目大於等於頂點的數目減一: ,而反之不成立。
  • 如果G= (V,E)是有向圖,那麼它是強連通圖的必要條件是邊的數目大於等於頂點的數目: ,而反之不成立。
  • 沒有迴路的無向圖是連通的若且唯若它是,即等價於: 

參見

參考文獻

  1. ^ Chapter 11: Digraphs: Principle of duality for digraphs: Definition (PDF). [2020-10-04]. (原始內容存檔 (PDF)於2020-01-10). 
  2. ^ Diestel, R. Graph Theory, Electronic Edition: 12. 2005 [2020-10-04]. (原始內容存檔於2019-12-16). 
  3. ^ Gross, Jonathan L.; Yellen, Jay. Handbook of graph theory. CRC Press. 2004: 335. ISBN 978-1-58488-090-5. 
  4. ^ Liu, Qinghai; Zhang, Zhao. The existence and upper bound for two types of restricted connectivity. Discrete Applied Mathematics. 2010-03-01, 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017. 
  5. ^ Balbuena, Camino; Carmona, Angeles. On the connectivity and superconnectivity of bipartite digraphs and graphs. Ars Combinatorica. 2001-10-01, 61: 3–22. 
  6. ^ Gibbons, A. Algorithmic Graph Theory. Cambridge University Press. 1985. 
  7. ^ Nagamochi, H.; Ibaraki, T. Algorithmic Aspects of Graph Connectivity. Cambridge University Press. 2008. 
  8. ^ Dirac, Gabriel Andrew. In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen. Mathematische Nachrichten. 1960, 22 (1–2): 61–85. MR 0121311. doi:10.1002/mana.19600220107. .
  9. ^ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz. A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs. Discrete Mathematics. 2007, 307 (7–8): 878–884. MR 2297171. doi:10.1016/j.disc.2005.11.052. .