跳至內容

連通圖

維基百科,自由的百科全書

連通圖(英語: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. .