1.連通圖和連通分量

連通圖：無(wú)向圖中，如果頂點(diǎn)vi到vj有路徑，則稱vi和vj是連通的。如果圖中任何兩個(gè)頂點(diǎn)都是連通的，則稱G為連通圖。如下圖

????連通分量：無(wú)向圖G的極大連通子圖稱為G的連通分量。極大連通子圖的意思是：該子圖是 ????G的連通子圖，如果再加入一個(gè)頂點(diǎn)，該子圖不連通。

????對(duì)于連通圖，則其連通分量就是它自己，對(duì)于非連通圖，則有兩個(gè)以上連通分量。

2.強(qiáng)連通圖和強(qiáng)連通分量

強(qiáng)連通圖：有向圖中，如果圖中任何兩個(gè)頂點(diǎn)vi到vj有路徑，且vi到vj也有路徑，則稱G為強(qiáng)連通圖。

強(qiáng)連通分量：有向圖G的極大連通子圖稱為G的強(qiáng)連通分量。極大強(qiáng)連通子圖意思是：該子圖是G的強(qiáng)連通子圖，如果再加一個(gè)頂點(diǎn)，該子圖不再是強(qiáng)連通的。

如下圖所示，（a）是強(qiáng)連通圖，（b）不是強(qiáng)連通圖，（c）是（b)的強(qiáng)連通分量。

3.無(wú)向圖的橋與割點(diǎn)

????在生活中，橋就是連接河兩岸的交通要道，橋斷了，河兩岸不再連通。在圖論中，橋有同樣的含義，如圖所示，去掉該邊（5，8）后圖分裂成兩個(gè)互不連通的子圖，邊（5，8）為圖G的橋。同樣，邊（5，7）也為圖G的橋。

????如果去掉無(wú)向連通圖G中的一條邊e,G分裂為兩個(gè)不相連的子圖，那么e為G的橋或割邊。

????在日常網(wǎng)絡(luò)中，有很多路由器使網(wǎng)絡(luò)連通，有的路由器壞掉也無(wú)傷大雅，網(wǎng)絡(luò)仍然連通，但是非常關(guān)鍵結(jié)點(diǎn)的路由器壞了，網(wǎng)絡(luò)將不再連通。如圖所示，如果5號(hào)結(jié)點(diǎn)的路由器壞了，圖G不再連通，分裂成3個(gè)不相連的子圖，5號(hào)結(jié)點(diǎn)為圖G的割點(diǎn)。

????如果去掉無(wú)向連接圖G中的一個(gè)點(diǎn)v以及v關(guān)聯(lián)的所有邊，G分裂為兩個(gè)或兩個(gè)以上不相連的圖，那么v為G的割點(diǎn)。

注意：刪除邊時(shí)，只是把邊刪除，不刪除邊關(guān)聯(lián)的點(diǎn)；而刪除點(diǎn)時(shí)，要?jiǎng)h除該點(diǎn)及其關(guān)聯(lián)的所有邊。

割點(diǎn)與橋的關(guān)系：

1）有割點(diǎn)不一定有橋，有橋一定存在割點(diǎn)。

2）橋一定是割點(diǎn)依附的邊。

4.無(wú)向圖的雙連通分量

5.雙連通分量的縮點(diǎn)

????把每一條邊雙連通分量e-DCC看作一個(gè)點(diǎn)，把橋看作連接兩個(gè)縮點(diǎn)的無(wú)向邊，得到一個(gè)樹，這種方法稱為e-DCC縮點(diǎn)。

????例如,如圖所示，圖中有兩個(gè)橋，5-7,5-8，每個(gè)橋的邊保留，橋兩端的邊雙連通分量縮為一個(gè)點(diǎn)，這樣生成一個(gè)樹。

????如圖所示，圖G的點(diǎn)雙連通分量有4個(gè)：

????把每一個(gè)點(diǎn)雙連通分量v-DCC看作一個(gè)點(diǎn)，把割點(diǎn)看一個(gè)點(diǎn)，每個(gè)割點(diǎn)向包含它的v-DCC連接一條邊，得到一個(gè)樹，這種方法稱為v-DCC縮點(diǎn)。