## Try It Now

Work these exercises to see how well you understand this material.

### Exercises

- Estimate the number of vertices and edges in each of the following graphs. Would the graph be considered sparse, so that an adjacency matrix would be inefficient?
- Vertices: Cities of the world that are served by at least one airline. Edges: Pairs of cities that are connected by a regular direct flight.
- Vertices: ASCII characters. Edges: connect characters that differ in their binary code by exactly two bits.
- Vertices: All English words. Edges: An edge connects word
*x*to word*y*if*x*is a prefix of*y*.

- Directed graphs G
_{1}, . . . , G_{6}, each with vertex set {1, 2, 3, 4, 5} are represented by the matrices below. Which graphs are isomorphic to one another?

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.