一、極大強(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ì)。