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尋找Articulation Vertex

任取樹上的一個點，當這個點的祖先與每一棵子樹想要互通有無，利用tree edge的話，顯然會經過此點；另一方面，不想利用tree edge的話，不想經過此點的話，就必須利用back edge了。

在DFS tree之中，子樹與子樹之間不會有邊，所以只需要考慮祖先與子樹之間有沒有back edge。

這也就是說，祖先與每一棵子樹之間都有back edge的話，該點就不是關節點；祖先與其中一棵子樹之間缺少back edge的話，該點就是關節點。

樹根沒有辦法直接套用上述規則，因為樹根沒有祖先。然而樹根更加容易判斷是不是關節點。

如果樹根的各棵子樹想要互通有無，除了通過樹根之外，決不會有替代路線。所以，若樹根有兩棵以上的子樹，或者說樹根有兩個以上的小孩，則樹根一定是關節點。

實作時，要判斷祖先與子孫，可以運用DFS的遍歷順序。

尋找一張無向圖上所有的Articulation Vertex（Tarjan's Algorithm）

bool adj[9][9]; // 無向圖，adjacency matrix。 int dis[9]; // DFS遍歷順序，用來判斷祖先與子孫。 int grand[9]; // 紀錄該點的子孫們用back edge連到的最高祖先。 // 例如第4點的子孫們， // 有back edge連到祖先第grand[4]點。 int t = 0; // 時刻。 void DFS(int p, int i) // 第p點是第i點的父親 { dis[i] = ++t; // 紀錄遍歷順序 grand[i] = i; // 預設為沒找到back edge int child = 0; // 紀錄第i點有幾個小孩 bool ap = false; // 紀錄第i點是不是關節點 for (int j=0; j<9; ++j) // 進行DFS if (adj[i][j] && j != p) // 避免回頭路 if (dis[j]) // back edge { // 紀錄最高的祖先。 if (dis[j] < dis[grand[i]]) grand[i] = j; } else // tree edge { child++; DFS(i, j); // 紀錄第i點的子孫們，利用back edge連到的最高祖先。 if (dis[grand[i]] < dis[grand[j]]) grand[i] = grand[j]; // 第i點的祖先、第i點的其中一棵子樹（樹根為第j點） // 兩者之間缺少back edge，因此第i點為關節點。 if (dis[grand[j]] >= dis[i]) ap = true; } // 判斷是不是關節點。樹根和非樹根分開判斷。 if (i == p && child > 1 || i != p && ap) cout << "第" << i << "點是關節點"; } void articulation_vertex() { memset(dis, 0, sizeof(dis)); t = 0; // 進行DFS for (int i=0; i<9; ++i) if (!dis[i]) DFS(i, i); }

上方的程式碼中，如果讓grand[]改為存入遍歷順序值，而不是點的編號，那麼程式碼可以再縮短一點點。

bool adj[9][9]; int dis[9]; int low[9]; // 紀錄該點子孫們用back edge連到的最高祖先（的遍歷順序）， // 也就是遍歷順序盡量小的點，故取名為low。 // 例如第4點的子孫們， // 有back edge連到遍歷順序為low[4]的祖先。 int t = 0; void DFS(int p, int i) { dis[i] = low[i] = ++t; int child = 0; bool ap = false; for (int j=0; j<9; ++j) if (adj[i][j] && j != p) if (dis[j]) // back edge { // 紀錄遍歷順序較小的，即是最高祖先。 low[i] = min(low[i], dis[j]); } else // tree edge { child++; DFS(i, j); // 紀錄遍歷順序較小的，即是最高祖先。 low[i] = min(low[i], low[j]); if (low[j] >= dis[i]) ap = true; } if (i == p && child > 1 || i != p && ap) cout << "第" << i << "點是關節點"; }

也可以改為在DFS結束之後，再來判斷關節點。程式碼切割成兩階段，比較清爽。

bool adj[9][9]; int dis[9], low[9], t = 0; void DFS(int p, int i) { dis[i] = low[i] = ++t; for (int j=0; j<9; ++j) if (adj[i][j] && j != p) if (dis[j]) low[i] = min(low[i], dis[j]); else { DFS(i, j); low[i] = min(low[i], low[j]); } } bool articulation_vertex(int i) { // 樹根要特別處理 if (i是樹根) return i點的小孩數目 > 1; for (int j=0; j<9; ++j) if (adj[i][j] && (i,j) is tree edge) if (low[j] >= dis[i]) return true; return false; } void articulation_vertex() { memset(dis, 0, sizeof(dis)); t = 0; // 進行DFS for (int i=0; i<9; ++i) if (!dis[i]) DFS(i, i); // 尋找所有關節點 for (int i=0; i<9; ++i) if (articulation_vertex(i)) cout << "第" << i << "點是關節點"; }

UVa 315 10199

尋找一張無向圖上所有的Bridge

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

UVa 796 610

Articulation Vertex與Bridge的性質

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

【待補文字】

延伸閱讀：判斷一張有向圖是不是Directed Cactus

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

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

使用 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 是否能順利走到圖上所有點。

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

int adj[9][9]; // adjacency matrix int dis[9]; // DFS遍歷順序 int low[9]; // 可以走回到的最高祖先（的遍歷順序） int t = 0; // 時刻 bool v[9]; // 已經結束拜訪的節點 bool DFS(int p, int i) { dis[i] = low[i] = ++t; int c = 0; for (int j=0; j<9; ++j) if (!dis[j]) // tree edge { // 一旦發現不是仙人掌就可以馬上結束 if (!DFS(i, j)) return false; // 找到一條走回到i點祖先的路 if (low[j] < dis[i]) if (++c > 1) return false; // 更新i點可走到的最高祖先 low[i] = min(low[i], low[j]); } else // back edge { // 排除 forward edge 與 cross edge 的情況 if (v[j]) return false; // 找到一條走回到i點祖先的路 if (dis[j] < low[i]) if (++c > 1) return false; // 更新i點可走到的最高祖先 low[i] = min(low[i], dis[j]); } v[i] = true; return p == -1 ? true : c == 1; } bool directed_cactus() { memset(d, 0, sizeof(d)); memset(v, false, sizeof(v)); t = 0; // 也要確認DFS是否有走到圖上所有點 return DFS(-1, 0) && t == V; }

UVa 10510

Dominator

一張有向圖上，選定一個起點，再選定一個點。由起點走往該點的必經之點（們），就是該點的Dominator，是一個集合。

按照定義，自己也是自己的Dominator。自己支配自己。

演算法：一個點的Dominator

移除選定的點，然後由起點進行Graph Traversal，無法到達的點的Dominator就是選定的點。小心原圖可能有許多塊連通分量。

圖的資料結構為adjacency matrix的話，便是O(V^2)；圖的資料結構為adjacency lists的話，便是O(V+E)。

UVa 11902

Dominator Tree

每個點相互支配的關係，可以簡單表示成一棵有向樹，樹根是起點。

演算法：所有點的Dominator

dom(x) = dom(1st parent of x) ∩ dom(2nd parent of x) ∩ ...

按照拓樸順序，依序計算每個點的Dominator，記錄成Dominator Tree的形式。不斷反覆計算，直到答案正確為止。

時間複雜度為O((V+E)*K)，K為收斂的次數。當給定的圖是有向無環圖DAG，K = 1。

演算法：所有點的Dominator（Lengauer-Tarjan Algorithm）

http://www.cl.cam.ac.uk/~mr10/lengtarj.pdf

時間複雜度O(ElogV)。實際執行起來，並不比前面的方法來得快。

演算法：所有點的Dominator

O(E*alpha(E,V))。可以加速到O(V+E)，但是方法相當複雜，並不實用。

【待補文字】

延伸閱讀：有向圖的關節點與橋

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

Connected Graph

這不是一個專有名詞。對於一張圖來說，如果所有兩點之間皆得以邊相通，這張圖就是一張連通的圖。例如一棵樹就是一張連通的圖。

Connected Component（Component）
【註：1-connected component in undirected graph】

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

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

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

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

UVa 10765

Biconnected Component（Block）
【註：2-vertex-connected component in undirected graph】

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

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

常常被誤認為是Biconnected Component的一種連通分量
【註：2-edge-connected component in undirected graph】

一張無向圖上，不會產生橋的連通分量。常被誤認為「雙連通分量」。

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

Strongly Connected Component
【註：1-connected component in directed graph】

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

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

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

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

UVa 11504 11709 11770 11838

Weakly Connected Component

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

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

UVa 11324

演算法

找到一張有向圖所有的強連通分量。亦可檢驗圖上是否有環。亦可收縮圖上所有的環。

觀察強連通分量的縮圖，觀察DAG的先後順序。

一、找到一個拓樸順序。
　　（一種方式是以DFS的離開順序的反序，作為拓樸順序。）
二、顛倒所有邊的方向。
　　所有強連通分量的位置依舊相同！
三、新圖依照原圖的拓樸順序，以DFS或BFS實施連通性測試。
　　每一棵DFS tree或BFS tree，
　　都對應一個強連通分量。

時間複雜度

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

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

int adj[9][9]; // adjacency matrix bool visit[9]; // DFS visit record vector<int> finish[9]; // DFS的離開順序 int scc[9]; // 每個點的強連通分量編號 void DFS1(int i) { visit[i] = true; for (int j=0; j<9; ++j) if (adj[i][j] && !visit[j]) DFS1(j); finish.push_back(i); } void DFS2(int i, int c) { cout << "第" << c << "個強連通分量"; cout << "包含第" << i << "點"; scc[i] = c; // 設定第i點屬於第c個強連通分量 visit[i] = true; for (int j=0; j<9; ++j) if (adj[j][i] && !visit[j]) // 顛倒所有邊的方向 DFS2(j, c); } void kosaraju() { finish.clear(); memset(visit, false, sizeof(visit)); for (int i=0; i<9; ++i) if (!visit[i]) DFS1(i); memset(visit, false, sizeof(visit)); for (int i=9-1; i>=0; --i) if (!visit[finish[i]]) // 原圖的拓樸順序 DFS2(finish[i], c++); // 找到一個強連通分量 } int adj[9][9]; bool visit[9]; vector<int> fin[9]; // 依照離開順序排好所有點 int contract[9]; // 每個點收縮到的點 void DFS1(int i) { if (visit[i]) return; visit[i] = true; for (int j=0; j<9; ++j) if (adj[i][j]) DFS1(j); finish.push_back(i); } void DFS2(int i, int p) { if (visit[i]) return; visit[i] = true; for (int j=0; j<9; ++j) if (adj[j][i]) // 顛倒所有邊的方向 DFS2(j, n); contract[i] = p; // 收縮至第p點 } void kosaraju() { finish.clear(); memset(visit, false, sizeof(visit)); for (int i=0; i<9; ++i) DFS1(i); memset(visit, false, sizeof(visit)); for (int i=9-1; i>=0; --i) DFS2(finish[i], finish[i]); }

演算法

強連通分量由環組成。利用前述找關節點的手法，來找出環。

一、執行DFS。
二、執行過程中，針對每一個點，
　　都計算以該點為根的子樹，
　　藉由back edge和tree edge所能回到的最高祖先。
　　（與關節點演算法的主要差異：
　　　關節點演算法走back edge時，走完了就停。
　　　此處是不斷走back edge和tree edge，不斷找路往祖先走。）
三、在回溯階段時，
　　每當發現以某一點為根的子樹，已經形成一個完整的SCC，
　　則馬上從目前的DFS Forest上面移除此SCC，
　　並且將此SCC儲存到其他地方。

時間複雜度等於一次DFS的時間。圖的資料結構為adjacency matrix的話，便是O(V^2)；圖的資料結構為adjacency lists的話，便是O(V+E)。

int adj[9][9]; // adjacency matrix int dis[9], low[9], t = 0; // 遍歷順序、追溯到的最高祖先（的遍歷順序） int s[9], *stack; // 堆疊 bool instack[9]; // 紀錄DFS forest目前還有哪些點 int contract[9]; // SCC縮圖 void DFS(int i) { dis[i] = low[i] = ++t; instack[i] = true; *++stack = i; for (int j=0; j<9; ++j) if (adj[i][j]) { if (!dis[j]) DFS(j); if (instack[j]) low[i] = min(low[i], low[j]); } // 形成 SCC，從目前的 DFS forest 移除它。 // i 點也是 SCC 裡面，發現時間最早的點。 if (dis[i] == low[i]) { while (*stack != i) { contract[*stack] = i; instack[*stack] = false; stack--; } contract[*stack] = i; instack[*stack] = false; stack--; } } void tarjan() { memset(dis, 0, sizeof(dis)); memset(instack, false, sizeof(instack)); t = 0; stack = s; for (int i=0; i<9; ++i) if (!dis[i]) DFS(i); } int adj[9][9]; // adjacency matrix，兩點間可能有多條邊。 int dis[9], low[9], t = 0; // 遍歷順序、追溯到的最高祖先（的遍歷順序） int s[9], *stack; // 堆疊，紀錄已經遍歷過但是尚未收縮的點。 // disjoint-set forest，用來紀錄縮圖。 int p[9]; void init() {...} int find(int x) {...} void union(int x, int y) {...} void DFS(int p, int i) { dis[i] = low[i] = ++t; for (int j=0; j<9; ++j) if (adj[i][j]) if (!dis[j]) { *++stack = j; DFS(i, j); low[i] = min(low[i], low[j]); if (low[j] > dis[i]) // 子孫沒有形成環 stack--; // pop j else if (low[j] == dis[i]) // 子孫形成環 { while (*stack != j) union(*stack--, i); union(*stack--, i); // pop j } } else if (j != p || j == p && adj[i][j] >= 2) low[i] = min(low[i], dis[j]); } void tarjan() { init(); memset(d, 0, sizeof(d)); n = 0; stack = s; for (int i=0; i<9; ++i) if (!dis[i]) DFS(-1, i); int vertex = 0; for (int i=0; i<9; ++i) if (i == f(i)) vertex++; cout << "收縮後共有" << vertex << "點"; }

Orientation

一張無向圖，無向邊改成有向邊，替每一條邊選擇一個方向，稱做「定向」。

根據Robbins' theorem，沒有橋的無向圖，一定能改成強連通的Orientation，反之亦然。

UVa 610 10972

Underlying Graph

一張有向圖，有向邊換成無向邊，稱做「底圖」。

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

Vertex Connectivity（Connectivity）

一張圖的「點連通度」是指：欲讓圖不連通，最少需要從圖上拿掉多少個點？

換句話說，一張圖上隨意拿掉「點連通度」減一個點，一定還是連通的。

根據Menger's Theorem，此問題等價於：兩點之間，點不重覆（端點除外）的路徑同時最多有幾條（vertex-disjoint paths）？點連通度等於所有兩點的最小值。

根據Max-Flow Min-Cut Theorem，此問題又等價於：點容量為一、邊無容量，求所有兩點之間的最大流的最小值。

【待補圖片】

Edge Connectivity

一張圖的「邊連通度」是指：欲讓圖不連通，最少需要從圖上拿掉多少條邊？

換句話說，一張圖上隨意拿掉「邊連通度」減一條邊，一定還是連通的。

根據Menger's Theorem，此問題等價於：兩點之間，邊不重覆的路徑同時最多有幾條（edge-disjoint paths）？邊連通度等於所有兩點的最小值。

根據Max-Flow Min-Cut Theorem，此問題又等價於：邊容量為一、點無容量，求所有兩點之間的最大流的最小值。

【待補圖片】