Log in Page Discussion History Go to the site toolbox

CLRS Solutions

From BluWiki

Contents

Chapter 15

�15.1

4

Instead of filling matrices f_i[], we just need to remember the f_i[j-1] i=1,2 for j-1 so we use two variables and overwrite them every iteration.

�15.3

1

The enumeration is the least optimal for it multiplies subproblems (integers) whereas the recursion adds.

Chapter 21

�21.1

3

Find-Set is called twice for every edge, Union is called n-k times since there are k components- each components of size s accounts for (s-1) unions.

�21.2

...

�21.3

4

m LINK (if we start with m singletons) can create trees of max-height lgn if the rank heuristic is used. If we don't use the rank heuristic we might create a tree that is a chain of rank m. Then the FIND-SET using the path compression can take lg(k) for a vertex, but then lg(k) vertices become in height 1, and the rest of the vertices stemming from them have their height reduced by 1. After lgk FIND-SET on the same tree it becomes of height 1!, this effects half of the tree. after 2*lgk FIND-SETS (at maximal cost) the tree is of height 1. If we don't use the rank heuristic: we might have a chain and we use FIND-SET at its midpoints at cost: mlgm

Chapter 22

�22.2

3

while (Q != 0):
    j = dequeue(Q)
    for (i = 1 to n):
        if (E[j,i] == 1):
        �Proceed as the original....
It takes O(V^2) regardless of O(E)...

4

A sketch of a proof by induction on δ(v): δ(v)=0: This case is trivially true. δ(v)=n>0: then v∈adj[u], δ(u)=n-1, u is enqueued and v is discovered, if the order of the adjacency lists of any vertex is shuffled, still v must be discovered after u is enqueued (or another vertex of equal heghit)...

5

V = {0,1,2,3,4} E = {(0,1),(0,2),(1,3),(2,3),(2,4),(1,4)} Eπ = ={(0,1),(1,3),(0,2),(2,4)}

6

Basically we have to find out if the graph G is bipartite, or not. G is bipartite iff it has no odd cycles. We need to paint the vertices alternatively BLACK and RED, and if two adjacent nodes have the same color then the answer is NO, if no such nodes exists, then we're OK BLACK is 'GOOD', RED is 'BAD'...

7

Any path between two nodes consists of the paths between each node and the root r. Therefore we need to run BFS(G,r) and the 2 nodes with the greatest d(v) are the give as the diameter δ(u,v)=d(u)+d(v).

8

Basically, run BFS(G,r) for some arbitrary r, then traverse the tree depth-first, and for each non-tree edge- traverse and reverse it once when you first arive at one of its vertices...

�22.3

6

DFS(G)
   for (u ∈ V):
       color[u] = WHITE
       π[u] = NIL
   time = 0
   for (u ∈ V): 
       if (color[u]==WHITE):
           DFS-VISIT(u)
DFS-VISIT(u)
   color[u] = GRAY    
   //White vertex u has just been discovered.
   time+=1
   d[u] = time
   for v ∈ Adj[u]  
   //Explore edge(u, v).
       if color[v] = WHITE
           π[v] = u
           DFS-VISIT(v)
   color[u] = BLACK      
   //Blacken u; it is finished.
   time+=1
   f[u] = time
DFS-V-S(u):
   S = 0
   color[u] = GRAY
   time+=1
   d[u] = time
   push(u,S)
   while (S != 0):
       x = top[S]
       for (v in Adj[x]):
           if (color[v] == WHITE):
               push (v,S)
               color[v] = GRAY
               time+=1
               d[v] = time
               π[v] = x
       if (x == top[S]):
           color[x] = BLACK
           pop(S)
 

12

We need to modify DFS, so that for every node, we remember to which DFS-Tree it belongs. G isn't singly connected iff there is a forward edgee, or a cross edge between verticed in the same tree, or there are trees T1,T2,T3,T4: T1 has cross edges to T2 and T3, and T2,T3, each has cross edges to T4, or...

Now for each cross edge (u,v) between T,S, make the sub-tree stemming from v a new tree, and the tee-edge (x,v) a new cross edge. Then make a graph, H, with vertex for each tree, and edge connects two trees iff there's a cross edge between them. Then G is singly connected iff G has a back edge or H has a cycle. H has a cycle iff it has a back edge.

�22.4

2

We only run DFS-Visit on s. Then we check if s is a predecessor of t by comparing their time frames, and if so we check the same for each descendent of s that is a predecessor of t and increase the counter when there are more than 1...

3

G undirected graph is acyclic iff thre are no back edges in its DFS. Run DFS and stop as soon as a back edge appear. This happens as soon as a vertex is re-visited, or we run out of edges- in which case |E|<n ang G is a forest.

4

5

�22.5

3

No: we can have (u,v)∈E, u∈C, v∈C', f(C)>f(v) and so if u is the first vertex, then C' will be visited from v and the tree stemming from v will contain both C and C'.

5

We should add another field to the nodes, c[x], which marks the component to which they belong (this can be discover during the second DFS performed in the algorithm). Whenever a cross edges is discovered during the second DFS we add the corresponding edge if it has yet been added.

6

If we run BFS(C,u), BFS(C^T,u) and delete all other edges in C then we are left with a unique path from v t0 u and from u to v, for each v∈C. Then we have to delete all excess inter-component edges using the algorithm in 5.

7

G(V,E) semi-connected iff G^SCC is semi-connected, so we need to build G^SCC and then check its semi-connectivity, which is easy since it's acyclic so we can topologically sort it and find out whether it's connected or not...

22-Qs

1

Strait forward...

2

a: obvious... b: Remember that every edge is either tree or back for undirected G. If the property holds, then clearly there is no path from a descendant of v to an ancestor of v which passes over v, hence v is an articulation point. On the other direction: removing v disconnects G, yet G_π-G_π_v is connected and the only way to disconnect the graph is if such s exists... c: Recursively post-oreder walked the tree and calculate l[w]... d: By b (non-root) v is articulation point iff l[v]=d[v], and by a the root is articulation iff it has degree>1 and by c we need no more than O(V+E) time to calculate that. e: Easy... f: a tree edge e=(u,v) is a bridge iff l[v]<=d[v]... a back edge is never a bridge. g: If e is an edge between biconnected components than it is a bridge or else it would close a cycle between vertices from different bccs... If e is a bridge then u, v can't belong to the same bcc- if they do then there is a cycle containing them so removing e doesn't disconnects them.

h: remove all the bridges, then run DFS and find its scc which are (by abuse of notation) LSO the bcc

3

3-a: The conditions is clearly necessary: if not say in(v)<out(v) then we would never visit one of the out edges since we can only return in(v) times to v, and the case in(v)>out(v) is symmetrical. Sufficient: We start at an arbitrary vertex v, chose and arbitrary previously explored edge and travels through, according to the condition each time we enter a vertex we can exit it unless we get to v and after exploring all of its edges, in this case we've completed a cycle. Then pick a different vertex on this cycle and repeat... untll every vertex in is exausted. If we haven't visited edge e-(u,v) then u,v are not on the cecle, but then G is not connected since there is no way out of the cycle- a contradiction!

b: See a

4 =

Build DFS tree, then find out its scc, then compute the minimum of each scc, then sort topologically G_SCC and correct R(v)...

Chapter 23

�23.1

1

Take A = 0, S = u, then (u,v) is a light edge for the cut (S,V-S) which respects A.

2

Take an tree on three nodes: 01,02 w(01)=1 w(02)=2 S={0} A=0

3

If T is MST containing e=(u,v) take A=T-e, S=The connected component of u in T-e then e is a light edge crossing S.

4

A cycle with equal weights.

5

Let T be MST of G'. If T isn't a MST of G then e=(u,v) closes a cycle C in T such that ∀f∈C w(f)<w(e). In fact the edges of C' the cycle given in the premise, which doesn't belong to T is close a cycle with C and their weights are greater than any edge in C otherwise T is not a MST...

6

Assume e=(u,v)∈T': T&wedg;T' are MSTs. Let C=(S,T-S) be a cut crossed by e (every e of a MST has such cut- let S=the subtree rooted from v). But e is the unique edge crosses C by the premise. It follows that either e∈T' or no edge of T' crosses C, which is impossible since V(T')=V(G) and T' is connected.

A counter example for the other direction: take a star and close one triangle...

7

Das ist einfach

8

Fisrt observe: Let e=(u,v) be an edge of minimal weight, and T MST. If e∉T then e closes a cycle in T, so if we remove from the T an edge f from that cycle it must be that w(f)=w(e) or T∪{e}-{f} is a lighter spanning tree than T.

Now assume by induction that the n smallest weights in T,T' coincide. By similar argument to the one above it follows that the (n+1)th weights of L,L' also conside.

9

C=(V',V-V') is a cut, T' respects C, If T' isn't MST for G', Let R be one, then R also respects the cut and we can extend R to a spanning tree of G by adjoining to it all edges from T-T' and so we get a lighter spanning tree than T in G- a contradiction.

10

Assume T isn't MST with the new weight. If T' is MST for the new weight, (x,y)∈T' otherwise we'd get |T'|'=|T|'. In the old graph, |T'| = |T'|'+k < |T| = |T|'+k so T is not a MST of the old graph either!

11

Let e=(x,y)∉T w'(e)=w(e)-k, T a MST. e closes a cycle C in T. If ∃f∈C : w(e)-k < w(f) then T is not MST of the new graph because by replacing f with e we get a lighter tree. If ∀f∈C w(e)-k≥w(f) then T is MST of the new graph as well: Suppose it isn't- Let H be MST of the new graph. w(H)-k < w(T), and clearly it must be that e∈H. ... se bellow:

In general: if T is a spanning tree and not minimal, we can always improve it by replacing and edge with a lighter edge- this can be done by running the generic lgorithm, giving edges in T precedence over non tree edges of same weight, the first tree edge that is not a light edge can be replaced with a light edge.

For our purpose: if T isn't a MST than T can also be improved, but the only possible improvement is to replace a tree edge with e. So The algorith of joining e to T and checking the ccle C it closes for heavier edge than e is correct.

�23.2

1

Any order that gives precedence for the tree edges will result in T... The tree is constructed in increasing order of its weights list (which is the same for all trees by ex?)

2

...

3

O(VlgV + E) = o(ElgV) if E = ω(V)

4

We could use linear-time sorting and runs the algorithm at time O(Eα(V))

5

The cost for extract-min is lgV and lgW respectively in each case, so in the second case we can improve to O(E+VlgW). Instead of a normal heap we use a heap of stacks so multiple occurrences of the same value are stacked together and the heap has only W possible values.

6

we can use a bucket-sort which cost O(E) so kruskal's algo is faster.

7

We need to add the lightest new edge to T, then we need at most 1 improvement as described in a previous answer, to see if another new edge should replace a heavier tree edge in the cycle that it closes in the tree. A T-improvement takes take O(V).

8

E = {(0,1),(0,2),(1,2)} V1 = {1,2} w(1,2)=3, w(0,*)=1

23-Qs

1

a: MST is unique because the list of weights of MST is unique and only one list of edges in G can generate that list due to all weights being distinct. The second best spanning tree doesn't have to be distinct- a second best is always one T-improvement apart from the MST, but there could be 2 different improvements- i.e 2 supplants 4 and 4 supplants 6...

b: this follows from the fact that every tree can be repeatedly improved until we get a MST. A second best is a spanning tree 1 improvement apart of minimal weight from MST.

c: if r is the root, then max[u,v]=max(max[r,u],max[r,v]), we can run depth-first scan of the tree and during the scan compute max[r,u] and running time Θ(E+V)=O(V^2).

d: Find The MST, T, then run the algo from c, then run on all the non-tree edges and find edge e=(u,v) such that w(u,v)-max[u,v] is minimal. running time is O(V^2 + E + ElgV) = O(V^2)

2

a: every minimal-incident edge for a vertex v belongs to any MST, clearly the edge returned by the call MST-REDUCE all cross the cut (defined by the minimal edges) and PRIM-MSTare returns the safe edges that complete the tree to MST.

b: This follows since G is connected, so every vertex must have at list one other vertex in its equivalent class.

c: ??? what's there to prove???

d: Follows by c. But since |V'| ≤ |V|/2 is actually better than kE...

e: k = lglgV &rarrow; V(k)=V2^-k=V/lgv Prim(G')+preprocessing then takes: O(ElglgV + E +(V/lgV)lgV) = O(ElglgV).

f: Elglgv = o(VlgV)

3

a: Every edge e∉T is greater than any edge f∈T on the cycle that it closes in T.

b: Check for every edge e=(u,v) ∈E s.t. w(e)>b if it belongs to an MST: this can be done by checking whether e is a light edge that crosses the cut C = (u,V-u). for v∈V:

   if min{(u,v) : u∈ adj[v]} > b}
   //if adj is sorted this takes O(1)
       return NO

return YES //takes O(E) or O(V) if adj is sorted.

c:

   while(|E|>0):
       k = median_weight //takes O(E)
       If (bottleneck <= k):
           delete edges e s.t. w(w) > k
           //since there is a spanning tree of lesser weight
       els: contract all edges e s.t. w(e)<=k

In every iteration we get rid of half the edges, so the running time is: E∑2-i = O(E).

4

a: takes ElgE and returns a MST since T can't be improved

b: returns an arbitrary spanning true, runs at time O(E) if we remember for each visited vertex for which component it belongs.

c: returns MST but takes O(EV) because we have to check each cycle

Chapter 24

�24.1

1

Site Toolbox:

Personal tools
GNU Free Documentation License 1.2
This page was last modified on 3 December 2007, at 15:49.
Disclaimers - About BluWiki