Articulation Vertex / Bridge

我可以往,彼可以來,曰通;通形者,先居高陽,利糧道以戰,則利。《孫子》

Articulation Vertex(Articulation Point)(Cut-vertex)

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

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

Bridge(Cut-edge)

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

無向圖,尋找所有的Articulation Vertex

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

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

這個演算法簡單易懂又容易實作。不過接下來要介紹更快的方法。

原本路線+替代路線=環

移除一個點之後,經過此點的路線被截斷了。要是沒有替代路線,無法繞過點,就會不連通,此點就是關節點。反過來說,如果有替代路線,此點就不是關節點。

原本路線和替代路線,併在一起看,又可以想做是一個環。也就是說:找的到環,就找的到替代路線,可以繞過關節點;找不到環,就找不到替代路線,繞不過關節點。

要在一張圖上找替代路線不太直覺,但是找環就比較直覺了──把圖重新畫成樹的形狀,就容易找環了!要把圖重新畫成樹的形狀,利用Graph Traversal就行了。這裡就利用一下DFS tree吧!

利用DFS tree

任取樹上的一個點。當此點的祖先、此點的子孫想要互通有無,利用tree edge的話,顯然會經過此點;不想利用tree edge的話、不想經過此點的話,就必須利用back edge了。

另外,在DFS tree之中,此點的子樹們之間沒有邊。因此只需要考慮祖先與每一棵子樹之間有沒有back edge。

祖先與每一棵子樹之間都有back edge,則此點不是關節點;祖先與其中一棵子樹之間缺少back edge,則此點就是關節點。

樹根不能套用上述規則,因為樹根沒有祖先。然而樹根更容易判斷是不是關節點。

樹根的子樹們想要互通有無,只能經過樹根。因此當樹根有兩棵以上的子樹,或者說,有兩個以上的小孩,則樹根一定是關節點。

實作時,想要判斷祖先與子孫,可以運用DFS的遍歷時刻。

無向圖,尋找所有的Articulation Vertex

時間複雜度為遍歷的時間複雜度。圖的資料結構為adjacency matrix,便是O(V²);圖的資料結構為adjacency lists,便是O(V+E)。

運用遞迴實作,整合程式碼。

方才的程式碼,如果讓trace[]改為存入遍歷時刻,而不是點的編號,那麼程式碼可以再縮短一點點。

UVa 315 10199

low的意義

low的意義是:不斷往下走tree edge,最後走一次back edge,所能觸及的最高祖先。

low也可以修改成:不斷往下走tree edge、往上走back edge,所能觸及的最高祖先。修改不會影響結果,而且可以精簡程式碼!

無向圖,尋找所有的Bridge

方法類似於尋找關節點。只需要特別當心兩點之間有多條邊的情況。多重邊當中,有一條是tree edge,其餘都是back edge。

UVa 796 610 12783

Dominator

天下何思何慮?天下同歸而殊塗,一致而百慮。天下何思何慮?《易傳.繫辭》

Dominator

一張有向圖,選定一個起點、一個終點。由起點到終點,途中的必經之點、沒有替代路線的點,稱作「支配點」;起點與終點本身也是支配點。途中的必經之邊,則尚未命名。

只要移除了支配點,起點到終點的連繫就被切斷了,呈現不連通的狀態。

想要判斷一個點不是支配點,只要從圖上移除此點,再看看起點到終點是否連通就好了。

支配點就像是交通要衝、軍事要津。守塔遊戲當中,最理想的禦敵之處,通常正是支配點:http://www.kingdomrush.com/

有向圖,給定起點,尋找所有的Dominator

從起點實施Graph Traversal。接下來,移除圖上一個點,再實施一次。原本走得到、這次卻走不到的點,就是被支配的點。反過來說,走不到的點的支配點,就是移除的點。

每一個點都用一次Graph Traversal來判斷是誰的支配點,逐一試驗圖上每一個點,總共執行V+1次的Graph Traversal就可以找出每個點的全部支配點了。

這個演算法簡單易懂又容易實作。不過接下來要介紹更快的方法。

原本路線+替代路線

如果有替代路線,那麼交叉路口之間的點,一定不是支配點!

以下我們考慮抵達終點的情況:原本路線與替代路線,點邊皆異,除了分岔點與終點。分岔點到終點之間的點,一定不是支配點。

給定起點與終點,找到所有「分岔點」,可能有許多個,包含了終點。離起點最近的分岔點,稱作「最高分岔點」。

給定起點與終點,找到所有「支配點」,可能有許多個,包含了起點與終點。離終點次近的支配點,稱作「次低支配點」。

最高分岔點、次低支配點,不見得相同。尤其是麻花辮。

從最高分岔點到終點,尋找路線上每個點的最高分岔點,不斷遞迴,排除所有不是支配點的情況,得到次低支配點。

遞迴窮舉最高分岔點,逼近次低支配點!很特別的對偶。

但是有一個例外:抵達終點的路線只有唯一一條,此時最高分岔點(終點)的父親才是次低支配點。為了應付這個例外,最高分岔點必須強制改成終點的父親。

支配點的支配點,也是支配點。次低支配點的次低支配點,不斷遞迴,得到所有支配點。

【註:最高分岔點,原論文稱作semidominator。次低支配點,原論文稱作immediate dominator。】

利用DFS tree

把圖重新畫成樹的形狀,就容易觀察替代路線了,這裡就利用一下DFS tree吧!

根據DFS的特性,針對一個分岔點,原本路線會在樹上,替代路線不會經過時刻更小的點、只會經過時刻更大的點。

因此,各種路線上,時刻最小的點,就是最高分岔點。時刻大小,代表高低。

我們可以將計算順序定為「時刻從大到小」。DFS樹的後半段(以及父親),涵蓋了所有替代路線!

有向圖,給定起點,尋找所有的最高分岔點

時刻從大到小,每個點依序作為終點,計算最高分岔點sdom。

窮舉所有入邊,從DFS樹的後半段,檢查所有替代路線上的點,從中找到sdom最小者。

sdom是遞推計算的。針對一條入邊,只需沿著DFS樹逆行到頂,檢查一條路徑上的點,從中找到sdom最小者。這一條路徑上的sdom,已經包含了各種替代路線的最高分岔點了。

窮舉所有入邊,也包括了父親。一方面涵蓋替代路線,一方面應付例外。時間複雜度為O(EV)。

找到替代路線上的sdom最小值之後,仿效disjoint-sets forest的精神,順手將路線上每一個點直接連向開頭,減少森林高度。隨著森林的增長,最小值只會越來越小,答案保持正確。原作者宣稱時間複雜度降至O(ElogV)。

原作者進一步降至O(Eα(E,V)),此處省略。

利用特殊資料結構Micro Tree甚至可達O(V+E),但是不實用,只有理論上的價值。

另外,原作者想到了一個奇技淫巧:維護森林時,本來是i點與小孩聯集,改為了i點預先與父親聯集!父親尚未處理,sdom值預設為自己。i點的sdom值小於等於父親。尋找路徑最小值,比較大小是以小孩為主、父親為輔,最小值恰巧不受影響。

有向圖,給定起點,尋找所有的次低支配點

求得最低支配點:從最高分岔點出發的所有路線,找到路線上每個點的最高分岔點,判斷是不是麻花辮。若否,原本的最高分岔點就是次低支配點。若是,則必須遞迴引用路線上每個點的次低支配點。

第一波,時刻從大到小,從DFS樹後半段,找到需要遞迴引用的點。第二波,時刻從小到大,完成引用。時間複雜度同前。

奇技淫巧,可以精簡程式碼。

陣列索引值、陣列數值,從節點編號改成時刻。

Dominator Tree

一張有向圖,選定一個起點,由起點到圖上各點的支配點們,疊合成一棵有向樹,稱作「支配樹」,只有唯一一種。

圖上各點各自連向次低支配點。

學過最短路徑的讀者,可以將支配樹類比為最短路徑樹。疊合所有支配點,成為支配樹;疊合所有最短路徑,成為最短路徑樹。支配點的支配點,也是支配點;最短路徑從頭截下一段,也是最短路徑。

延伸閱讀:遞推演算法

dom(s, t) = { dom(s, from1(t)) ∩ dom(s, from2(t)) ∩ ... } ∪ t

採用遞歸法,計算起點到終點的所有支配點:窮舉起點到終點的所有路線,計算起點到「終點的前一點」的所有支配點;各種路線的支配點們取交集,再補上終點。

以遞推方式,從起點開始,依序計算圖上各點的支配點。然而不幸的是:我們不明白計算順序!

當圖上無環,可以採用拓撲順序,只需遍歷一次。當圖上有環,只好採用偽拓樸順序:「DFS離開點的逆序」,反覆實施數次,趨近正確答案,直到答案不再變動,即是正確答案。

學過最短路徑的讀者,可以將此類比為「Label Correcting Algorithm」。重複遍歷的過程當中,儘管無法確定支配樹的長相,但是可以確定支配樹正在一層一層生長。

最多遍歷V次,每個點最多有V個「終點的前一點」,每一點最多有V個祖先、V個支配點,時間複雜度為O(V³)。

如果只想求支配樹,按理應該可以改成計算起點到終點的次低支配點:窮舉起點到終點的所有路線,計算起點到「終點的前一點」的所有次低支配點的最低共同祖先LCA(取交集),再將終點連上LCA(補上終點)。

但是有向圖的LCA究竟如何定義高低呢?似乎還沒有人研究。

有向圖的關節點

http://verona.dei.unipd.it/~prin08/kickoff/laura.pdf

有向圖的關節點,有兩種定義方式:移除關節點之後,強連通分量變多(雙通變單通、不通)、弱連通分量變多(有通變不通)。

尋找所有的強連通關節點:圖上任選一點,找出此點出發的支配樹、以及抵達此點的支配樹。這兩棵樹,除去樹根與樹葉之後所剩下的節點,取聯集,即是強連通關節點──但是不包含樹根。樹根必須另行判斷是否為關節點。

尋找所有的弱連通關節點:改為取交集。

UVa 11902 Sphere EN BIA

Component

Connected Graph

一張圖,如果所有兩點之間皆得以邊相通,這張圖就是一張連通的圖。例如一棵樹就是一張連通的圖。

Connected Component(Component)
(1-connected component in undirected graph)

譯作「連通分量」、「連通成分」、「連通元件」、「連通單元」等等,也有人簡稱為「分量」,沒有正式翻譯。

當一張無向圖不連通、分隔成幾個區塊的時候,每一個區塊都是一個「連通分量」。一個獨立的點也是一個連通分量。

一張無向圖的連通分量們,不可能互相重疊。一個連通分量是指在連通的情況下,點數盡量最多、擴展範圍最大的一個子圖;因此,從一個連通分量當中,切下一小塊仍舊連通的子圖,並不能叫做連通分量。

運用Graph Traversal就能找到一張無向圖的所有連通分量。

UVa 459 10765

Biconnected Component(Block)
(2-vertex-connected component in undirected graph)

一張無向圖上,不會產生關節點的連通分量,稱作「雙連通分量」。一張無向圖的雙連通分量們,通常會互相重疊,重疊的部分都是原圖的關節點。

把一個雙連通分量視作一個點,把一個關節點也視作一個點,凡有接觸就添上一條邊,如此可以建立出一棵樹,通常稱作BCC Tree或Block Tree。

Bridge-connected Component
(2-edge-connected component in undirected graph)

一張無向圖上,不會產生橋的連通分量,稱作「橋連通分量」。

兩個點之間沒有橋,就至少有兩條不同的路徑。這兩條路徑勢必形成一只環。一個橋連通分量,想必是由很多環交疊而成的。

把一個這樣的連通分量視作一個點,凡有接觸就添上一條邊,如此可以建立出一棵樹。

ICPC 5135 4839 7605

Strongly Connected Component
(1-connected component in directed graph)

在無向圖當中,只要邊邊相連,即形成連通,不必在意方向。在有向圖當中,由於有了方向限制,因此細分為「強連通」和「弱連通」:所有兩點之間,雙向都有路可通,則是「強連通」;所有兩點之間,至少單向有路可通,則是「弱連通」。

一張有向圖的「強連通分量」,是所有兩點之間,雙向皆有路可通的連通分量。一張有向圖的強連通分量們,不可能互相重疊。

兩個點來回都有路徑,這兩條路徑勢必形成一只有向環。一個強連通分量,想必是由很多有向環交疊而成的。

要是把一張圖的各個強連通分量,各自收縮成一個點,如此圖上就沒有環,形成有向無環圖(DAG)。這個手法很有用處──沒有環的圖,常常會有效率極佳、令人眼睛一亮的演算法。當遇到一張有環的圖,不妨先把每個強連通分量統統收縮,簡化問題的複雜程度。

UVa 11504 11709 11770 11838

Weakly Connected Component

一張有向圖的「弱連通分量」,是所有兩點之間,至少單向有路可通的連通分量。一張有向圖的弱連通分量們,通常會互相重疊。

一個弱連通分量,可以看作是強連通分量的縮圖當中的一條有向路徑。要找最大的弱連通分量,即是縮圖當中,涵蓋最多原點的一條有向路徑。

UVa 11324

Component: Tarjan's Algorithm

演算法

一張無向圖,找到所有的Bridge-connected Component。亦可進一步收縮所有的BCC、收縮所有的環,讓原圖變成一棵樹。

一張有向圖,找到所有的Strongly Connected Component。亦可進一步收縮所有的SCC、收縮所有的環,讓原圖變成一張有向無環圖。

為什麼要收縮呢?當圖上有環,難以設計有效率的演算法。收縮所有的環,讓圖變成樹、有向無環圖,就容易解決問題了!

無向圖:
尋找所有的Bridge-connected Component、收縮所有的環

利用尋找所有橋的演算法,輔以堆疊,找到所有的BCC。

一、實施DFS。
二、拜訪階段,
  針對每一個點,計算自身與子孫所能觸及的最高祖先。
  (觸及是指:不斷往下走tree edge、往上走back edge。)
三、回溯階段,
  每當發現某一點恰是最高祖先,即表示此點與子孫已經形成BCC。
  從堆疊之中刪除BCC,避免再次處理。

時間複雜度等於一次DFS的時間。圖的資料結構為adjacency matrix,便是O(V²);圖的資料結構為adjacency lists,便是O(V+E)。

有向圖:
尋找所有的Strongly Connected Component、收縮所有的環

與無向圖幾乎相同。不必擔心多重邊的問題,但是要小心處理forward edge和cross edge。

一、實施DFS。
二、拜訪階段,
  針對每一個點,計算自身與子孫所能觸及的最高祖先。
  觸及是指:不斷走任意邊,但是不能走到曾經形成的SCC。
  (forward edge和cross edge可能連往已經移除的SCC,不得計算。)
三、回溯階段,
  每當發現某一點恰是最高祖先,即表示此點與子孫已經形成SCC。
  從堆疊之中刪除SCC,避免再次處理。

Component: Kosaraju's Algorithm

演算法

一張有向圖,找到所有的Strongly Connected Component。亦可進一步收縮所有的SCC、收縮所有的環,讓原圖變成一張有向無環圖。

原圖,顛倒每一條邊的方向,得到新圖。所有SCC的位置依舊相同!

縮圖亦如是!原縮圖、新縮圖都是有向無環圖。以原縮圖的拓樸順序,遍歷新縮圖,依序摘下每個點,每個點都是一個SCC。而且只有入邊、沒有出邊。

改以尚未收縮的原圖、新圖來詮釋。以原圖的「偽」拓樸順序,遍歷新圖,依序摘下每個連通分量,每個連通分量都是一個SCC。而且沒有出邊,不怕走過頭。

原圖有環,沒有拓樸順序,只好以偽物代替:「DFS離開點的順序,然後頭尾顛倒」或簡述為「DFS離開點的逆序」。雖然這個順序既非原圖、亦非縮圖的拓樸順序,但是可以優先遇見應該摘下的連通分量。

一、原圖實施DFS,找偽拓樸順序。
  (每一棵SCC子樹,必然連續遍歷。)
二、新圖實施DFS/BFS,以偽拓樸順序找連通分量。
  每一棵DFS tree/BFS tree,對應到每一個SCC。
  (確認哪些點是同一個SCC。)

時間複雜度為兩次DFS的時間,以及顛倒所有邊的時間。

資料結構是adjacency matrix,不必變動資料結構就可以達到顛倒所有邊的效果,總時間複雜度O(V²);資料結構是adjacency lists,需要顛倒所有邊,總時間複雜度O(V+E)。

2-Satisfiability

兩個至少選一個

首先介紹嘮叨媽媽和偏食小孩的討價還價問題:

青椒、菠菜至少選一個。青椒、番茄至少選一個。番茄、苦瓜至少選一個。苦瓜、菠菜至少選一個。不吃苦瓜、不吃青椒,至少選一個。選擇哪些菜色,才能成全媽媽的愛心,滿足小孩的任性?

2-Satisfiability(2-SAT)

邏輯學有一個相似的問題。

X₀、X₁、……是變數,變數值是true或false。變數可以重複出現。變數可以加上not。括號之間是and,括號裡面是or,格式是固定的。

括號之間是and:每個括號都是true,整個式子才是true。

括號裡面是or:「左右皆true」或者「左true右false」或者「右true左false」,整個括號才是true。

如何設定變數值,讓整個式子成為true呢?

2-Satisfiability另一種觀點

N個變數。每個變數都要設定數值為true或false。

一個變數X,要嘛X = true,要嘛X = false。換句話說,要嘛X = true,要嘛¬X = true。兩個元件X與¬X二選一。

N個變數,一共2N個元件。最後選出N個元件。

一個括號裡面有兩個元件,括號必須成為true。

正向思考:左右皆選、左選右不選、左不選右選。

可選可不選。這樹立了模稜兩可的規則,難以設計演算法。

逆向思考:不選這個,就必須選另外一個。

一定要選。這樹立了一定要遵守的規則,容易設計演算法。

以有向圖做為模型

把元件之間的「依賴關係」建立成有向圖。

一、依序處理每個括號。
 甲、變數不同。例如(X or Y)。
  回、不選X(選了¬X),就一定要選Y:建立一條有向邊¬X → Y。
  回、不選Y(選了¬Y),就一定要選X:建立一條有向邊¬Y → X。
 乙、變數相同。例如(X or X)。
  回、一定要選X,一定不能選¬X:建立一條有向邊¬X → X。
    (一旦選¬X,就連帶選X,產生矛盾。只好選X。) 
 丙、變數相同,一正一反。例如(X or ¬X)。
  回、無論選X或選¬X都行:不必建立邊。

判斷是否有解

凡無解,必有一個環同時穿過X與¬X。

證明若右則左:

X與¬X必須二選一。選了一個點,點可及之處也得選。當X與¬X同屬一環,無論選哪一個,都會連帶選到對方,導致矛盾、導致無解。

證明若左則右:

引發矛盾無解的情況是X必選,X同時連向Y與¬Y。(可以推廣成有中繼點。可以推廣成Y與¬Y是祖孫關係。)

既然存在X→Y,就表示某一個括號是¬X與Y,也一定存在¬Y→¬X。同理,既然存在X→¬Y,也一定存在Y→¬X。

補上新邊,可以發現,如果有任何引發矛盾無解的情況,那麼X和¬X必同屬一環。

實作時,判斷X與¬X是否在同一個SCC即可。SCC裡面是一群交織的環,SCC之間沒有環。

找出其中一組解

依序設定每一對元件X與¬X。若是祖孫,則選擇孫,避免矛盾;若不是祖孫,則任一皆可。另外也必須確認先前設定的元件,是否產生衝突。

可以找出字典順序最小的解。時間複雜度為O(VE)。

一、建立有向圖。
二、依序判斷每一對元件X與¬X何者為解:
 甲、嘗試X作為解:若X可及之處存在非解者,則X非解。
 乙、嘗試¬X作為解:若¬X可及之處存在非解者,則¬X非解。
 丙、確認X與¬X何者為解之後,將其可及之處全數標記為解。

採用逆向拓樸順序。時間複雜度為O(V+E)。

一、建立有向圖。
二、尋找所有SCC。
三、收縮每個SCC,成為有向無環圖DAG。
  (同一個SCC裡面的點,必須同進退;要嘛全選,要嘛全不選。)
四、尋找縮圖的拓樸順序。
五、在縮圖上,以逆向拓樸順序,設定解。

兩個只能選一個

把or改成xor。留給讀者解決。

三個至少選一個

括號裡面改成三個變數,稱作3-SAT。NP-complete。沒有快速的演算法。

3-SAT被認為是最根本的NP-complete問題。所有NP-complete問題都可以重新改寫成3-SAT問題,然後用3-SAT演算法求解。然而式子繁雜冗長,實務上沒有人這麼做。但是理論上還是有人這麼做,請參考TAOCP 4B(目前只有草稿Volume 4 Fascicle 6)。

UVa 10319 11294 11861 11930 ICPC 3211 3713 4452 4849

Cactus Graph

Cactus Graph

http://en.wikipedia.org/wiki/Cactus_graph

http://tmtacm.blogspot.tw/2013/05/blog-post.html

Directed Cactus Graph

有向圖上,每條邊隸屬於恰好一個有向簡單環。另一種說法:許多有向環,相互銜接成樹狀,接縫恰好是一點。

要判斷一張有向圖是不是仙人掌,原理就跟判斷關節點的方法相同。

使用 DFS ,會遇到三種情形:

一、 (i, j) 是 cross edge 或 forward edge:

    tree edge 和 back edge 剛好構成仙人掌全部的邊,
    所以不會有 cross edge 與 forward edge。
    如果有的話,就表示不是仙人掌。

    實作時,可利用 DFS stack 判斷,
    如果 j 不在 stack 又已經拜訪過(也就是 j 已經從 stack 彈出來了),
    則表示 (i, j) 一定是 cross edge 或 forward edge。

二、 (i, j) 是 back edge:

    如果從 i 就已經有路可以走回到 i 的祖先(也是會經過其他的back edge),
    此時 j 又走回到 i 的祖先,表示環重疊,不是仙人掌。

    範例一:12 23 34 45 56 62 53!       // i = 5 and j = 3
    範例二:12 23 34 45 51! 53!         // 怎麼好像在寫棋譜...

    實作時,累加 i 回到祖先的路有幾條,只能是恰好一條。
    可利用關節點演算法的原理,記錄 i 可到達的最高祖先。

三、 (i, j) 是 tree edge:

    與 2. 的概念很像,不過要在 DFS 的回溯階段才能判斷。
    如果從 i 就已經有路可以走回到 i 的祖先,
    此時 j 又有路走回到 i 的祖先,表示環重疊,不是仙人掌。

    範例一:12 23 34 45 56! 67! 72! 58! 89! 91!     // i = 5 and j = 8
    範例二:12 23 34 45 51! 58! 89! 91!             // 同上

    實作時,累加 i 回到祖先的路有幾條,只能是恰好一條。和(二)一起累加。
    可利用關節點演算法的原理,記錄 i 可到達的最高祖先。

DFS 結束之後,
最後要判斷 DFS 是否能順利走到圖上所有點。

附註:樹根不必走到祖先,要當作例外處理。可以選定任何一點作為樹根。

UVa 10510 ICPC 3514 4045