連通分量:無向圖 G的一個(gè)極大連通子圖稱為 G的一個(gè)連通分量(或連通分支)。連通圖只有一個(gè)連通分量，即其自身;非連通的無向圖有多個(gè)連通分量。

強(qiáng)連通圖:有向圖 G=(V,E) 中，若對(duì)于V中任意兩個(gè)不同的頂點(diǎn) x和 y，都存在從x到 y以及從 y到 x的路徑，則稱 G是強(qiáng)連通圖。相應(yīng)地有強(qiáng)連通分量的概念。強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即是其自身;非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連分量。

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

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

初級(jí)通路:通路中所有的頂點(diǎn)互不相同。初級(jí)通路必為簡單通路，但反之不真。

無向圖G的一個(gè)極大連通子圖稱為G的一個(gè)連通分量(或連通分支)。連通圖只有一個(gè)連通分量，即其自身;非連通的無向圖有多個(gè)連通分量。

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

強(qiáng)連通和弱連通的概念只在有向圖中存在。

一個(gè)無向圖G=(V,E) 是連通的，那么邊的數(shù)目大于等于頂點(diǎn)的數(shù)目減一:|E|>=|V|-1，而反之不成立。

如果G=(V,E) 是有向圖，那么它是強(qiáng)連通圖的必要條件是邊的數(shù)目大于等于頂點(diǎn)的數(shù)目:|E|>=|V|，而反之不成立。

沒有回路的無向圖是連通的當(dāng)且僅當(dāng)它是樹，即等價(jià)于:|E|=|V|-1。

在有向圖中, 若對(duì)于每一對(duì)頂點(diǎn)v1和v2, 都存在一條從v1到v2和從v2到v1的路徑,則稱此圖是強(qiáng)連通圖。

即有向圖G=(V,E) 中，若對(duì)于V中任意兩個(gè)不同的頂點(diǎn)x和y，都存在從x到y以及從y到x的路徑，則稱G是強(qiáng)連通圖。相應(yīng)地有強(qiáng)連通分量的概念。強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即是其自身;非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連分量。

如果有向圖中，對(duì)于任意節(jié)點(diǎn)v1和v2，至少存在從v1到v2和從v2到v1的路徑中的一條，則原圖為單向連通圖。

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

強(qiáng)連通圖、連通圖、單向連通圖三者之間的關(guān)系是，強(qiáng)連通圖必然是單向連通的，單向連通圖必然是弱連通圖。

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

通路中所有的頂點(diǎn)互不相同。初級(jí)通路必為簡單通路，但反之不真。

一個(gè)無向圖 G=(V,E) 是連通的，那么邊的數(shù)目大于等于頂點(diǎn)的數(shù)目減一:|E|>=|V|-1，而反之不成立。

如果 G=(V,E) 是有向圖，那么它是強(qiáng)連通圖的必要條件是邊的數(shù)目大于等于頂點(diǎn)的數(shù)目:|E|>=|V|，而反之不成立。

沒有回路的無向圖是連通的當(dāng)且僅當(dāng)它是樹，即等價(jià)于:|E|=|V|-1。