Due Friday, October 7, in Gradescope.
All enrolled students should have been included in the course Gradescope roster before the due date; if you have not, please contact a TA.
What is the adjacency matrix for the directed graph whose Python adjacency list representation is shown below?
{ 0: [2,3,4], 1: [0, 2], 2: [0, 3], 3: [ ], 4: [1] }A Möbius ladder is an undirected graph with an even number \(n\) of vertices, which can be numbered from \(0\) to \(n-1\). Each vertex has three neighbors: the vertex numbered \(i\) is connected to vertices \(i-1\), \(i+1\), and \(i+\frac{n}{2}\) (all taken modulo \(n\)). It can be converted into a directed graph by making two copies of each edge, one in each direction. For each of the six types of object in the Goodrich & Tamassia object-oriented representation described in the lecture notes, state as a function of \(n\) how many objects of that type would be used to represent the resulting directed graph.
163 students only: Draw a depth-first search tree and a breadth-first search tree for the graph from question 1, with the starting vertex \(s=0\). In each case, whenever the algorithm loops over the neighbors of a vertex, use the ordering given by the adjacency list from question 1.
265 students only: Define a connected undirected graph to be unicursal if it has the following property: No matter which vertex you start a depth-first search from, and no matter which order you loop over the neighbors of each vertex, its depth-first search tree will be a single directed path, from the start vertex to a single leaf vertex. For instance, one kind of unicursal graph is a complete graph, in which there is an edge between every pair of vertices. Find an example of a unicursal graph that is not complete. Your answer can be a description of this graph in English, or it can be a drawing of the graph.
Compute the DFS numbers, escape numbers, and strongly connected components of the graph from question 1, with the same assumptions about starting vertex and search ordering as in question 3(a).