在圖論中，連通圖基于連通的概念。在一個無向圖 G 中，若從頂點vi到頂點vj有路徑相連（當然從vj到vi也一定有路徑），則稱vi和vj是連通的。如果 G 是有向圖，那么連接vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點都是連通的，那么圖被稱作連通圖。圖的連通性是圖的基本性質。

概述

在圖論中，連通圖基于連通的概念。在一個無向圖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(tǒng)的連通路徑，x和y分別是起點和終點。當x=y時，Γ被稱為回路。如果通路Γ中的邊兩兩不同，則Γ是一條簡單通路，否則為一條復雜通路。如果圖G中每兩點間皆連通，則G是連通圖。

相關概念

連通分量：無向圖的一個極大連通子圖稱為的一個連通分量（或連通分支）。連通圖只有一個連通分量，即其自身；非連通的無向圖有多個連通分量。

強連通圖：有向圖= - ,中，若對于V中任意兩個不同的頂點和，都存在從到以及從到的路徑，則稱是強連通圖。相應地有強連通分量的概念。強連通圖只有一個強連通分量，即是其自身；非強連通的有向圖有多個強連分量。

單向連通圖：設G=是有向圖，如果u->v意味著圖G至多包含一條從u到v的簡單路徑，則圖G為單連通圖。

弱連通圖：將有向圖的所有的有向邊替換為無向邊，所得到的圖稱為原圖的基圖。如果一個有向圖的基圖是連通圖，則有向圖是弱連通圖。

初級通路：通路中所有的頂點互不相同。初級通路必為簡單通路，但反之不真。

性質

一個無向圖= - ,是連通的，那么邊的數(shù)目大于等于頂點的數(shù)目減一：|E|>=|V|-1，而反之不成立。如果= - ,是有向圖，那么它是強連通圖的必要條件是邊的數(shù)目大于等于頂點的數(shù)目：|E|>=|V|，而反之不成立。沒有回路的無向圖是連通的當且僅當它是樹，即等價于：|E|=|V|-1。