# 110 選手班 - 進階圖論 ###### tags: `宜中資訊` `CP` Ccucumber12 2021.08.20 --- ## Outline - DFS Tree - Biconnected Component - Strongly Connected Components - 2-SAT - Maximum Bipartite Matching --- ## DFS Tree ----  ---- ### Undirected Graph - Tree Edge: - 樹邊 - Real edge on DFS tree - unvisited - Back Edge: - 回邊 - From descendent to ancestor - visited ---- ### Directed Graph - Tree Edge: - Back Edge: - Foward Edge: - 前向邊 - From ancestor to descendent - Cross Edge: - 交錯邊 - From a family to another ----  ---- ### Cycle - Undirected Graph: - Back Edge - Directed Graph: - Back Edge - Cross Edge(possibly) ---- - $d[x]$: time that $x$ enters DFS - $f[x]$: time that $x$ exists DFS - For Edge $(i,j)$: - $d[i] < d[j] < f[j] < f[i]$: Tree / Foward - $d[j] < d[i] < f[i] < f[j]$: Back - $d[j] < f[j] < d[i] < f[i]$: Cross ---- ### Simplify The Problem consider the two/four edges' performance --- ## Biconnected Component ---- ### 連通性 - 討論**無向圖**上的連通性 - 邊雙連通：在一張連通無向途中，若點$u$和點$v$無法透過刪除任何一條邊，使他們不連通，則稱$u$和$v$點雙連通 - 點雙連通：在一張連通無向途中，若點$u$和點$v$無法透過刪除任何一個點，使他們不連通，則稱$u$和$v$點雙連通 ---- ### 邊雙連通 - 傳遞性：若$x$和$y$邊雙連通，$y$和$z$邊雙連通，則$x$和$z$邊雙連通 - 判斷一張圖是否邊雙連通：移除每條邊$e$，檢查是否整張圖還連通。 ---- ### 橋 - bridge / cut edge - 割邊 - 定義：若移除邊$e$會使得圖不連通，則稱$e$為橋 ---- ### Problem - 給定一張圖$G$，請找出圖中的所有橋(Bridge)  ---- ### Tarjan - 不少他發明的算法都以他的名字命名，以至於有時會讓人混淆幾種不同的算法。 --wiki  ---- ### DFS Tree - Back Edge: 一定不是橋 - Tree Edge: 有可能是橋 - 刪除後要透過back edge連通 - 邊$(u,v)$往上連到祖先 - $v$有back edge - $v$的子孫有back edge且高度只少連到$u$ ---- ### Low Function - $\text{low}(v):=$對於無向圖上的節點 $v$，$\text{low}(v)$被定義為「在不透過父邊的情況下，能夠到達深度最淺的祖先的深度」 ----  ---- | | a | b | c | d | e | f | g | h | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | dep | 0 | 1 | 2 | 3 | 4 | 2 | 3 | 2 | | low | 0 | 0 | 1 | 1 | 2 | 2 | 3 | 0 | ---- - $\text{low}(v) = \text{dep}(v)\rightarrow v$的父邊是橋 - 無法不透過父邊到達更淺的祖先 ---- ### Find $\text{low}$ - DFS 時從 $v$ 透過邊 $e$ 走到 $u$： - $u$還沒拜訪過： - $e$是樹邊，有機會從 $u$ 或他的小孩經過回邊走到更淺的祖先 - 對 $u$ 做DFS後，將 $\text{low}(v)$ 和 $\text{low}(u)$ 取 $\min$ - $u$拜訪過： - $e$是回邊，根據定義可以更新$\text{low}(v)$ - 將 $\text{low}(v)$ 和 $\text{dep}(u)$ 取 $\min$ ---- ### Time Complexity - DFS: $\mathcal{O}(V + E)$ ---- ```c= const int N = 100010 ; vector<int> g[N]; bool vis[N], bridge[N] ; int low[N], dep[N] ; void dfs(int x) { vis[x] = true ; low[x] = dep[x] ; for(auto i:g[x]) { if(vis[i]) { low[x] = min(low[x], dep[i]) ; } else { dep[i] = dep[x] + 1 ; dfs(i) ; low[x] = min(low[x], low[i]) ; } } if(low[x] == dep[x]) bridge[x] = true ; } ``` ---- ### 邊雙連通分量 - Bridge-connected Components - BCC - 定義：圖上「邊雙連通」的連通子圖，通常指極大的連通子圖 ----  ---- - 在尋找 bridge 的過程中順便找 BCC - 如果$u$的父邊是橋，則$u$往下形成一個BCC - 利用 stack 紀錄 ---- - 拜訪一個新的點時，將該點塞入stack - 若發現 $u$ 父邊是橋，將 stack 裡的東西取出直到 $u$ 也被取出 - 這些被取出的點形成 BCC ---- ### Time Complexity - DFS: $\mathcal{O}(V+E)$ ---- ```c= const int N = 100010 ; vector<int> g[N]; bool vis[N], bridge[N] ; int low[N], dep[N], bcc[N], bccID ; stack<int> stk ; void dfs(int x) { vis[x] = true ; low[x] = dep[x] ; stk.push(x) ; for(auto i:g[x]) { if(vis[i]) { low[x] = min(low[x], dep[i]) ; } else { dep[i] = dep[x] + 1 ; dfs(i) ; low[x] = min(low[x], low[i]) ; } } if(low[x] == dep[x]) { bridge[x] = true ; ++bccID ; int k ; do { k = stk.top() ; bcc[k] = bccID ; stk.pop() ; } while(k != x) ; } } ``` ---- ### Properties - 邊連通分量內： - 任兩點至少有兩條路相通，且這兩條路沒有共用邊 - Robbin定理：存在一種將邊定向的方式，使得任兩點可以互相抵達(形成SCC) ---- ### 縮點 - 若將每個 BCC 視為一個點，新的圖將形成一棵樹 ---- ### 點雙連通 - **沒有**傳遞性：若$x$和$y$點雙連通，$y$和$z$點雙連通，無法保證$x$和$z$點雙連通 - 判斷一張圖是否點雙連通：移除每個點$v$，檢查是否整張圖還連通。 ---- ### 割點 - cut vertex / articulation vertex(point) / AP - 關節點 - 定義：若圖 $G$ 在點 $v$ 移除後會變得不連通，則稱 $v$ 為割點 ---- ### Problem - 給定一張圖 $G$，請找出圖中所有的割點  ---- ### Low Function - 觀察點 $v$ 及其小孩 $u$ - 若 $u$ 無法不透過 $v$ 到達祖先時，則 $v$ 是 AP - $\text{low}(u) \geq \text{dep}(v)\rightarrow v$ 是AP ---- ### Root - 根節點是AP若且唯若他有兩條樹邊 - 每條樹邊下的子樹各自獨立 ---- ### Time Complexity - DFS: $\mathcal{O}(V+E)$ ---- ### 點雙連通分量 - stack 紀錄 - 若 $v$ 是AP，則下方形成一個BCC - 點雙連通分量有交集： - AP 要放回 stack - 改成紀錄邊 (沒有交集) ---- ### 圓方樹 - 圓點：割點 - 方點：點雙連通分量  ---- ### 重邊 - 只有一條邊是父邊(樹邊)，剩下的視為回邊 - 額外判斷往父親走了幾次 --- ## Strongly Connected Components ---- ### 連通性 - 討論**有向圖**上的連通性 - 弱連通(weakly connected)：將有向邊轉成無向邊後圖連通 - 強連通(strongly connected)：對於任兩個點 $v$ 和 $u$，都存在一條從 $v$ 走到 $u$ 的路徑及從 $u$ 走到 $v$ 的路徑 ---- ### 強連通分量 - Strongly Connected Components / SCC - 定義：圖上「強連通」的連通子圖，通常指極大的連通子圖 ----  ---- ### Tarjan? - 討論四種DFS Tree上的邊 - 透過DFS一次解決 - 實作複雜 ---- ### 縮點 - SCC 縮點後將形成 DAG  ---- - 若以拓樸排序的反序 DFS 取下每個點，每次 DFS 恰好都會取得一個SCC - 希望可以找到一個好的順序，類似拓樸排序的反序，得以產生同樣的效果 ---- - 討論兩個點 $x$ 和 $y$ - 若 $x$ 能到達 $y$，但 $y$ 無法到達 $x$，則 $x$ 和 $y$ 在不同SCC - 希望 $y$ 比 $x$ 早 DFS ---- ### Kosaraju - 建立反圖 $G'$，在 $G'$ 上 DFS 並記錄每個點離開的時間 - 依照離開時間大到小的順序在原圖 G 上 DFS 即可正確找出 SCC ---- ### Proof - 對於點對 $x$ 和 $y$，若 $x$ 能到達 $y$，但 $y$ 無法到達 $x$ - 考慮在反向圖 $G'$ 上 DFS 到 $y$ 時的狀況 - $x$已經拜訪過了：$x$已經離開，$x$ 時間小於 $y$ - $x$尚未拜訪過：$y$ 將會 DFS 到 $x$，且 $y$ 至少要等 $x$ 離開後才能離開，$x$ 時間小於 $y$ ----  ---- ### Time Complexity - 兩次 DFS - $\mathcal{O}(V+E)$ ---- ```c= const int N = 100010 ; vector<int> g[N], rg[N], ord; int scc[N], sccID ; bool vis[N] ; void dfsRev(int x) { vis[x] = true ; for(auto i:rg[x]) if(!vis[i]) dfsRev(i) ; ord.push_back(x) ; } void dfs(int x) { vis[x] = true ; scc[x] = sccID ; for(auto i:g[x]) if(!vis[i]) dfs(i) ; } void kosaraju(int n) { for(int i=1; i<=n; ++i) if(!vis[i]) dfsRev(i) ; reverse(ord.begin(), ord.end()) ; fill(vis, vis+N, 0) ; for(auto i:ord) if(!vis[i]) { ++sccID ; dfs(i) ; } } ``` --- ## 2-SAT ---- ### 2-Satifiability - 有 $N$ 個布林變數(Boolean variables)：$x_1,x_2,\dots,x_N$ - 運算式：$(x_1 \vee x_2) \wedge (\neg x_1 \vee x_3) \wedge (\neg x_2 \vee \neg x_5) \wedge \dots$ - 找到一組 $x_1,x_2,\dots,x_N$ 使得運算式為真 ---- ### 老媽與偏食小孩 - 有一個媽媽要他的小孩吃各種蔬菜，可是小孩不肯，於是他們在討價還價後定出了以下的條件 - 青椒、菠菜至少選一個 - 青椒、番茄至少選一個 - 番茄、苦瓜至少選一個 - 不吃苦瓜、不吃青椒至少選一個 - 請問要選擇那些菜色才能符合兩人開出的條件？ ---- - 青椒($x_1$)、菠菜($x_2$)、番茄($x_3$)、苦瓜($x_4$) - 青椒、菠菜至少選一個 $(x_1 \vee x_2)$ - 青椒、番茄至少選一個 $(x_1 \vee x_3)$ - 番茄、苦瓜至少選一個 $(x_3 \vee x_4)$ - 不吃苦瓜、不吃青椒至少選一個 $(\neg x_4 \vee \neg x_1)$ - $(x_1 \vee x_2) \wedge (x_1 \vee x_3) \wedge (x_3 \vee x_4) \wedge (\neg x_4 \vee \neg x_1)$ ---- ### 建立模型 - 每個變數只有兩種狀態 $x = True \vee False$ - 將每個變數拆成兩種個討論 - True: $x$ - False: $\neg x$ ---- - $(a \vee b)$ - $\neg a \longrightarrow b$ - $\neg b \longrightarrow a$ - $(\neg a \vee b)$ - $a \longrightarrow b$ - $\neg b \longrightarrow \neg a$ ---- - $N$ 個變數形成 $2N$ 個點 - $M$ 個條件形成 $2M$ 條有向邊 - 有向圖 ---- ### 判斷是否有解 - $a \rightarrow \neg b$：若 $a$ 為真，則 $b$ 必定為假 - $x \rightarrow \neg x$：若 $x$ 為真，則 $x$ 必定為假 $\Rightarrow$ $x$ 不能為真 - $\neg x \rightarrow x$：若 $x$ 為假，則 $x$ 必定為真 $\Rightarrow$ $x$ 不能為假 ---- - $x$ 無解的條件：當 $x \rightarrow \neg x$ 和 $\neg x \rightarrow x$ 同時存在 - $\implies$ 當 $x$ 能走到 $\neg x$ 且 $\neg x$ 能走到 $x$，$x$ 無解 - $\implies$ $x$ 和 $\neg x$ 在同一個 SCC 內 ---- ### Solution - 對於變數個數建點 - 對於每個條件建立有向邊 - 在圖上做 SCC - 檢查每個變數是否矛盾 ---- ### Time Complexity - $N$ 個變數，$M$ 個條件 - 建點：$\mathcal{O}(N)$ - 建邊：$\mathcal{O}(M)$ - SCC：$\mathcal{O}(N+M)$ - 檢查：$\mathcal{O}(N)$ - Total：$\mathcal{O}(N+M)$ ---- ### 找到一組解 - 同一個 SCC 內的點必定全選或全不選 - 在縮圖上以拓樸排序反向設定解 - $x$ 在 $\neg x$ 前面：$x \rightarrow \neg x$，$x$ 為假 - $\neg x$ 在 $x$ 前面：$\neg x \rightarrow x$，$x$ 為真 ---- ### XOR - $a \oplus b$ - $(a \vee \neg b) \wedge (\neg a \vee b)$ - 四個有向邊 ---- ### K-SAT - $(a \vee b \vee c \vee\dots \vee n) \wedge (\dots$ - 一個條件裡面最多有 $k$ 個元素取 OR - ex. 1-SAT：$\neg x_1 \wedge x_2 \wedge \neg x_3 \wedge\dots \wedge x_N$ ---- ### 3-SAT - 所有 NP-complete 皆能轉換為 3-SAT 問題 - 目前沒有好的解法 --- ## Maximum Bipartite Matching ---- ### 匹配 - Matching - 一張無向圖中相鄰兩點配成一對，且每個點最多只能與一個人配對 - 在圖中挑出一些邊，使得這些邊各自獨立 ----  ---- ### 二分圖最大匹配 - 討論一張二分圖上的匹配問題 - 通常要找到最大的匹配數量 - Ex. 交友網站上男女各自找有興趣的異性，當兩人對彼此都有興趣則形成一條邊，請找出可能的最大成功配對數量。 ----  ---- ### 網路流 - 源點接上左邊所有點，且容量為 $1$ - 匯點接上右邊所有點，且容量為 $1$ - 最大匹配 = 最大流 - Dinic's 算法：$\mathcal{O}(\sqrt V E)$ ---- ### 交錯路徑 - alternating path - 匹配邊與未匹配邊彼此相間的路徑 - $(x_1,[y_1,x_2],[y_2,x_3],\dots,[y_{n-1},x_n],[y_n,x_{n+1}])$ - 只有首點或末點未匹配 - 顛倒交錯路徑上的匹配邊與未匹配邊不影響匹配數量 ---- ### 增廣路徑 - augmenting path - 首點和末點皆未匹配 - $(x_1,[y_1,x_2],[y_2,x_3],\dots,[y_{n-1},x_n],y_n)$ - 顛倒增廣路徑上的匹配邊與未匹配邊會使匹配數量$+1$ ---- ### Berge's Lemma - 一組匹配 $M$ 為圖 $G$ 中的最大匹配若且唯若圖上不存在對於 $M$ 來說的增廣路徑 - 在圖上不斷的找增廣路徑，如果成功找到就翻轉他，直到找不到為止 ---- ### Augmenting Path Algorithm - 二分圖中左邊的點集 $X$，右邊的點集 $X$ - 對於每個左邊的點 $x \in X$： - 從 $x$ 開始 DFS，若鄰居 $y$ 未被匹配，則找到了路竟$(x,y)$，將 $y$ 與 $x$ 匹配 - 若鄰居 $y$ 已經匹配，考慮他的匹配點 $z\ (z \in X)$，如果 $z$ 有增廣路徑的話，把 $(x,y)$ 接過去還是一條增廣路徑，遞迴 $z$。 ---- ### Time Complexity - 對於左邊每個點，最多會 DFS 整張圖一次 - $\mathcal{O}(V) \times \mathcal{O}(E) = \mathcal{O}(VE)$ ---- ```c= const int N = 1010 ; vector<int> g[N]; int py[N] ; bool vis[N] ; bool dfs(int x) { for(auto i:g[x]) if(!vis[i]) { vis[i] = true ; if(!py[i] || dfs(py[i])) { py[i] = x ; return true ; } } return false ; } int APA(int n) { int ret = 0 ; for(int i=1; i<=n; ++i) { fill(vis, vis+N, 0) ; if(dfs(i)) ++ret ; } } ``` ---- ### 二分圖最大權匹配 - 匈牙利算法（KM算法） - 本質上也是利用 增廣路徑算法 - 在點上加權重 $l[x], l[y]$ 使得 $l[x] + l[y] \geq w(x,y)$ - 逐漸降低權重使得 $l[x] + l[y] = w(x,y)$ - 一般：$\mathcal{O}(V^2E)$、優化：$\mathcal{O}(VE)$ - Tutorial: https://blog.csdn.net/sixdaycoder/article/details/47720471 ---- 一般 ```c= struct KM { int n ; vec<vec<pii>> g ; vec<int> lx, ly, vx, vy, p; KM (int _n) { n = _n ; g.rs(n + 1) ; p.rs(n + 1) ; lx.rs(n + 1) ; ly.rs(n + 1) ; vx.rs(n + 1) ; vy.rs(n + 1) ; } void addEdge(int a, int b, int c) { g[a].EB(b, c); } bool dfs(int x) { vx[x] = true; for(auto [i, u]:g[x]) if(!vy[i] && lx[x] + ly[i] == u) { vy[i] = true; if(!p[i] || dfs(p[i])) { p[i] = x ; return true; } } return false ; } int exe () { rep1(i, n) for(auto j:g[i]) amax(lx[i], j.S); rep1(i, n) { while(true) { fill(ALL(vx), 0); fill(ALL(vy), 0); if(dfs(i)) break; int d = INF; rep1(i, n) if(vx[i]) for(auto [j, u]:g[i]) if(!vy[j]) amin(d, lx[i] + ly[j] - u) ; rep1(i, n) { if(vx[i]) lx[i] -= d ; if(vy[i]) ly[i] += d ; } } } int ret = 0; rep1(i, n) ret += lx[i] + ly[i] ; return ret ; } }; ``` ---- 優化 ```c= struct KM { int n; vec<vec<int>> g; vec<int> lx, ly, slk, vis, pre, mat; KM (int _n) { n = _n ; g.assign(n+1, vec<int>(n+1, -INF)); lx.rs(n+1); ly.rs(n+1); vis.rs(n+1); mat.rs(n+1); slk.rs(n+1); pre.rs(n+1); } void addEdge(int a, int b, int c) { g[a][b] = c; } void bfs(int x) { int px, py = 0, ny = 0, d; rep(i, n+1) vis[i] = pre[i] = 0, slk[i] = INF; mat[py] = x; do { px = mat[py], vis[py] = true, d = INF; rep1(i, n) if(!vis[i]) { if(slk[i] > lx[px] + ly[i] - g[px][i]) slk[i] = lx[px] + ly[i] - g[px][i], pre[i] = py; if(d > slk[i]) d = slk[i], ny = i; } rep(i, n+1) if(vis[i]) lx[mat[i]] -= d, ly[i] += d; else slk[i] -= d; py = ny; } while(mat[py]); while(py) mat[py] = mat[pre[py]], py = pre[py]; } ll match() { rep1(i, n) bfs(i); ll ret = 0; rep1(i, n) ret += lx[i] + ly[i]; return ret; } }; ``` ---- ### 一般圖最大匹配 - 增廣路徑可能形成環，稱為**花**(blossom) - 進行**縮花**(contract)的動作 - 我也不會QWQ --- ## Credit - Wikipedia - OI Wiki - 演算法筆記 - IONC - 日月掛長 - https://mathworld.wolfram.com/PerfectMatching.html - https://medium.com/swlh/on-the-importance-of-knowing-names-and-maximum-cardinality-matching-in-bipartite-graphs-180ef7f48b7e