# Week 11

# Question
:::info
:::spoiler Click to Open Question

## 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

**【蘇都扣】**

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$

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
:::

## 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】

//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】

//承上
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裡的圖為例：
何老師的作法，DFS會求出：AFEGDCB
張老師的作法，DFS會求出：AGEDBCF

很明顯的，E不應該在F的前面，因此不適用
會發生這樣的狀況因為較後面被走訪的點，先被pop出來了

因此我們要將該DFS修改一下，加入stack的$u$點先不要pop出來，待它的子小孩都過且離開stack後，再將$u$點pop出來

當每個子小孩離開stack時，順便將它的離開時間紀下來。待全部完成後，把紀下來的時間倒過來，即為topo sort的時間

附上蘇都扣來參考一下：

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 寫錯的版本

**證明**
$\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解法：

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的關係了

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]

<!-- $\text{By Theorem 23.1, We remove (u,v) and draw a cut cross (u,v). }$
$\text{Now, our strategy is choose a light-weight edge,}$
$\text{because (u,v) is in this MST originally, then (u,v) is a light edge.}$ -->

假設原本的圖形是這樣，紫色的邊構成$MST \; T$

接著將$(u, v)$剪掉，此時是兩個分開的connected component
我們需要再找個權重較低的邊，把圖重新組回$MST \; T'$

假定$(x, y)$是權重較小的邊 ($weight(x,y) \leq weight(u,v)$)
它能使圖形再次回到$MST$(因為$(x, y)$已經是當前最小)

:::spoiler Theorem 23.1
:::

會得出這樣的結論，是依據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)$ 中未必存在唯一最輕邊
由上圖可知，$AB\ 與\ BC$ 皆為最輕邊