CPSC 220
Graph Exercises

Consider the directed weighted graph G with vertex and edge sets below:

  V = {A,B,C,D,E,F,G}

  E = {(A,B,10),
       (A,D,20),
       (B,C,2),
       (B,D,6),
       (B,F,6),
       (B,G,8),
       (C,E,8),
       (D,F,5),
       (D,G,1)
       (G,E,1)
       (G,F,3)}

1. Suppose we are considering adding edges to or removing edges from G.
   1. For the given size of V, what is the maximum possible size of E (assuming no self-loops)?
   2. For the given size of V, what is the minimum possible size of E?

2. Assume that an integer takes one cell and a reference takes two cells, and it is not necessary to store the actual label on each vertex,
   1. How much space would it take to store G using
      1. an adjacency list?
      2. an adjacency matrix?
   2. Develop a general formula in terms of |V| and |E| for the space required for each representation under these assumptions. Then evaluate the space tradeoffs when
      1. |E| = |V|
      2. |E| = |V|²

   For questions 3-7, assume that "for each adjacent vertex" in any relevant algorithm takes the vertices in alphabetical order.

3. Show the order in which the vertices will be visited in a breadth-first search from A.

4. Show the order in which the vertices will be visited in a depth-first search from A.

5. As we have discussed, a tree is a special case of a graph.
   1. What edges would you have to remove from the graph above to turn it into a binary tree with the root at A?
   2. Draw the resulting tree, arranging the children of each node in alphabetical (i.e., the label of the left child should be smaller than the label of the right child). What tree traversal are you doing if you start at the root and do a
      1. DFS?
      2. BFS?

6. Use Dijkstra's algorithm to find the shortest route and distance from A to every other vertex.

7. Viewing this as an undirected graph, find a minimum spanning tree using
   1. Prim's algorithm
   2. Kruskal's algorithm