Exercises

  1. What is the significance of the fact that there is a path connecting vertex b with every other vertex in Figure 9.1.10, as it applies to various situations that it models?

  2. Draw a directed graph that models the set of strings of 0's and 1's (zero or more of each) where all of the 1's must appear consecutively.

  3. What is the maximum number of edges in an undirected graph with eight vertices?

    1. How many edges does a complete tournament graph with n vertices have?
    2. How many edges does a single-elimination tournament graph with n vertices have?

  5. Determine whether the following sequences are graphic. Explain your logic.
    1. (6, 5, 4, 3, 2, 1, 0)
    2. (2, 2, 2, 2, 2, 2)
    3. (3, 2, 2, 2, 2, 2)
    4. (5, 3, 3, 3, 3, 3)
    5. (1, 1, 1, 1, 1, 1)
    6. (5, 5, 4, 3, 2, 1)

 

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.