Homework 9: Fun with graphs

Remember to turn in a neat final draft of this homework on a separate sheet of paper.

Given below is an adjacency list representation of a graph:

A: [(A, C, 6), (A, G, 5)]
B: [(B, C, 7), (B, D, 8), (B, G, 5)]
C: [(C, A, 6), (C, B, 7), (C, E, 3), (C, F, 7), (C, G, 3), (C, H, 9)]
D: [(D, B, 8), (D, H, 8)]
E: [(E, C, 3), (E, F, 4)]
F: [(F, E, 4), (F, C, 7)]
G: [(G, A, 5), (G, B, 5), (G, C, 3)]
H: [(H, C, 9), (H, D, 8)]

1. Describe the important properties of the graph above, using the terminology we know about graphs. (Is it directed/undirected, cyclic/acyclic, connected/unconnected, etc.)
2. Draw a picture of the graph above.
3. Show the adjacency matrix representation of the graph above.
4. Perform a depth-first traversal of the graph above, starting with node A at the top of the stack, and list the order the nodes are visited in. Show your work.
5. Perform a breadth-first traversal of the graph above, starting at node A, and list the order the nodes are visited in. Show your work.
6. Draw an undirected, unweighted graph with 7 vertices, and the following degrees of each vertex: \[2, 3, 1, 4, 4, 5, 1\] Label each vertex with its degree in your final, neatly drawn graph.