连通图

**連通圖**（英語：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 is a non-trivial cutset}.

一個 non-trivial 割邊和 **edge-superconnectivity** λ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)$ 。
事實上，這其實是最大流最小割定理的特殊情況。

## 連通度的計算方面

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

1. 從 $G$ 的任意一個頂點開始
2. 使用深度優先或廣度優先搜索所有與該頂點連通的頂點，並計數
3. 搜索完成，如果計數等於 $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 中，前幾個份量是

## 一些例子

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

## 其他性質

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

## 參見

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

## 參考文獻