# HW 9: Graphs

## Solution

You can find the solution here

## Overview

This is a written homework assignment. It is due in class, in hard-copy.

### Due Date

This homework is due **Wed. 21 Nov. in class**

### Grading

The assignment is graded out of **100 points**. The value of questions are described below.

### Submission and Starter Code

Submission must occur in hard copy at the start of class.

## Problems

Consider the Adjacency list representation of a graph below:

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)]

- [10 points] Describe the important properties of the graph above, using the terminology we know about graphs. (Is it directed/undirected, cyclic/acyclic, connected/unconnected, etc.)
- [15 points] Draw a picture of the graph above.
- [20 points] Show the adjacency matrix representation of the graph above.
- [20 points] 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.
- [20 points] 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.
- [15 points] 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.