--- # System prepended metadata title: Week 11 --- # Week 11 # Question :::info :::spoiler Click to Open Question ![](https://i.imgur.com/iTv6rZ3.png) ![](https://i.imgur.com/dw9aicb.png) ![](https://i.imgur.com/YoD5hbL.png) ## Check - [ ] Q1 - [ ] Q2 - [ ] Q3 - [ ] Q4 - [ ] Q5 - [ ] Q6 - [ ] Q7 ::: # Answer ## Q1 > - [name=xian] :::spoiler **【題目】** A DFS forest can be generated by perform DFS on a directed graph. There are 4 types of edges in a DFS forest: `tree edge`, `forward edge`, `back edge` and `cross edge`. Modify DFS so that it can determine the type of each edge. ::: **【edge的定義】** * Tree Edge (GRAY to WHITE) * Edges in the DFS forest * Found when encountering a new vertex 𝑣 by exploring 𝑢, 𝑣 * Back Edge (GRAY to GRAY) * 𝑢, 𝑣 , from descendant 𝑢 to ancestor 𝑣 in a DFS tree * Forward Edge (GRAY to BLACK) * 𝑢, 𝑣 , from ancestor 𝑢 to descendant 𝑣. Not a tree edge. * Cross Edge (GRAY to BLACK) * Any other edge between trees or subtrees. Can go between vertices in same DFS tree or in different DFS trees. **【解題思路】** 利用塗色的方法解決問題，根據DFS Property我們可以將遇到不同顏色看做是edge的分類： * White(沒走過)： tree edge * Gray(走進去還沒出來)： back edge * Black(走出來了)：forward edge or cross edge * u.d < v.d $\Rightarrow$ forward edge * u.d > v.d $\Rightarrow$ cross edge 因此我們可以在DFS Algorithm中加入判斷式，獲得我們要的答案。 **【變數定義】** * $c[u]$：node u目前的顏色 * $d[u]$：node u第一次進入的時間 * $p[u]$：node u 第一次被探訪時的前一個node **【蘇都扣】** ```cpp= DFS(G) let v[] be the node of G and Adj[] be the Adjacency list of the G let all value in c[] be white //c[u]: node u 目前的顏色 time = 0 for u in V: if c[u] == white Visit(u) Visit(u) c[u] = gray d[u] = ++time for v in Adj[u]: if c[v] == white: p[v] = u Visit(v) (u,v) is a tree edge else if c[v] == gray: (u,v) is a back edge else //black if d[u] < d[v]: (u,v) is a forward edge else: (u,v) is a cross edge c[u] = black ``` ## Q2 > - [name=LXS] :::spoiler 【題目】 Show how the procedure STRONGLY-CONNECTED-COMPONENTS works on the graph of Figure 22.6. Specifically, show the finishing times computed in line 1 and the forest produced in line 3. Assume that the loop of lines 5-7 of DFS considers vertices in alphabetical order and that the adjacency lists are in alphabetical order. ::: * Strongly Connected Components ``` Strongly-Connected-Components(G) Call DFS(G) to computing f[u] for each u \in V. Compute GT. Call DFS(GT) but consider the vertices in order of decreasing f[u] computed in line 1. Output the vertices of each tree in the DFS forest formed in line 3 as a separate SCC. ``` * Call DFS(G) to computing f[u] for each $u \in V$. | Vertices | Discover d\[u\] | Finish f\[u\] | | -------- | --------------- | ------------- | | q | 1 | 16 | | r | 17 | 20 | | s | 2 | 7 | | t | 8 | 15 | | u | 18 | 19 | | v | 3 | 6 | | w | 4 | 5 | | x | 9 | 12 | | y | 13 | 14 | | z | 10 | 11 | * Graph of $G^T$ ```graphviz digraph { ordering=out; node [shape=circle] q -> y s -> w s -> q t -> q u -> r v -> s w -> q w -> v x -> t x -> z y -> t y -> u y -> r z -> x } ``` * Call $DFS(G^T)$ but consider the vertices in order of decreasing f[u] computed in line 1. * $\text{f[ ] in descending order.}$ | Vertices | Discover d\[u\] | Finish f\[u\] | | -------- | --------------- | ------------- | | r | 17 | 20 | | u | 18 | 19 | | q | 1 | 16 | | t | 8 | 15 | | y | 13 | 14 | | x | 9 | 12 | | z | 10 | 11 | | s | 2 | 7 | | v | 3 | 6 | | w | 4 | 5 | * $DFS(G^T)$ | Vertices | Discover d\[u\] | Finish f\[u\] | | -------- | --------------- | ------------- | | r | 1 | 2 | | u | 3 | 4 | | q | 5 | 10 | | t | 7 | 8 | | y | 6 | 9 | | x | 11 | 14 | | z | 12 | 13 | | s | 15 | 20 | | v | 17 | 18 | | w | 16 | 19 | 由此可得到五棵樹: :::spoiler ![](https://i.imgur.com/ZdYomQy.png) ::: ## Q3 > - [name=Mark] > **前情提要** G = (V, E) is semi-connected => for all pairs of vertices u, v in V, we have u->v or v->u. **思路** 1. 先對`graph`做求有向圖的SCC的`Tarjan's Algorith`得出SCC，$O(V+E)$ 2. 把SCC接起來成新的`graph`(已變成DAG)->`gN` 3. 對`gN`做`DFS()`檢查是否為`semi-connected`，$O(V+E)$，查看是否為線性鏈 **蘇都扣** 【step 1,2】 ```cpp= //dfn[] 為vertex n的時間戳 //low[] 為n或n子樹能追溯到最早stack中的時間戳 //component[] 每個點對應到的SCC收縮成的點 let g[] be the Adjacency list of the G //adjacency list let all value in dfn[N], component[N], low[N] be zero create an empty Stack S int T = 0 //時間戳記 int C = 0 //SCC component個數 for u = 0 to g.size(): if(!dfn[u]) DFS(u) DFS(u){ dfn[u] = low[u] = ++T S.push(u) for v in g[u]: if(v is not visited): //尚未被訪問到 DFS(v) low[u] = min(low[u], low[v]) else if(v is in S): low[u] = min(low[u], dfn[v]) if(dfn[u] == low[u]): C++ do{ t = S.pop() component[t] = C }while(t != u); } ``` 【step 3】 ```cpp= //承上 visit = [] //紀錄是否走過 answer = false flag = false DFS_check(index){ if(flag): return answer visit[index] = true for i in g[index]: if(visit[i]) continue; else if(!visit[i] && component[i] == component[index]): DFS_check(i) else if(!visit[i] && component[i] == component[index] + 1): DFS_check(i) else: flag = true answer = false if(!flag and C == component[index]): flag = true answer = true else: flag = true answer = false } ``` ans: $DSF\_check(root)_\#$ **證明** 如果這個圖是 semi-connected，對於任意的$(v_1,v_2)$，都會有 path $：v_1\rightarrow \cdots \rightarrow v_2$，假設 $U_1,U_2$ 是他們的SCCs，如果有 path 從 $U_1\ 到\ U_2$，那麼一定也會有 path 從 $v_1\ 到\ v_2$，因為 $U_1,U_2$ 裡的 node 都是 strongly-connected。 ## Q4 > - [name=songchiu] 題意：張貴雲教授教的「用stack解DFS」可否拿來處理Topo Sorting、Strongly-Connected-Component **【Topological Sorting】** 結論：**可以，但要修改**。 原本是沒辦法的，因為順序會有差，以ppt裡的圖為例： ![](https://i.imgur.com/fUWycpP.jpg =150x150) 何老師的作法，DFS會求出：AFEGDCB 張老師的作法，DFS會求出：AGEDBCF 很明顯的，E不應該在F的前面，因此不適用 會發生這樣的狀況因為較後面被走訪的點，先被pop出來了 因此我們要將該DFS修改一下，加入stack的$u$點先不要pop出來，待它的子小孩都過且離開stack後，再將$u$點pop出來 當每個子小孩離開stack時，順便將它的離開時間紀下來。待全部完成後，把紀下來的時間倒過來，即為topo sort的時間 附上蘇都扣來參考一下： ```cpp= TopoSort(){ Time[], time_counter = 0//初始化時間 for u in G if stack is empty and u not reached mark u as reached, push into stack while stack is not empty //Traverse the tree has_child = 0 for v in Adj[vertex at top of stack] if v not reached mark v as reached, push into stack has_child = 1 if has_child = 0 Time[vertex at top of stack] = ++time_counter pop stack } ``` :::spoiler 寫錯的版本 ![](https://i.imgur.com/Mo7wE8F.png) **證明** $\text{Let (u,v) be an edge. We shall show } finish\_time(v) < finish\_time(u) \text{ so that the ordering is correct}$ $\text{In DFS, there are two cases.}$ $\text{Case1: u is visited before v}$ $\text{Case2: v is visited before u}$ $\text{In Case 1, u cannot finish before DFS is performed on all its neighbors.}$ $\text{Since v is a neighbor of u , we must have }$ $discovery\_time(u) < discovery\_time(v) < finish\_time(v) < finish\_time(u)$ $\text{In Case 2, v must have finished before u starts. Otherwise the graph contains a cycle.}$ $\text{Thus, } finish\_time(v) < discovery\_time(u) \rightarrow finish\_time(v) < finish\_time(u)$ $\text{Both cases show }finish\_time(v) < finish\_time(u)_\#$ $\text{Note: discovery_time means the vertix enter stack}$ $\text{Note: finish_time means the vertix pop out stack}$ [Ref 清大資工演算法ppt](http://www.cs.nthu.edu.tw/~wkhon/ds/ds11/lecture/lecture12.pdf) ::: **【Strongly Connected Components】** 結論：**可以，但也要修改**。 在此說明常用的SCC解法： ```graphviz digraph { ordering=out; node [shape=circle] a -> b b -> c c -> a } ``` 假設從$A$開始找，$A$的時間為1；接著向下找，依序找到$B$、$C$； 接著$C$就會走回$A$，但發現$A$走過了，就會將$A=1$的時間傳給$C$，接著再依序往上傳給$B$ (利用遞迴式回傳值的方式) 因此我們在一張圖中，看到有幾種不同的時間，就是有幾個$SCC$ 但是第二種解法，它用stack來處理 假設有一點$u$，在準備被走訪前，先被丟到stack 走訪時被從stack取出，走訪後就沒辦法再回頭改它的值了 由於我們沒辦法回頭更新$u$，因此這個方法不適合拿來解$SCC$ 但還是有辦法解的，只要稍微修改一下就行了 跟剛剛的很像，但多拿一個stack $S$來紀錄一下當時走訪過哪些點 之後再透過一個vector $SCC$ 來存放，擁有相同counter值的，會被放到同個vector元素裡 這樣就可以找出它們是不是SCC的關係了 ```cpp= findSCC(){ counter = 0//初始化SCC個數 for u in G //run 1st DFS if stack is empty and u not reached mark u as reached, push into stack while stack is not empty Traverse the tree and store each vertex by exit time into S while S is not empty //run 2nd DFS u = S's top if stack is empty and u not reached mark u as reached, push into stack counter++ while stack is not empty SCC[counter].push_back(vertex at top of stack) for v in Adj[vertex at top of stack] if v not reached mark v as reached, push into stack return SCC } ``` ## Q5 > - [name=songchiu] 假設原本的圖形是這樣，紫色的邊構成$MST \; T$ ![](https://i.imgur.com/l8jczis.jpg =250x150) 接著將$(u, v)$剪掉，此時是兩個分開的connected component 我們需要再找個權重較低的邊，把圖重新組回$MST \; T'$ ![](https://i.imgur.com/5Skp03M.jpg =250x150) 假定$(x, y)$是權重較小的邊 ($weight(x,y) \leq weight(u,v)$) 它能使圖形再次回到$MST$(因為$(x, y)$已經是當前最小) ![](https://i.imgur.com/OYAo5V9.jpg =250x150) :::spoiler Theorem 23.1 ![](https://i.imgur.com/yZAdTjy.jpg) ::: 會得出這樣的結論，是依據Theorem 23.1 當把$(u, v)$剪掉後，在它的crossing edge當中，可以找到一個最輕邊$(x, y)$ 這個最輕邊$(x, y)$也會是MST裡的一條邊 用數學式來證就是： 因為 $weight(x,y) \leq weight(u,v)$ 所以 $weight(T') \leq weight(T)−weight(u,v)+weight(x,y)$ $weight(T') \leq weight(T)$ 因此若$T$是$MST$，$T'$也會是$MST$ ## Q6 > - [name=chung] :::spoiler **【題目】** Let e be a maximum-weight edge on some cycle of connected graph G = (V, E). Prove that there is a minimum spanning tree of G’ = (V, E – {e}) that is also a minimum spanning tree tree of G. That is, there is a minimum spanning tree of G that does not include e. ::: **【Proof】** 利用反證法，假設 T 是一顆隨意的生成樹，不包含上述被剪掉的最大weight的邊 e・由於樹的特性，可以得知點之間一定有路徑互相連接，假設這條路徑為P，P 一定會穿過 S 與 V − S 兩個子集，假設連接兩個 set 的邊為 e'，e' 連接的兩個點分別為 V' 與 W'・將 e' 替換成 e，生成新的樹 T'，由於 e > e'，因此 T' 的權重勢必會比較大，而 T' 的每個點也都會有路徑相連，同時 T' 是以 e' 替換 e 形成，並沒有引進新的邊，因此也不會出現 cycle，故得證 T' 的權重大於 T，T'不是最小生成樹，故最小生成樹不會包含e。 ## Q7 > - [name=yee] :::spoiler **【題目】** Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. Show that the converse is not true by giving a counterexample. ::: **【解題思路】** 透過反證法，先假設有兩棵$MST$，分別為 $T、T'$ 先從 $T$ 中隨機移除一條邊 $e$，產生兩個$T$的子集 $S、V-S$ 因為$e\ cross\ cut(S,V-S)$ ，由 $Q5$ 可知 $e$ 為 $cut(S,V-S)$中的唯一最輕邊 再假設 $x$ 為 $T'$ 且穿過 $cut(S,V-S)$ 由於穿過 $cut(S,V-S)$ 的最輕邊是唯一 即代表 $e$ 與 $x$ 為同一條邊，所以 $e$ 也屬於 $T'$ 又因 $e$ 為隨機選擇，代表所有於 $T$ 上的邊也於 $T'$ 上 即可證明 $MST$ 是唯一 **【Counterexample】** 若一 $Graph$ 存在唯一 $MST$，$cut(S,V-S)$ 中未必存在唯一最輕邊 ![](https://i.imgur.com/YwSnnYn.png) 由上圖可知，$AB\ 與\ BC$ 皆為最輕邊