Print bookPrint book

Try It Now

Site: Saylor Academy
Course: CS202: Discrete Structures
Book: Try It Now
Printed by: Guest user
Date: Thursday, 3 April 2025, 6:40 PM

Description

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

Table of contents

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.

Solutions

  1. Answer: In Figure 9.1.10, computer b can communicate with all other computers. In Figure 9.1.11, there are direct roads to and from city b to all other cities.

  2. Answer:


  3. Answer: The maximum number of edges would be \binom{8}{2} = \frac{(7)(8)}{2} = 28.

  4. Answer:
    1. \binom{n}{2} = \frac{(n-1)n}{2}
    2. n - 1, each vertex except the champion vertex has an indegree of 1 and the champion vertex has an indegree of zero.

  5. Answer:
    1. Not graphic - if the degree of a graph with seven vertices is 6, it is connected to all other vertices and so there cannot be a vertex with degree zero.
    2. Graphic. One graph with this degree sequence is a cycle of length 6.
    3. Not Graphic. The number of vertices with odd degree is odd, which is impossible.
    4. Graphic. A "wheel graph" with one vertex connected to all other and the others connected to one another in a cycle has this degree sequence.
    5. Graphic. Pairs of vertices connected only to one another.
    6. Not Graphic. With two vertices having maximal degree, 5, every vertex would need to have a degree of 2 or more, so the 1 in this sequence makes it non-graphic.