弱連通圖

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

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

基本介紹

• 中文名：弱連通圖
• 科目：離散數學

相關概念

通分量

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

連通圖

在無向圖中, 若從頂點v1到頂點v2有路徑, 則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。

強連通和弱連通的概念只在有向圖中存在。

一個無向圖G=(V,E) 是連通的，那么邊的數目大於等於頂點的數目減一：|E|>=|V|-1，而反之不成立。

如果G=(V,E) 是有向圖，那么它是強連通圖的必要條件是邊的數目大於等於頂點的數目：|E|>=|V|，而反之不成立。

沒有迴路的無向圖是連通的若且唯若它是樹，即等價於：|E|=|V|-1。

強連通圖

在有向圖中, 若對於每一對頂點v1和v2, 都存在一條從v1到v2和從v2到v1的路徑,則稱此圖是強連通圖。

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

單向連通圖

如果有向圖中，對於任意節點v1和v2，至少存在從v1到v2和從v2到v1的路徑中的一條，則原圖為單向連通圖。

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

強連通圖、連通圖、單向連通圖三者之間的關係是，強連通圖必然是單向連通的，單向連通圖必然是弱連通圖。

弱連通圖

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

初級通路

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

相關定義

定義1

設D是有向圖D=(V, E)的一個子圖。如果D`是強連通的(單向連通的、弱連通的),且D中不存在真包含D`的子圖是強連通的(單向連通的、弱連通的),則稱D`是D的一個強連通分支(單向連通分支、弱連通分支)。

定義2

有向圖D=(V,E)的每個點位於且僅位於D的某個強(弱)連通分支中。