---
# System prepended metadata

title: homework IX

---

---
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)$
![](https://i.imgur.com/D2bG7tq.png)
$G^T(V, E^T)$
![](https://i.imgur.com/aNOWzHl.png)
### 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)$
![](https://i.imgur.com/0Od3L4V.png)
$G^2(V, E^2)$
![](https://i.imgur.com/oJKvtp6.png)

### 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:
![](https://i.imgur.com/C46yMs8.png)

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