**Question 1. **Figure 1 shows a directed graph *G*.

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

- Give the adjacency-list representation of
*G*. When giving your answer, please order the vertices alphabetically. [2.5 points] - Give the adjacency-matrix representation of
*G*. When giving your answer, please order the vertices alphabetically. [2.5 points]

**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.

- 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*d*= 1 and*x.π*=*y*, then you can write*x*(1*,y*). [3 points] - 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 *b _{i,j }*is defined by

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

*b _{i,j }*= 1

*,*if the

*j*-th directed edge enters the

*i*-th vertex; (1)

^{}0

*,*otherwise

*.*

Explain what the entries of the matrix product *BB ^{T }*represent, where

*B*is the transpose of

^{T }*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.

- What is the purpose of assigning colors to vertices?
- 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.

- 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.

## Reviews

There are no reviews yet.