PROBLEM 1 (24 points): Consider the directed graph below. 2 A. (2 points) There are 6 vertices in this graph (labeled a, b,..., f). QUESTION: How many edges are there in the graph? List them as ordered pairs of vertices (see (D below) if you are unsure exactly what this means.) B. (2 points) Indegree/Outdegree: In a directed graph, edges are ordered pairs of vertices where the first vertex is the source vertex of the edge and the second vertex is the destination vertex. For example, (b,f) is an edge in the graph above and b is the source vertex and f is the destination vertex of that edge. So far, so good. The outdegree of a vertex is the number of edges for which it is the source - or, informally, the number of "arrows leaving the vertex." Similarly, the indegree of a vertex is the number of edges for which that vertex is the destination or, informally, the number of "incoming arrows". QUESTION: For each vertex in the graph above, determine both its indegree and outdegree. Sle your answer in table form C. (2 points) Draw the adjacency-matrix representation of the graph. Order the row/columns in the matrix alphabetically. See linked lecture notes for an example D. (2 points) Draw the adjacency list representation of the graph. As in (C) order the vertices alphabetically - both in the "vertex array" and in the "neighbor-list" for each vertex. See linked lecture notes for an example E. (4 points) Simple Paths: A simple path is a path which does not have any cycles ("loops") -- i.e., simple paths do not visit any vertices multiple times. QUESTION: how many distinct simple paths are there from vertex e to vertex d? List each path F. (4 points) Shortest Paths: We will say the length of a path is the number of edges it traverses. A shortest path between two vertices is exactly what you would think: a path a. What is the shortest path length from vertex e to vertex d (in number of edges)? b. How many distinct shortest paths are there from vertex e to vertex d? List them with minimum length. QUESTIONS G. (4 points) Simple Cycles: a cycle in a directed graph is a path that returns to its starting vertex. For example, the path f a b f in the given graph is a cycle. A simple cycle is a cycle which has no repeated vertices except the starting/ending vertex (the cycle described above is simple). (Most people don't even think much about nor simple cycles; this definition is given just for completeness.) QUESTIONS: a. How many simple cycles in the graph above start and end at vertex d b. List each of these simple cycles