一、極大強(qiáng)連通子圖是什么

極大強(qiáng)連通子圖

（1）極大連通子圖是連通圖的一個(gè)連通分量，連通分量本身是一個(gè)連通圖。
（2）連通圖的極大連通子圖只有一個(gè)就是其本身，是少數(shù)的。
（3）非連通的極大連通子圖有多個(gè)，每一個(gè)都是一個(gè)連通圖。
為什么稱為極大？如果將連通分量外的任意一個(gè)頂點(diǎn)添加進(jìn)連通分量都會(huì)造成不連通。

極小連通子圖

（1）一個(gè)連通圖的生成樹是該連通圖的極小連通子圖。同一個(gè)連通圖可以有不同的生成樹，所以生成樹不是少數(shù)的。

（2）極小連通子圖=生成樹，則有n個(gè)頂點(diǎn)，必然有n-1條邊。

（3）為什么稱為最小？如果去極小連通子圖的一條邊就無(wú)法構(gòu)成樹，不滿足樹的定義。意味著在極小連通子圖中每一條邊都是必不可少的。如果給極小連通子圖增加一條邊，n個(gè)節(jié)點(diǎn)，n條邊，則必然會(huì)構(gòu)成環(huán)。意味只有能夠連通圖中所有頂點(diǎn)而又不會(huì)構(gòu)成回路的任意的子圖都是他的生成樹。

延伸閱讀：

二、強(qiáng)連通分量

強(qiáng)連通分量是有向圖的極大的強(qiáng)連通子圖，所謂“極大”意味著，把圖劃分為若干個(gè)強(qiáng)連通分量后，不存在兩個(gè)強(qiáng)連通分量相互可達(dá)。處理強(qiáng)連通分量的一個(gè)有力的工具是dfs生成樹：在dfs時(shí)，每當(dāng)通過(guò)某條邊e訪問(wèn)到一個(gè)新節(jié)點(diǎn)，就加入這個(gè)點(diǎn)和這條邊，最后得到的便是dfs生成樹。反向邊和橫叉邊都有一個(gè)特點(diǎn)：起點(diǎn)的dfs序必然大于終點(diǎn)的dfs序。這可以導(dǎo)出一個(gè)有用的結(jié)論：對(duì)于每個(gè)強(qiáng)連通分量，存在一個(gè)點(diǎn)是其他所有點(diǎn)的祖先。若不然，則可以把強(qiáng)連通分量劃成 n個(gè)分支，使各分支的祖先節(jié)點(diǎn)互相不為彼此的祖先。這些分支間不能通過(guò)樹邊相連，只能通過(guò)至少n條橫叉邊相連，但這必然會(huì)違背上一段講的性質(zhì)。