Week 10

Click to Open TOC

• Week 10
• Question
• Answer
  • Q1
  • Q2
    • 【adjacency-list】
    • 【adjacency-matrix】
  • Q3
  • Q4
  • Q5
  • Q6
  • Q7

Question

Click to Open Question

Check

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

Answer

Q1

• chung

【題目】

Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees

【out-degree】

要在有向圖的adjacency-list計算out-degree，從vertex的adjacency-list中遍歷所有相鄰邊(E)，即便圖沒有邊仍然需要判斷vertex(V)，因此所需時間為

$O(|V|+|E|)$

【in-degree】

要計算in-degree，必須遍歷每個頂點(V)，走完所有的點及邊即可確認所有的in-degree，因此所需時間為

$O(|V|+|E|)$

Q2

• xian

【題目】

The transpose of a directed graph

$G=(V,E)$ is the graph

$G^T=(V,E^T)$, where

$E^T=(v,u)\in V\text{X}V:(u,v)\in E$. Thus,

$G^T$ is

$G$ with all its edges reversed. Describe efficient algorithms for computing

$G^T$ from

$G$, for both the adjacency-list and adjacency-matrix representations of

$G$. Analyze the running times of your algorithms.

【example】

【adjacency-list】

由下圖可知，只要

$G$的 Adjacency-List 遍歷一次，即可找到

$G^T$的 Adjacency-List ，每經過任何一個節點的List時，即在

$G^T$的List加上相對的節點。

• 當經過a點的b時，即在對面b節點加上a點，以此類推，即可計算出
  $G^T$的Adjacency-List
• 時間複雜度：即為遍歷一次所有點和edge
  $\Rightarrow O(|V|+|E|{)}_{\mathrm{\#}}$
  

【蘇都扣】

let G[],T[] be the Linked_list of G,G_T

for i=1 to G.size():
    node = g[i]->next
    while(node):
        link g[i] to the end of T[node] 
        node = node->next
        
return T

【adjacency-matrix】

由下圖可知，我們只需將Adjacency-Matrix轉置，即可計算出

$G^T$的Adjacency-Matrix

• 時間複雜度：執行兩個for迴圈即可算出答案
  $\Rightarrow O(|V{|}^2{)}_{\mathrm{\#}}$

$G:\left[\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 0& 1\\ 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}\right]\Rightarrow G^T:\left[\begin{array}{ccccc}0& 1& 1& 0& 0\\ 1& 0& 0& 0& 0\\ 0& 1& 0& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 1& 0& 0& 0\end{array}\right]$

【蘇都扣】

let G[][],T[][] be the matrix of G,G_T

for i=1 to |V|:
    for j = 1 to |V|:
        T[j][i] = G[i][j]
        
return T

Q3

• LXS

題目

The square of a directed graph

$G=(V,E)$ is the graph

$G^2=(V,E^2)$ such that

$(u,v)\in E^2$ if and only if

$G$ contains a path with at most two edges between

$u$ and

$v$. Describe efficient algorithms for computing

$G^2$ from

$G$ for both the adjacency-list and adjacency-matrix epresentations of

$G$. Analyze the running times of your algorithms.

【Adjacency-matrix】

$G:$ The Adjency matrix of the graph

$G[m,n]\text{代表}m\to n$

$$\begin{gathered} (G\times G)[m,n]=(m\to 1\times 1\to n)+...+(m\to k\times k\to n) \\ =(m\to 1\wedge 1\to n)\vee ...\vee (m\to k\wedge k\to n) \end{gathered}$$
這樣沒算到

$m\to n$因為沒有self-loop時，

$m\to m$是

$0$，

$m\to m\wedge m\to n=0\times 1=0$，

$m\to n\wedge n\to n$同理
因此再加上

$G$，即

$G^2=G\times G+G$，加法時間複雜度最高為

$O(|V{|}^2)$，整體的時間複雜度為矩陣乘法的時間複雜度，Strassen為例，時間複雜度為

$O(|V{|}^{lg7})\approx O(|V{|}^{2.807})$

【Adjacency-list】

對途中每一個Edge做遍歷，透過

$G^T$找到可以通向那個Edge的Edge起點，再將那個點加入

$G^2$中

【Psuedocode】

def Square1():
    # G:  The Adjency list of the graph
    # Gt: Transpose of G
    # Gs: G Square

    for v in G:
        for u in v: # v->u
            Gs[v].append(u) # One edge
            for w in Gt[v]: # x->v
                Gs[w].append(u)

G Transpose 可以在

$O(|V|+|E|)\mathrm{時}\mathrm{間}\mathrm{達}\mathrm{成}$，因此時間複雜度為

$O(|E||V|+|V|)$

Q4

• Mark

題目

There are two types of professional wrestlers: “babyfaces” (“good guys”) and
“heels” (“bad guys”). Between any pair of professional wrestlers, there may or may
not be a rivalry. Suppose we have n professional wrestlers and we have a list of r
pairs of wrestlers for which there are rivalries. Give an O(n + r)-time algorithm that
determines whether it is possible to designate some of the wrestlers as babyfaces
and the remainder as heels such that each rivalry is between a babyface and a heel.
If is it possible to perform such a designation, your algorithm should produce it.

思路
類比塗色問題，相鄰兩個點須為不同顏色 => 比賽的對戰組合類型永遠都是heel v.s. babyface，不同type互打

步驟
令graph中的每個vertex有visited、type等屬性，對graph做BFS()，以edge作為對戰組合，若尚未經過(visited is false)的就令他為與來源vertex相反的type，若已經過則觀察相鄰的vertex是否為不同類型，可以的話就繼續搜尋直到結束，否則return false。
若BFS()是True的情況，跑一個loop將所有vertex分配到對應babyface、heel的array，並回傳

蘇都扣

def BFS():
    # q: queue
    # f: the vertex we put into q
    # vertex[]: 用來存input進來的所有vertex    
    # rivals[]: vertex的鄰居，這裡代表是對手，是屬於vertex[i]的陣列
    f = vertex[0]
    q.put(f) 
    while(q)
        u = q.pop()
        if u have not been visited:
                set u is visited
                u.type = "Babyface"
        for i in range(0, length of u.rivals)
            v = u.rivials[i]
            if v have not been visited:
                set v is visited
                if u.type == "Babyface":
                    v.type = "Heel"
                elif u.type == "Heel":
                     v.type = "Babyface"
                q.put(v)

            elif v have been visited:
                if v.type == "Babyface":
                    if u.type != "Heel":
                        return False
                elif v.type == "Heel":
                    if u.type != "Babyface":
                        return False
            if q is empty
                for vertex in vertex[]:
                    leftover = vertex
                    if leftover have not been visited:
                        q.put(leftover)
                        break
                
    return True
# babyfaces[]: 用來存type是babyface的vertex
# heels[]: 同上意義
def foo():
    if BFS():
        for vertex in vertex[]:
            if vertex.type == "Babyface":
                babyfaces.append(v.name)
            else:
                heels.append(v.name)
        return babyfaces, heels
    else:
        print("Cannot find the designaction")
        return False

範例

6
Bear
Maxxx
Killer
Knight
Duke
Samson
5
Bear Samson
Killer Bear
Samson Duke
Killer Duke
Maxxx Knight

// Sample Solution
Yes Possible
Babyfaces: Bear Maxx Duke
Heels: Killer Knight Samson

Time Complexity

$O(n+r)$

Q5

• songchiu

題目

Give a linear-time algorithm that takes as input a directed acyclic graph G = (V, E) and two vertices s and t, and returns the number of simple paths from s to t in G.
For example, the directed acyclic graph of Figure 22.8 contains exactly four simple paths from vertex p to vertex v: pov, poryv, posryv, and psryv. (Your algorithm needs only to count the simple paths, not list them.)

【解題思路】
用DFS來解，但稍微改良一下，讓它可以計算到底有幾條路徑符合
並且讓每個點多一個欄位，計算它的子節點總共有幾個路徑

【遞迴式】

$DFS(s,t)=s.sum=\{\begin{array}{l}1,\text{if s=t}\\ 0,\text{if s have non visited point and s has no child}\\ sum(DFS(c,t))c\in s^{\prime }schild,\text{if s have non visited point and s has child}\\ s.sum,\text{otherwise}\end{array}$

【蘇都扣】

int DFS(s,t) {
    if s = t
        return 1
    if s have non visited point
        if s has no child
            return 0
        s.sum = sum (DFS(c,t) for c in s's child)
    mark point s as visited
    return s.sum
}

【時間複雜度】
每個點只會被走一遍，時間複雜度為

$O(|V|+|E|)$

Q6

• yee

【題目】

Give an algorithm that determines whether or not a given undirected graph G = (V,E) contains a cycle. Your algorithm should run in O(V) time, independent of |E|.

【解題思路】
當一個undirected graph跑DFS未產生back edges，表示其為acyclic。
因此只要做DFS時，產生一個back edge就代表存在cycle。

【蘇都扣】

for u in G
    let u.visited = false 
DFS(G,u){
    u.visited = true
    for v in G.Adj[u]  //v表示所有與u相連的節點
        if v.visited == false
            DFS(G,v)
        else
            return true
    return false
}

【複雜度】
若有back edge，會在經過所有V前找到，若為acyclic，因

$|E|$<

$|V|-1$，也小於

$|V|$，因此時間複雜度為

$O(|V|)$

Q7

• yee

【題目】

Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains an euler circuit,and if the answer is positive your algorithm should output an euler circuit.

【解題思路】
當一個graph每個V的degree皆為大於等於二的偶數，表示該graph有euler circuit。
李永樂老師解說

離散數學的ppt截下來的

【蘇都扣】

IsEulerCiruit(G){
    for v in G
        if v.deg mod 2 != 0
            return false
    return true
}
printEulerCircuit(G, u){
    for u in G
        for v in G.Adj[u]
            if IsConected(G.remove(u, v)) == true   //判斷移除這個edge還會不會是connected 
                G.remove(u, v)
                print(u)
                printEulerCircuit(G, v)
}

【複雜度】
判定是否為euler circuit需看過每個V的degree，需花

$O(|V|)$，印出euler circuit需

$O(|V|+|E|)$且判定移除edge是否為connected也需

$O(|V|+|E|)$，因此時間複雜度為

$O(|V|)+O((|V|+|E|{)}^2)=O((|V|+|E|{)}^2)$

印出euler circuit需多

$O(|V|)$來存，因此空間複雜度為

$O(|V|)$