# CompSci 163/265, Spring 2015, Homework 1

1. In class we discussed three representations of graphs:

• an adjacency matrix (a matrix whose rows and columns are indexed by the vertices, with a $1$ in row $i$ and column $j$ if there is an edge from vertex $i$ to vertex $j$),
• an adjacency list (in a form described by Goodrich and Tamassia in which there is an object for each vertex and edge, each edge object points to its two vertex endpoints, and each vertex object points to two collections of edge objects for its incoming and outgoing edges), and
• a Python representation described by van Rossum in which a graph is a dictionary whose keys are vertices and whose values are lists of the outgoing neighbors of each vertex (see the link for examples).

1. Draw the graph whose adjacency matrix is below, using circles for the vertices and arrows for the edges. Label each vertex with the number of its row and column.

$\left( \begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ \end{matrix} \right)$
2. How many objects of each type would be needed to represent the same graph in the Goodrich and Tamassia representation?

3. Write down a Python expression that produces the van Rossum representation for the same graph. In this expression, use the number i to represent the vertex whose adjacencies are given by the ith row and column of the matrix.

2. In the low-attention-span web surfer model used to define the pagerank algorithm, suppose that the probability of getting bored and going to a uniformly random page is $0.1$, and the probability of following a random link from the current page is $0.9$. Given the graph represented by the same matrix above, starting from a state in which each vertex is equally likely, what would be the probabilities of being on each of the four vertices after a single time step?

1. Draw a graph, a designated starting vertex in your graph, and a sequence of the vertices that can be reached from the starting vertex, with the property that the sequence you give could have been generated by a depth first search, but not by a breadth first search.

2. Draw a graph, a designated starting vertex in your graph, and a sequence of the vertices that can be reached from the starting vertex, with the property that the sequence you give could have been generated by a breadth first search, but not by a depth first search.

3. (For 265 students only.) Draw a graph in which it is impossible for depth first search and breadth first search to generate the same sequence as each other, no matter which starting vertex is chosen and no matter which ordering is chosen for the list of edges out of each vertex. Explain why the two search algorithms must always generate different sequences for your graph.

3. For the graph below, draw a possible depth-first search forest. Additionally, label each vertex with the lowlink number that would be computed by Tarjan's strongly connected components algorithm, and list the strongly connected components. Don't forget to include any single-vertex components, if they exist.