---
title: Homework XI
---
# P1
[CLRS 3rd] Exercise 23.1-6
## Topic
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.
## Solution
如果將一個已找出MST的graph做n次cut，那cut完後就會產生n+1個graph。
這也代表被cut的edge中一定會有至少一條是原本MST裡連接graph的edge。
而若每做一個cut，都含有一個唯一且weight最小的edge，那也就代表這個edge一定是MST裡連接graph的edge，且唯一連接的edge。
在滿足上述的條件之下，每個edge都是weight最小且唯一，得:此Tree是graph唯一的MST。
### Counter-example:
let G=(V,E);
V={a,b,c} ;
E={(a,b),(b,c),(a,c)} with weights 2,3 and 2 respectively
此graph的MST是由兩個edge為2的邊所組成，而此MST也是唯一的。
但當我們對a做cut，被cut後的edge並沒有unique light edge，因為兩個weight為2的edge都是light edge。
反證得: 如果Tree是graph裡唯一的MST，並不代表所有graph裡的cut都含有 unique light edge。
# P2
[CLRS 3rd] Exercise 23.1-8
## Topic
Let T be a minimum spanning tree of a graph G, and let L be the sorted list of the edge weights of T. Show that for any other minimum spanning tree T′ of G, the list L is also the sorted list of edge weights of T′.
## Solution
假設T中第一條edge為(u,v)連結AB，如果(u,v)不為T'中的edge，這時將(u,v)加入T'會形成一個cycle，為了解決cycle須從T'中刪除一條edge，
如果存在一條比(u,v)大的edge，代表T'不為 *MST*，
如果存在一條比(u,v)小的edge，那代表T不為 *MST*，
所以只能選擇和(u,v)相同weight的edge，
每個edge重複做上面的步驟都能找到相同weight的edge，所以L和L'相同。
# P3
[CLRS 3rd] Exercise 23.1-11
## Topic
Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of the edges not in T. Give an algorithm for finding the minimum spanning tree in the modified graph.
## Solution
如果加入一個decreased-edge到 T,會產生一個cycle,所以要移除組成這個cycle的所有edge裡weight最大的edge
```PSEUDO=
DFS(u,v){
for each a ∈ Adj[v]
cycle<-edge(v,a);
if(a==u)
return cycle;
else
DFS(u,a);
}
New_tree(T){
T<-edge(u,v);
DFS(u,v);
T.remove(edge in the cycle of maximum weight);
}
```
# P4
[CLRS 3rd] Exercise 23.2-4
> 時間複雜度我覺得應該這樣才對 稍微小改一下[name=Joe_Wang][color=#7728cc]
## Topic
Suppose that all edge weights in a graph are integers in the range from 1 to ∣V∣. How fast can you make Kruskal's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?
## Solution
原版時間複雜度: O(E log V)
## a.
weight介於1到V, 可以用counting sort在O(V + E)時間內sort完
sort: O(V + E)
find and union: $O(E\alpha(E))$
整體時間複雜度為O(V + E($\alpha$(E))) // $\alpha$(E)很小
## b.
weight介於1到W, 可以用counting sort在O(W + E)時間內sort完
sort: O(W + E)
find and union: $O(E\alpha(E))$
則整體時間複雜度為$O(W + V +E\alpha(E))$
```PSEUDO=
KRUSKAL(G){
A = ∅
For each vertex v ∈ G.V:
MAKE-SET(v)
For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v):
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A
}
```
# P5
[CLRS 3rd] Exercise 23.2-5
## Topic
Suppose that all edge weights in a graph are integers in the range from 1 to ∣V∣. How fast can you make Prim's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?
## Solution
原版時間複雜度: O(E log V)
### a.
weight介於1到V, 可以用van Emde Boas priority queue
初始化: O(V)
extract-min: O(VlglgV)
change-key: O(ElglgV)
總體時間複雜度: O((V+E)lglgV)
\\
在weight範圍介於 0 to V(正整數)間的情況下，可以用 van Emde Boas priority queue 來實作 Prim’s algorithm
VEB tree operation time:
search--O(loglogV)
insert--O(loglogV)
delete--O(loglogV)
1.initial -- $O(V)$
2.Extract-Min -- $V*O(loglogV)$
3.Change-Priority -- $E*O(loglogV)$
總體時間複雜度: $O((V+E)lglgV)$
### b.
weight介於1到W,
//
用doubly linked list的資料結構
建一個陣列Q[W]來實作priority queue
Extract-Min只須找到第一個不為Nil的
Change-Priority key值從j降到i:
把該點加到Q[i]並從Q[j]移除
1.initial -- $W*O(V)=O(V)$
2.Extract-Min -- $E*O(W)=O(E)$
3.Change-Priority -- $E*O(1)=O(E)$
W為常數,因此時間複雜度為: $O(E+V)$
//
# P6
[CLRS 3rd] Exercise 23.2-7
## Topic
Suppose that a graph G has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to G?
## Solution
e : the number of new incident edges
E' : e+E
(1)把新的vertex.edge加入MST後直接用 Kruskal’s Algorithm 做新的MST:
case1時間複雜度--O(E'logE')
```
1.建新的graph O(E')
2.取得最小權重的邊 最多E'次 O(E'logE'+E')
檢查是否構成cycle:O(1)
union---O(1)
find---O(α(E')) 約等於O(1)
```
(2)任意加一條new_edge到MST,再依序加入其他new_edge後把形成的cycle裡權重最大的edge移除
在E遠大於e時會較快
case2時間複雜度--O(e*(E+V))
```
1.找出最小的new incident edge加入T O(e)
2.依序加入其他新的edge,e-1次 O(e*(E+V))
DFS()---O((E+2)+(V+1))
remove largest edge in cycle
```
# P7
## Topic
Perform the Kruskal’s and Prim’s algorithms to the figure below
## Solution
### Kruskal's algorithm
```pesudo=
Kruskal(graph){
A= empty set;
for(each edge in order by nondecreasing weight)
if(adding the edge to A doesn't create a cycle)
add it to A;
if(|A|==n-1) break;
}
```
adding the edge from v1 to v3 into A.
***Doesn't create a cycle***
adding the edge from v4 to v6 into A
***Doesn't create a cycle***
adding the edge from v2 to v5 into A
***Doesn't create a cycle***
adding the edge from v3 to v6 into A
***Doesn't create a cycle***
adding the edge from v1 to v4 into A
***Does create a cycle, so we won't add the edge into A***
adding the edge from v2 to v3 into A
***Doesn't create a cycle***
### Prim's algorithm
```pseudo=
Built a priority queue Q for V with key[u] = ∞ ∀u ∈ V;
key[v0] = 0; π[v0] = Nil; // Any vertex will do
While (Q != empty set) {
u = Extract-Min(Q);
for( each v ∈ Adj(u) )
if (v ∈ Q && w(u, v) < key[v] ) {
π[v] = u;
key[v] = w(u, v);
Change-Priority(Q, v, key[v]);
}
}
```
***pick v1 to be the root, pop v1***
***key[v3] is the smallest in priority queue, pop v3***
***key[v6] is the smallest in priority queue, pop v6***
***key[v4] is the smallest in priority queue, pop v4***
***key[v2] is the smallest in priority queue, pop v2***
***key[v5] is the smallest in priority queue, pop v5***
# P8
[CLRS 3rd] Problem 16-4 Scheduling variations
## Topic
Consider the following algorithm for the problem from Section 16.5 of scheduling unit-time tasks with deadlines and penalties. Let all n time slots be initially empty, where time slot i is the unit-length slot of time that finishes at time i. We consider the tasks in order of monotonically decreasing penalty. When considering task $a_j$, if there exists a time slot at or before $a_j$'s deadline $d_j$ that is still empty, assign $a_j$ to the latest such slot, filling it. If there is no such slot, assign task $a_j$ to the latest of the as yet unfilled slots.
a. Argue that this algorithm always gives an optimal answer.
b. Use the fast disjoint-set forest presented in Section 21.3 to implement the algorithm efficiently. Assume that the set of input tasks has already been sorted into monotonically decreasing order by penalty. Analyze the running time of your implementation.
## Solution
### a.
若所有task可以在deadline內完成, 理所當然可以獲得最佳解
若兩個task可以挑選, 但是只有一個空間, 挑penalty大者,
逾期的task從最後面找空間放, 避免讓後面的task逾期
則可以得最低penalty
### b.
```pseudo
MAKE-SET(X)
X.P = X
X.rank = 0
UNION(X,Y)
LINK(FIND-SET(X), FIND-SET(Y))
LINK(X,Y) // link 2 set
if X.rank > Y.rank
Y.p = X
X.high=Y.high
else
X.p =Y
y.low=x.low
if X.rank == Y.rank
y.rank = y.rank + 1
FIND-SET(X) //return root
if x!= x.p
x.p = FIND-SET(X.p)
return x.p
SCHEDULING-VARIATIONS(a)
D[1..n] is an array // point to the task it's deadline is i
for i = 1 to n
a[i].time = a[i].deadline
if D[a[i].deadline] != null //if a tree has been created
y = FIND-SET(D[a[i].deadline]) //find the tree's root
a[i].time = y.low - 1 //往左邊找空間
x = MAKE-SET(a[i])
D[a[i].time] = x //排進去
x.low = x.high = a[i].time
//鄰近的tree合在一起
if D[a[i].time - 1] != null
UNION(D[a[i].time - 1], D[a[i].time])
if D[a[i].time + 1] != null
UNION(D[a[i].time], D[a[i].time + 1])
```
MAKE-SET, UNION, LINK最多執行3n次
時間複雜度: O(n $\alpha$(n)) 依Theorem 21.14
Sign in with Wallet
Connect another wallet