概述
連通圖在圖論中，連通圖基於連通的概念。在一個無向圖 G 中，若從頂點vi到頂點vj有路徑相連(當然從vj到vi也一定有路徑)，則稱vi和vj是連通的。如果 G 是有向圖，那么連線vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那么圖被稱作連通圖。圖的連通性是圖的基本性質。
嚴格定義
對一個圖 G=(V,E) 中的兩點 x 和 y ，若存在交替的頂點和邊的序列
Γ=(x=v0-e1-v1-e2-...-ek-(vk+1)=y) (在有向圖中要求有向邊vi−( vi+1)屬於E )，則兩點 x 和 y 是連通的。Γ是一條x到y的連通路徑，x和y分別是起點和終點。當 x = y 時，Γ 被稱為迴路。如果通路 Γ 中的邊兩兩不同，則 Γ 是一條簡單通路，否則為一條複雜通路。如果圖 G 中每兩點間皆連通，則 G 是連通圖。
相關概念
連通分量： 無向圖 的一個極 大連通子圖稱為 的一個連通分量（或 連通分支）。連通圖只有一個 連通分量，即其自身；非連通的 無向圖有多個連通分量。
強連通圖： 有向圖 =( , ) 中，若對於V中任意兩個不同的 頂點 和 ，都存在從 到 以及從 到 的路徑，則稱 是強連通圖。相應地有強 連通分量的概念。 強連通圖只有一個強 連通分量，即是其自身；非強連通的 有向圖有多個強連分量。
單向連通圖：設G=是 有向圖，如果u->v意味著圖G至多包含一條從u到v的簡單路徑，則圖G為單連通圖。
弱連通圖：將 有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖。如果一個 有向圖的基圖是連通圖，則有向圖是 弱連通圖。
初級通路：通路中所有的 頂點互不相同。初級通路必為簡單通路，但反之不真。
性質
一個 無向圖 =( , ) 是連通的，那么邊的數目大於等於 頂點的數目減一：|E|>=|V|-1，而反之不成立。
如果 =( , ) 是 有向圖，那么它是 強連通圖的必要條件是邊的數目大於等於 頂點的數目：|E|>=|V|，而反之不成立。
沒有 迴路的 無向圖是連通的若且唯若它是 樹，即等價於：|E|=|V|-1。
參考來源
Fred Buckley,Marty Lewinter.《圖論簡明教程》.李慧霸 王鳳芹 譯.北京:清華大學出版社.2005 年
W.T.Tutte, Graph Theory . Cambridge University Press . 2004
