Posted on 2010-08-01 21:24
Kevin_Zhang 閱讀(299)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
圖論
割頂：
連通圖G的一個(gè)頂點(diǎn)子集V，如果刪除這個(gè)頂點(diǎn)子集和它所附帶的邊后，圖便不再連通。則稱(chēng)V是G的割頂集。
最小割頂集中頂點(diǎn)的個(gè)數(shù)，稱(chēng)為G的連通度。連通度等于1時(shí)，割頂集中的那個(gè)頂點(diǎn)叫做割頂。
注意：完全圖的連通度為總頂點(diǎn)數(shù)－1；
牽一發(fā)而動(dòng)全身的點(diǎn)稱(chēng)為割點(diǎn)
邊連通度：
連通圖G的一個(gè)邊子集E，如果刪除邊子集的邊后，圖便不再連通，則稱(chēng)E是G的橋集。
含有最小邊數(shù)的橋集的邊數(shù)|E|稱(chēng)為G的邊連通度。|E|＝1時(shí)，E中的邊叫做橋。
注意：規(guī)定不連通圖的邊連通度為0；完全圖的邊連通度為總頂點(diǎn)數(shù)－1；
連通圖的兩個(gè)特征：
1 連通度<=邊連通度<=頂點(diǎn)數(shù)
2 頂點(diǎn)數(shù)大于2的2連通圖的充分必要條件是任兩個(gè)頂點(diǎn)在一個(gè)圈上.(沒(méi)搞明白)
塊的概念：
沒(méi)有割點(diǎn)的連通子圖，這個(gè)子圖中的任何一對(duì)頂點(diǎn)之間至少存在兩條不相交的路徑，或者說(shuō)要使兩個(gè)站點(diǎn)同時(shí)發(fā)生故障
至少兩個(gè)站點(diǎn)同時(shí)發(fā)生故障，這種二連通分支稱(chēng)為塊．
顯然各個(gè)塊之間的關(guān)系有如下兩種：
1 互不連接
2 通過(guò)割頂連接(割頂可以屬于不同的塊，也可以?xún)蓚€(gè)塊公有一個(gè)割頂)
引申：無(wú)向圖尋找塊，關(guān)鍵是找割頂．
滿(mǎn)足是割頂?shù)臈l件：
1 如果u不是根，u成為割頂?shù)某湟獥l件：當(dāng)且僅當(dāng)存在u的一個(gè)兒子頂點(diǎn)s,從s或者s的后代點(diǎn)到u的祖先點(diǎn)之間不存在后向邊．
2 如果u是根，則u成為割頂當(dāng)且僅當(dāng)它不止有一個(gè)兒子點(diǎn)．
怎樣求割頂：
引入一個(gè)標(biāo)號(hào)函數(shù)：
low(u)=min{dfn(u),low(s),dfn(w)}; s是u的一個(gè)兒子，(u,w)是后向邊
顯然low(u)值是u或者u的后代所能追溯到的最早(序號(hào)小)的祖先序號(hào)．
利用標(biāo)號(hào)函數(shù)low，分析求割頂?shù)牟襟E：
頂點(diǎn)u不為根且為割頂?shù)臈l件是當(dāng)且僅當(dāng)u有一個(gè)兒子s，使得low(s)>=dfn(u),即s和s的后代不會(huì)追溯到比
u更早的祖先點(diǎn)．
low(u)的計(jì)算步驟：
1 low(u)=dfn(u);
//u在dfs過(guò)程中首次被訪(fǎng)問(wèn)
2 low(u)=min{low(u),dfn(w)}
//檢查后向邊(u,w)時(shí)
3 low(u)=min{low(u),low(s)}
//u的兒子s的關(guān)聯(lián)邊被檢查時(shí)
注意：對(duì)任何頂點(diǎn)u計(jì)算low(u)的值是不斷修改的，只有當(dāng)以U為根的dfs子樹(shù)和后代的low值,dfn值全部出現(xiàn)以后才停止.