連通圖

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

嚴格定義

對一個圖G= (V,E)中的兩點${\displaystyle x}$和${\displaystyle y}$，若存在交替的頂點和邊的序列${\displaystyle \Gamma =(x=v_{0}-e_{1}-v_{1}-e_{2}-\cdots -e_{k}-v_{k}=y)}$（在有向圖中要求有向邊${\displaystyle v_{i}-v_{i+1}}$屬於E），則兩點${\displaystyle x}$和${\displaystyle y}$是連通的。${\displaystyle \Gamma }$是一條${\displaystyle x}$到${\displaystyle y}$的連通路徑，${\displaystyle x}$和${\displaystyle y}$分別是起點和終點。當${\displaystyle x=y}$時，${\displaystyle \Gamma }$被稱為迴路。如果通路${\displaystyle \Gamma }$中的邊兩兩不同，則${\displaystyle \Gamma }$是一條簡單通路，否則為一條複雜通路。如果圖G中每兩點間皆連通，則G是連通圖。

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

分量和割

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

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

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

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

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

如果圖${\displaystyle G}$的邊連通度大於等於${\displaystyle k}$，則它被稱作${\displaystyle k}$-邊連通的。

在一個圖上，以下的不等式成立:${\displaystyle \kappa (G)\leqslant \lambda (G)\leqslant \delta (G)}$，其中${\displaystyle \delta (G)}$是${\displaystyle G}$的最小度(minimum degree)^[2]。 如果圖${\displaystyle G}$的點連通度等於其最小度,則被稱作極大連通的，如果它的邊連通度等於其最小度，則它被稱作極大邊連通的^[3]。

Super- and hyper-連通

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

一個割點集${\displaystyle X}$被稱作non-trivial的，如果對於任意不屬於${\displaystyle X}$的頂點${\displaystyle v}$，其鄰域${\displaystyle N(u)}$都不包含在${\displaystyle X}$中。${\displaystyle G}$的superconnectivity可以被表示成： ${\displaystyle \kappa (G)=}$= min{|X| : X is a non-trivial cutset}.

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

門格爾定理

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

連通度的計算方面

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

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

根據門格爾定理，在連通圖${\displaystyle G}$上，對於任意一對頂點${\displaystyle u}$，${\displaystyle v}$，${\displaystyle \kappa (u,v)}$，${\displaystyle \lambda (u,v)}$可以通過最大流最小割算法迅速的計算，因此，${\displaystyle G}$的邊連通度和點聯通度分別作為${\displaystyle \kappa (u,v)}$，${\displaystyle \lambda (u,v)}$的最小值，可以被迅速地計算。

連通圖的個數

${\displaystyle n}$階（小於等於16）的不同的連通圖的個數在 On-Line Encyclopedia of Integer Sequences中被記錄在 A001187中，前幾個份量是

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

一些例子

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

其他性質

• 連通性被圖同態保持
• 如果${\displaystyle G}$是連通的，則它的線圖${\displaystyle L(G)}$也是連通的
• 圖${\displaystyle G}$是2-邊連通的，若且唯若它有一個定向，且是強連通的。
• 根據G. A. Dirac的結論，如果圖${\displaystyle G}$是${\displaystyle k}$-點連通的，且${\displaystyle k\geqslant 2}$，則對於每k個頂點組成的集合，存在一個環經過這個集合上所有的頂點。^[8][9] 在${\displaystyle k=2}$時，反過來亦成立。

• 一個無向圖G= (V,E)是連通的，那麼邊的數目大於等於頂點的數目減一：${\displaystyle |E|\geq |V|-1}$，而反之不成立。

• 如果G= (V,E)是有向圖，那麼它是強連通圖的必要條件是邊的數目大於等於頂點的數目：${\displaystyle |E|\geq |V|}$，而反之不成立。

• 沒有迴路的無向圖是連通的若且唯若它是樹，即等價於：${\displaystyle \displaystyle |E|=|V|-1}$。

參見

• 代數連通度
• Cheeger constant (graph theory)
• Dynamic connectivity, 併查集
• 擴展圖
• Strength of a graph

參考文獻

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..