Articulation Vertex / Bridge

Articulation

Articulation乃「關節」之意,骨骼與骨骼銜接的地方就是關節。關節一旦被拆開,肢體之間的連繫就被切斷了。

Articulation Vertex(Articulation Point)

Articulation Vertex中文稱作「關節點」。是讓一張無向圖維持連通,不可或缺的點。只要從一張無向圖上移除了關節點(以及與之相連的邊),就會讓這張圖分離成更多部分,呈現不連通的狀態。

Bridge

Bridge中文稱作「橋」。只要從一張無向圖上移除了橋,就會讓這張圖分離成更多部分,呈現不連通的狀態。

尋找一張圖上所有的Articulation Vertex

要判斷一個點是不是關節點,只要從圖上移除此點,再看看圖是否連通就好了;要判斷連通,可以使用任何一種Graph Traversal演算法。

每一個點都用一次Graph Traversal演算法來判斷是不是關節點,逐一試驗圖上每一個點,總共執行V次的Graph Traversal演算法就可以找出全部的關節點了。V為圖上的點數。

這個演算法簡單易懂又容易實做,只不過這個演算法還不夠漂亮。下面要介紹更妙的方法。

觀察Articulation Vertex的性質

移除關節點所造成的影響,可以想做是:原本經過關節點的路線中斷後,沒有其他替代路線得以避過關節點,結果造成這張圖不連通。反而言之,如果有替代路線,就不會形成關節點。

替代路線和原路線,併在一起看,又可以想做是環(cycle)。如果有環,就不會形成關節點。

要觀察環──把圖重新畫成樹的形狀,就更容易觀察環了!所以接著就來觀察一下DFS trees吧!

Articulation Vertex與DFS Trees的關係

上圖中,屬於DFS trees的邊以實線表示,不屬於DFS trees的邊則以虛線表示。注意到無向圖的DFS trees不會有cross edges,所以會構成環的邊,就只有back edges,也就是圖中的虛線。

一個點若是關節點,則此點的子孫當中,有些子孫沒有替代路線、沒有back edges得以避過關節點,而無法到達此點的祖先。無法到達此點的祖先的話,也不可能到達更遠的地方了。

一個點若非關節點,則此點的子孫們必有替代路線、有back edges得以避過此點,而到達其他點。反方向亦然。

至於一個點的祖先們自己如何相連、子孫們自己如何相連、其他不包含此點的子樹上的點們自己如何相連,都跟此點是不是關節點扯不上關係。

Articulation Vertex與其子樹們的關係

把一個點的子孫,重新視作是幾棵子樹,以子樹的觀點,進行更細緻的分析,看看能不能發現什麼。

上圖中在檢查第1點是不是關節點。第1點的子孫們,共可分為兩棵子樹。可以發現,在其中任何一棵子樹當中,只要子樹的其中一點有一條back edge連向第1點的祖先,那麼這棵子樹上的所有點,都可以藉由這條back edge來避過第1點,到達第1點的祖先,或者到達更遠的地方了!

一個點若是關節點,則此點的子樹當中,會有點無法避過此點,而無法到達此點的祖先,也不可能到達更遠的地方了。

一個點若非關節點,則此點的子樹當中,各個子樹都各自有一條以上的back edge,得以避過此點,而到達此點的祖先。因此也就可以到達其他地方。

樹根比較特別,沒辦法套用上述規則,因為樹根並沒有祖先。不過樹根的分析更簡單:無向圖的DFS trees決不會有cross edge,也就是說樹根的各棵子樹之間,除了通過樹根的路線之外,決不會有替代路線。所以,若樹根有兩個以上的小孩,則樹根一定會是關節點。

尋找一張圖上所有的Articulation Vertex

要判斷祖先,可以利用DFS的遍歷順序。

上方的程式碼中,如果讓a[]直接存入遍歷順序值,而不是點的編號,則程式碼可以再縮短一點點。

UVa 315 10199

如何尋找一張圖上所有的Bridge

方法類似於尋找關節點,所以不再覆述。

橋有個頗強的性質:環上的邊決不會成為橋,但是環上的點有可能成為關節點。

UVa 796