連通圖

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

## 嚴格定義

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

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

## 分量和割

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

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

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

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

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

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

在一個圖上，以下的不等式成立:$\kappa(G)\leqslant\lambda(G)\leqslant\delta(G)$，其中$\delta(G)$是$G$的最小度(minimum degree)。

如果圖$G$的點連通度等於其最小度,則被稱作極大連通的，如果它的邊連通度等於其最小度，則它被稱作極大邊連通的。

### Super- and hyper-連通

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

一個割點集$X$被稱作non-trivial的，如果對於任意不屬於$X$的頂點$v$，其鄰域$N(u)$都不包含在$X$中。$G$的superconnectivity可以被表示成：

$\kappa(G)=\min\{ |X|:X\text{ is a non-trivial cutset}\}$。

一個non-trivial 割邊和edge-superconnectivity $\lambda_1(G)$可以被類似地定義。

## 門格爾定理

圖論中關於連通性最重要的定理之一門格爾定理，它用頂點之間獨立路徑的個數刻畫了圖點連通和邊連通度。令$u$，$v$為圖$G$的兩個頂點，一系列連接$u$和$v$的路徑被稱作點獨立的，如果它們之間除了$u$，$v$之外，不會有相同的頂點。類似地，它們被稱作邊獨立的，如果它們不會有相同的邊。$u$ 和$u$點獨立的路徑的個數被記作$\kappa'(u,v)$，邊獨立的路徑的個數被記作$\lambda'(u,v)$。

門格爾定理告訴我們，若$u$，$v$不相同，則$\lambda'(u,v)=\lambda(u,v)$，若$u$，$v$不相同且不相鄰，則$\kappa'(u,v)=\kappa(u,v)$。

事實上，這其實是最大流最小割定理的特殊情況。

## 連通度的計算方面

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

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

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

### 連通圖的個數

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

n｜個數

2｜1

3｜4

4｜38

5｜728

6｜26704

7｜1866256

8｜251548592

## 一些例子

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

## 其他性質

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

## 參見

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