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