Make your own free website on Tripod.com

Exercises 22.5-1

How can the number of strongly connected components of a graph change if a new edge is added?

Answer:

A directed graph is strongly connected if every two vertices are reachable from each other. If a new edge is added then we have two scenarios of result

Exercises 22.5-2

Show how the procedure STRONGLY-CONNECTED-COMPONENTS works on the graph of finger 22.6. Specially, show the finishing times computed in line 1 and the forest procedure in line 3. Assume that the loop of line 5-7 of DFS considers vertices in alphabetical order and that the adjacency lists are in alphabetical order.

Answer:

Run DFS(G). When DFS returns, every vertex u has been assigned a discovery time d[u] and a finish time f[u].

 

 

q

r

s

t

u

v

w

x

y

z

f[u]

16

20

7

15

19

6

5

12

14

11

 

 

 

 

 

 

 

 

 

 

 

Compute GT to get the adjacency list:

 

Run DFS(GT) in order

 

r

u

q

t

y

x

z

s

v

w

f[uT]

2

4

8

9

10

13

14

18

19

20

 

Re-order f[u] and f[uT] we have the strongly connected components as:

 

r

u

q

t

y

x

z

s

v

w

 

20

19

16

15

14

12

11

7

6

5

f[uT]

2

4

8

9

10

13

14

18

19

20

{r}, {u}, {q, y, t}, {x, z}, {s, w, v}

 

 

Exercises 22.5-3

Professor Deaver claims that the algorithm for strongly connected components can be simplified by using the original (instead of the transpose) graph in the second depth-first search and scanning the vertices in order of increasing finishing time. Is the professor correct?

Answer:

Credit will go to Kathy Macropol as her answer address all components of this question.

Also reference: http://www.cc.gatech.edu/classes/AY2003/cs3500c_spring/homework3/hwk3solution.pdf

 

No. As an example, consider the graph:


It's obvious by looking at it that it contains 2 strongly connected components, {A, B}, and {C}.

Running through the algorithm:

We get the finishing times (assuming alphabetical order):

A(1
B(2,3)
C(4,5)
A(1,6)

Arranging this in order of increasing finishing times:

B(2,3) -> C(4,5) -> A(1,6)

And then, going through DFS with this, we get:

B -> A -> C

Which means we have one strongly connected component consisting of nodes A, B, and C...which is incorrect.