迮今樊玉書 2020-01-27

首先先明確兩個概念，無向圖和有向圖；其次，明確一個概念，極大連通子圖可以存在於無向圖中，也可以存在於有向圖中（下面進行分析）；最後知道，極小連通子圖只存在於連通的無向圖中，不存在於不連通的無向圖和有向圖中。

也就是說，極大連通子圖和極小連通子圖適用條件是不一樣的，儘管它們看起來貌似很接近。

下面先說無向圖中的極大連通子圖。無向圖中的極大連通子圖也叫連通分量。無向圖可以分成兩種型別：連通的無向圖、不連通的無向圖。連通的無向圖只有一個極大連通子圖，即它本身，因為不存在另一個連通的子圖包含的點和邊比它本身還要多，所以叫作極大連通子圖。不連通的無向圖可以拆分為若干個連通的無向圖，如果我們在拆分時注意把能連通的點邊都放在一個連通子圖中，使這個連通子圖足夠大，以至於再多包含一個點或邊它就變成不連通的了，我們稱這個連通子圖為極大連通子圖，也叫連通分量。

下面說極小連通子圖，極小連通子圖只存在於連通的無向圖中，也就是說該圖中只有一個連通分量（極大連通子圖），之所以說它極小，是因為極小連通子圖只要求包含圖中所有頂點及其比頂點數量少一個的邊（且不能成環），也就是說如果給極小連通子圖任意兩個頂點間加入一條邊，則必有環。

這裡的極大和極小不是指一個意思，不要弄混了，極大連通子圖是討論連通分量的，極小連通子圖是討論生成樹的。

提一下有向圖中的極大連通子圖。

有向圖可以分為強連通圖、弱連通圖、單向連通圖、不連通圖。極大連通子圖一般只在強連通圖中討論，即強連通分量。至於有向圖的這幾種型別，