Week 10 - HackMD

# Week 10 :::info :::spoiler Click to Open TOC [TOC] ::: # Question :::info :::spoiler Click to Open Question ![](https://i.imgur.com/o02Puu3.png) ![](https://i.imgur.com/bmwWcg3.png) ## Check - [ ] Q1 - [ ] Q2 - [ ] Q3 - [ ] Q4 - [ ] Q5 - [ ] Q6 - [ ] Q7 ::: # Answer ## Q1 > - [name=chung] :::spoiler **【題目】** 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 ::: ![](https://i.imgur.com/Ke6NbWv.jpg) #### **【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 > - [name=xian] :::spoiler **【題目】** 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】** ![](https://i.imgur.com/sPVnblv.png =80%x) ### **【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|)_\#$ ![](https://i.imgur.com/Kx80iey.jpg =70%x) **【蘇都扣】** ```cpp= 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)_\#$ $G:\begin{bmatrix} 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{bmatrix} \Rightarrow G^T: \begin{bmatrix} 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{bmatrix}$ **【蘇都扣】** ```cpp= 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 > - [name=LXS] :::spoiler 題目 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$ $(G\times G)[m,n]=(m\to 1\times 1\to n)+...+(m\to k\times k\to n)\\ =(m\to 1\land 1\to n)\lor...\lor(m\to k\land k\to n)$ 這樣沒算到$m\to n$因為沒有self-loop時，$m\to m$是$0$，$m\to m\land m\to n = 0\times 1=0$，$m\to n\land 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】 ```python= 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|)時間達成$，因此時間複雜度為$O(|E||V|+|V|)$ ## Q4 > - [name=Mark] :::spoiler 題目 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，並回傳 **蘇都扣** ```python= 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 ```  :::spoiler **範例** ``` 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 > - [name=songchiu] :::spoiler 題目 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.) ![](https://i.imgur.com/i70swW4.png) ::: **【解題思路】** 用DFS來解，但稍微改良一下，讓它可以計算到底有幾條路徑符合並且讓每個點多一個欄位，計算它的子節點總共有幾個路徑 **【遞迴式】** $DFS(s,t) = s.sum = \begin{cases} 1, \mbox{if s=t} \\ 0, \mbox{if s have non visited point and s has no child} \\ sum(DFS(c,t)) \;c \in s's \; child, \mbox{if s have non visited point and s has child} \\ s.sum, \mbox{otherwise} \end{cases}$ **【蘇都扣】** ```cpp= 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 > - [name=yee] :::spoiler 【題目】 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。 **【蘇都扣】** ```c++= 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 > - [name=yee] :::spoiler 【題目】 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。 [李永樂老師解說](https://www.youtube.com/watch?v=QsMycO8B4M0) ![](https://i.imgur.com/K913GS6.png =80%x) 離散數學的ppt截下來的 **【蘇都扣】** ```c++= 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|)$