Question 1:

Suppose that the strongly-connected components algorithm discussed in class is run on the graph. Any time an arbitrary choice of which vertex to consider next needs to be made, the vertex from among the possible choices that comes earlier in the alphabet is chosen. (Be sure that you understand all the ways in which the algorithm makes arbitrary choices. The algorithm does two depth-first searches, each of which makes some arbitrary choices. Those arbitrary choices should always favor the alphabetically earlier vertex. For example, if you have a choice between vertex A and vertex B, choose vertex A because it comes earlier in the alphabet.)

Iidentify strongly-connected components as follows. Write the label of each vertex in the component in alphabetical order with no spaces or punctuation. For example, if the component is made out of vertices X, T, and Q, enter QTX. Don't enter TQX or qtx or q-t-x.

a) Which strongly connected component is identified first?

b) Which strongly connected component is identified second?

c) Which strongly connected component is identified third?

d) Which strongly connected component is identified fourth?

e) Which strongly connected component is identified fifth?

f) What is the minimum number of edges you can add to this graph to make it strongly connected?