Try It Now

Site: Saylor Academy
Course: CS202: Discrete Structures
Book: Try It Now
Printed by: Guest user
Date: Thursday, March 28, 2024, 4:58 PM

Description

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

Table of contents

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.

Solutions

  1. Answer:
    1. A rough estimate of the number of vertices in the "world airline graph" would be the number of cities with a population greater than or equal to 100,000. This is estimated to be around 4,100. There are many smaller cities that have airports, but some of the metropolitan areas with clusters of large cities are served by only a few airports. 4,000-5,000 is probably a good guess. As for edges, that's a bit more difficult to estimate. It's certainly not a complete graph. Looking at some medium-sized airports such as Manchester, NH, the average number of cities that you can go to directly is in the 50-100 range. So a very rough estimate would be \frac{75 \cdot 4500}{2} = 168,750. This is far less than 4,5002, so an edge list or dictionary of some kind would be more efficient.
    2. The number of ASCII characters is 128. Each character would be connected to \binom{8}{2} = 28 others and so there are \frac{128 \cdot 28}{2} = 3,584 edges. Comparing this to the 1282 = 16,384, an array is probably the best choice.
    3. The Oxford English Dictionary as approximately a half-million words, although many are obsolete. The number of edges is probably of the same order of magnitude as the number of words, so an edge list or dictionary is probably the best choice.

  2. Answer: Each graph is isomorphic to itself. In addition, G2 and G4 are isomorphic; and G3, G5, and G6 are isomorphic to one another.