50.004–Homework Set 4 Solved

Question 1. Figure 1 shows a directed graph G.

 

Figure 1: A directed graph for use in Question 1 and Question 2.

(i)      Give the adjacency-list representation of G. When giving your answer, please order the vertices alphabetically.     

(ii)    Give the adjacency-matrix representation of G. When giving your answer, please order the vertices alphabetically.     

Question 2. Consider the directed graph G in Fig. 1, and run the breadth-first search on G, with vertex a as the source vertex. Assume that at each level, the vertices are traversed in alphabetical order.

(i)      Show the d and π values that result from running breadth-first search on the directed graph G. Note that d is the attribute representing the distance/level for the breadth-first search, while π is the attribute representing the pointer that points to the previous vertex. You can write in the form of V ertex(d,π). For example, if x is a vertex such that x.d = 1 and x.π = y, then you can write x(1,y).

(ii)    Based on your answers from the previous part, find a shortest path from vertex a to vertex g. Make sure you use the d and π values of the vertices of G.

1

Question 3. The incidence matrix of a directed graph G = (V,E) with no self-loops is a

|V | ∗ |E| matrix B whose (i,j)-th entry bi,j is defined by



                                                      −1,        if the j-th directed edge leaves the i-th vertex;



bi,j = 1, if the j-th directed edge enters the i-th vertex; (1) 0, otherwise.

Explain what the entries of the matrix product BBT represent, where BT is the transpose of

B. Justify your answer with details.                                                                                                                                 

Question 4. The pseudocode for one possible implementation of the breadth-first search (BFS) algorithm is shown on page 29 of slides L06 (“queue + adj list implementation version”). For this question, we shall refer to this particular pseudocode.

(i)      What is the purpose of assigning colors to vertices?           

(ii)    In this pseudocode, three distinct colors WHITE, GRAY, BLACK are used as the possible attribute values for the color attribute of a vertex. Explain how this pseudocode can be modified, so that only a single bit is used to store the color attribute value of every vertex.

             Justify your answer with details.                                                                                                                        

Question 5. Most graph algorithms that take an adjacency-matrix representation of a directed graph G = (V,E) as input has time complexity Ω(|V |2), but there are some exceptions. A universal sink is a vertex with in-degree |V | − 1 and out-degree 0. For this question, suppose that the adjacency matrix A for some directed graph G is provided.

(i)      Design an algorithm that takes as its input the adjacency matrix A and an index k, and returns TRUE or FALSE, depending on whether the k-th vertex of G is a universal sink or not, respectively, such that your algorithm runs in O(|V |) time. Please give your algorithm in pseudocode, and please explain in detail why your pseudocode works, as well as why your algorithm runs in O(|V |) time.

Explain why G can have at most one universal sink. Design an algorithm that takes as its input the adjacency matrix A, and either returns the character string “There is no universal sink” if G has no universal sink, or returns the index of the universal sink, if G has a universal sink