一、極大強連通子圖是什么

極大強連通子圖

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

極小連通子圖

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

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

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

延伸閱讀：

二、強連通分量

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