Exercises

  1. 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?
    1. 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.
    2. Vertices: ASCII characters. Edges: connect characters that differ in their binary code by exactly two bits.
    3. Vertices: All English words. Edges: An edge connects word xto word yif xis a prefix of y.

  2. Directed graphs G1, . . . , G6, 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
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.