---
title: homework IX
---
# P1
[CLRS 3 rd ] Exercise 22.1-1
## topic
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?
## Solution
想知道一個點的in-degrees or out-degrees需要探查他每一個相鄰的點也就是邊的數量,而一個邊只可能代表一個in-degrees or out-degrees,所以計算整個graph的in-degrees和out-degrees皆需要O(V+E)
# P2
[CLRS 3 rd ] Exercise 22.1-3
## Topic
The transpose of a directed graph G=(V,E) is the graph $G^{T}=(V,E^T)$, where $E^T={(v,u)∈V×V:(u,v)∈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.
## Solution
$G(V,E)$
$G^T(V, E^T)$
### a. adjacency-list
$G(V,E)$
| Node | | | | | | |
| ---- |:--- | --- | --- | --- | --- | --- |
| A | E |F | | | | |
| B | C |E | | | | |
| C | | | | | | |
| D | | | | | | |
| E | F | | | | | |
| F | C |D | | | | |
$G^T(V, E^T)$
| Node | | | | | | |
| ---- |:--- | --- | --- | --- | --- | --- |
| A | | | | | | |
| B | | | | | | |
| C | B |F | | | | |
| D | F | | | | | |
| E | A |B | | | | |
| F | A |E | | | | |
將所有邊存在 集合陣列 edge_set 裡, 對所有邊 (u, v)進行交換
例如: A->E transpose to E->A
Pseudocode:
```pseudo=
transpose(graph){
let edge_set [1...graph.size()] be an linked list;
while(i<graph.size())
edge_set[graph[i].node].insert(graph[i]);
delete(graph[i].node);
if (graph[i] is empty)
i++;
return edge_set;
}
```
時間複雜度: $O(|V|+|E|)$
### b. adjacency-matrix
$G(V,E)$
| Edge | A | B | C | D | E | F |
| ---- |:--- | --- | --- | --- |:--- | --- |
| A | 0 | 0 | 0 | 0 | 1 | 1 |
| B | 0 | 0 | 1 | 0 | 1 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 | 0 | 0 |
| E | 0 | 0 | 0 | 0 | 0 | 1 |
| F | 0 | 0 | 1 | 1 | 0 | 0 |
$G^T(V, E^T)$
| Edge | A | B | C | D | E | F |
| ---- |:--- | --- | --- | --- |:--- | --- |
| A | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 1 | 0 | 0 | 0 | 1 |
| D | 0 | 0 | 0 | 0 | 0 | 1 |
| E | 1 | 1 | 0 | 0 | 0 | 0 |
| F | 1 | 0 | 0 | 0 | 1 | 0 |
沿著矩陣對角線做數值交換 則可以得到transpose後的矩陣
時間複雜度: $O(|V|^2)$
Pseudocode:
```pseudo=
transpose (graph){
let new_graph [1...graph.size(), 1...graph.size()] be an new matrix
for i = 1 to graph.size()
for j = 1 to graph.size()
new_graph[i][j]=graph[j][i];
return new_graph
}
```
# P3
[CLRS 3 rd ] Exercise 22.1-5
## topic
The square of a directed graph G=(V,E) is the graph $G^2=(V,E^2)$ such that (u,v)∈$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 representations of G. Analyze the running times of your algorithms.
## Solution
$G(V,E)$
$G^2(V, E^2)$
### a. adjacency-list
$G(V,E)$
| Node | | | | | | |
| ---- |:--- | --- | --- | --- | --- | --- |
| 1 | 2 | | | | | |
| 2 | 3 | | | | | |
| 3 | 4 | | | | | |
| 4 | 5 | 6 | | | | |
| 5 | | | | | | |
| 6 | 2 | | | | | |
$G^2(V, E^2)$
| Node | | | | | | |
| ---- |:--- | --- | --- | --- | --- | --- |
| 1 | 2 | 3 | | | | |
| 2 | 3 | 4 | | | | |
| 3 | 4 | 5 | 6 | | | |
| 4 | 5 | 6 | 2 | | | |
| 5 | | | | | | |
| 6 | 2 | 3 | | | | |
將所有邊存在 集合陣列 edge_set 裡, 對所有邊 (u, v)
計算edge_set[v]跟edge_set[u]的差集, 再把差集中的元素連在graph[u]後面
(集合用hash實做, $O(|V|)$)
由於不會刪除圖中的邊, 圖中有self-loop也不會有問題
時間複雜度: $O(|V| |E|)$
Pseudocode
```pseudo=
square (graph){
let edge_set [1...new_graph.size()] be an array of set
for i = 1 to new_graph.size()
edge_set[i].insert(graph[i])
for i = 1 to new_graph.size()
for edge in edge_set[i]
result = set.difference(edge_set[edge], edge_set[i])
graph[i].link(result)
return graph
}
```
### b. adjacency-matrix
$G(V,E)$
| Edge | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- |:--- | --- | --- | --- |:--- | --- |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 1 | 0 | 0 | 0 | 0 |
$G^2(V, E^2)$
| Edge | 1 | 2 | 3 | 4 | 5 | 6 |
| ---- |:--- | --- | --- | --- |:--- | --- |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 | 0 | 0 |
| 3 | 0 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 | 1 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 1 | 1 | 0 | 0 | 0 |
一般版:
時間複雜度: $O(|V|^3)$
複製整個圖在new_graph ($O(|V|^2)$)
掃描new_graph 如果看到new_graph[i, j] == 1
就把new_graph[i, ...] 跟 graph[j, ...]做or ( $O(|V|^3)$)
由於不會刪除圖中的邊, 圖中有self-loop也不會有問題
```Pseudocode=
square (graph){
new_graph = graph
for i = 1 to graph.size()
for j = 1 to graph.size()
if graph[i, j] ==1
for k = 1 to graph.size()
new_graph[i, k] = new_graph[i, k] || graph[j,k]
return new_graph
}
```
快快版:
時間複雜度: $O(|V|^2 + |E|* |V|)$
將每個點連出去的邊存在 vector<set<int>> edge_set 裡($O(|V|^2)$),
i為 1...n 的點, u 為i連到的點, v為u連到的點
再把graph[i, v]設為graph[u, v] (集合用hash實做, $O((|V| +|E|)* |V|)$)
由於不會刪除圖中的邊, 圖中有self-loop也不會有問題
Pseudocode
``` Pseudocode=
square (graph){
let edge_set [1...new_graph.size()] be an array of set
for i =1 to graph.size()
for j = 1 to graph.size()
if graph[i, j]==1
edge_set[i].insert(j)
for i =1 to graph.size()
for u in edge_set[i]
for v in edge_set[u]
graph[i][v] = graph[u][v]
return graph
}
```
# P4
[CLRS 3 rd ] Exercise 22.1-6
## topic
Most graph algorithms that take an adjacency-matrix representation as input require time $\Omega(V^2)$, but there are some exceptions. Show how to determine whether a directed graph G contains a universal sink − a vertex with in-degree ∣V∣−1 and out-degree 0 − in time O(V), given an adjacency matrix for G.
## Solution
判斷一個graph裡有沒有universal sink,首先要先了解universal sink的定義.
universal sink就是所有的點都指向某個點(Vi),而(Vi)並沒有指向任何其他的點。
Example:
| Edge | 1 | 2 | 3 | 4 |
| ---- |:--- | --- | --- | --- |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 0 | 1 |
| 3 | 0 | 1 | 0 | 1 |
| 4 | 0 | 0 | 0 | 0 |
假設我們從左上角開始走,也就是(1,1)。
一直往右走到底,除非遇到數值為1,那就往下走。
並持續以上的規律:
可得(1,1)->(1,2)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)
最終停在4的位置,於是我們檢查第4列是否全部為0並且第4行是否全部為1(4,4除外)
若符合上述條件，則我們找到universal sink;反之,則無。
時間複雜度: $O(|V|)$
Pseudocode
``` pseudo=
universal_sink(graph){
int i=1,j=1;
while (i<|V| && j<|V|)
if (matrix[i][j]==1)
i+=1;
else
j+=1;
if(matrix[i][k]==0 for every k && matrix[k][i]==1 for every k!=i)
return yes(we find a universal sink at i);
else
return no(there is no universal sink);
}
```
# P5
[CLRS 3 rd ] Exercise 22.2-7
## topic
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 it is possible to perform such a designation, your algorithm should produce it.
## Solution
將n個wrestlers當作vertices, r對對戰組合當作邊(有對戰的vertice相連)
因為對戰組合不能同陣營,所以兩相鄰點塗上不同顏色=>二色塗色問題
找第一個點開始做BFS,如果第一點為“babyfaces”其相鄰點為“heels”,如果為“heels”相鄰點則為“babyfaces”
當第一round的BFS做完,找下一個還沒塗色過的點繼續BFS(因為一個圖可能會有數個connected component)直到所有點都塗色
所以當n個點被塗色時,r個邊也被全部走過一次=>時間複雜度=$O(n+r)$
``` pseudo=
two_color(graph){
while(not travel all vertice){
if(vertice is colored and different from the previous color){
return no answer
}
else{
draw color (different from the previous one)
}
travel to next vertice (BFS or next connected component)
}
return yes
}
```
# P6
[CLRS 3 rd ] Exercise 22.2-8
## topic
The diameter of a tree T=(V,E) is defined as max$_{u,v∈V}$δ(u,v), that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.
## Solution
對樹中的一個點u, 做BFS可以知道u到樹中任何一點v的對最短距離,
BFS有兩種情況, 以端點或非端點為起點,
以端點為起點做BFS, 可以得到樹中最短的最長路徑(diameter)
以非端點為起點做BFS, 可以得到距離非端點最遠的端點
因此只要==做兩次BFS就可以保證得到樹中最短的最長路徑(diameter)==
時間複雜度O(|V|+|E|)
```pseudo=
diameter(graph){
//graph is in adjacency-list form
U is a node randomly picked as a root
table is an array recording the distances to the other nodes
table = BFS(graph, U) //O(|V|)
V is the node farthest from U
table.clear()
table = BFS(graph, V) //O(|V|)
return table.longest_distance
}
```
# P7
## topic
Given an undirected graph G, determine whether there is a Eulerian Circuit
(要求回到出發點) in G. If there is a Eulerian Circuit in G, Output the circuit.
## Solution
根據觀察, 只要==圖中沒有點的degree是奇數,還有任何degree不是0的點都是連通的, 圖中就會存在 Eulerian Circuit.==
``` pseudocode
eulerian (graph){
check every node's degree
if any node's degree is odd
return None
R is a randomly chosen root
S is a empty stack
S.push(R)
DFS (graph, S) //do DFS to graph, using S to store the circuit
if any non-zero degree vertices are not connected
return None
else
return S // circuit stored in S
}
```
Sign in with Wallet
Connect another wallet