Week 11

Question

Click to Open Question

Check

• Q1
• Q2
• Q3
• Q4
• Q5
• Q6
• Q7

Answer

Q1

• xian

【題目】

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

• LXS

【題目】

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$

• 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

由此可得到五棵樹:

Q3

• 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\mathrm{\_}check(root{)}_{\mathrm{\#}}$

證明

如果這個圖是 semi-connected，對於任意的

$(v_1,v_2)$，都會有 path

$：v_1\to \cdots \to v_2$，假設

$U_1,U_2$ 是他們的SCCs，如果有 path 從

$U_1\mathrm{到}{U}_2$，那麼一定也會有 path 從

$v_1\mathrm{到}{v}_2$，因為

$U_1,U_2$ 裡的 node 都是 strongly-connected。

Q4

• 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
}

寫錯的版本

證明

$\text{Let (u,v) be an edge. We shall show }finish\mathrm{\_}time(v)<finish\mathrm{\_}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\mathrm{\_}time(u)<discovery\mathrm{\_}time(v)<finish\mathrm{\_}time(v)<finish\mathrm{\_}time(u)$

$\text{In Case 2, v must have finished before u starts. Otherwise the graph contains a cycle.}$

$\text{Thus, }finish\mathrm{\_}time(v)<discovery\mathrm{\_}time(u)\to finish\mathrm{\_}time(v)<finish\mathrm{\_}time(u)$

$\text{Both cases show }finish\mathrm{\_}time(v)<finish\mathrm{\_}time(u{)}_{\mathrm{\#}}$

$\text{Note: discovery\_time means the vertix enter stack}$

$\text{Note: finish\_time means the vertix pop out stack}$

Ref 清大資工演算法ppt

【Strongly Connected Components】
結論：可以，但也要修改。

在此說明常用的SCC解法：

假設從

$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

• songchiu

假設原本的圖形是這樣，紫色的邊構成

$MSTT$

接著將

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

$MST{T}^{\prime }$

假定

$(x,y)$是權重較小的邊 (

$weight(x,y)\le weight(u,v)$)
它能使圖形再次回到

$MST$(因為

$(x,y)$已經是當前最小)

Theorem 23.1

會得出這樣的結論，是依據Theorem 23.1
當把

$(u,v)$剪掉後，在它的crossing edge當中，可以找到一個最輕邊

$(x,y)$
這個最輕邊

$(x,y)$也會是MST裡的一條邊

用數學式來證就是：
因為

$weight(x,y)\le weight(u,v)$
所以

$weight(T^{\prime })\le weight(T)-weight(u,v)+weight(x,y)$

$weight(T^{\prime })\le weight(T)$

因此若

$T$是

$MST$，

$T^{\prime }$也會是

$MST$

Q6

• chung

【題目】

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

• yee

【題目】

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^{\prime }$
先從

$T$ 中隨機移除一條邊

$e$，產生兩個

$T$的子集

$S、V-S$
因為

$ecrosscut(S,V-S)$ ，由

$Q5$ 可知

$e$ 為

$cut(S,V-S)$中的唯一最輕邊
再假設

$x$ 為

$T^{\prime }$ 且穿過

$cut(S,V-S)$
由於穿過

$cut(S,V-S)$ 的最輕邊是唯一
即代表

$e$ 與

$x$ 為同一條邊，所以

$e$ 也屬於

$T^{\prime }$
又因

$e$ 為隨機選擇，代表所有於

$T$ 上的邊也於

$T^{\prime }$ 上
即可證明

$MST$ 是唯一

【Counterexample】
若一

$Graph$ 存在唯一

$MST$，

$cut(S,V-S)$ 中未必存在唯一最輕邊

由上圖可知，

$AB\mathrm{與}BC$ 皆為最輕邊