連通圖

連通圖（英語：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中，前幾個份量是

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