- Due before class on Monday, November 23
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:
- Describe the important properties of the graph above, using the terminology we know about graphs. (Is it directed/undirected, cyclic/acyclic, connected/unconnected, etc.)
- Draw a picture of the graph above.
- Show the adjacency matrix representation of the graph above.
- 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.
- 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.
- 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.
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)]