Try It Now
Work these exercises to see how well you understand this material.
Exercises
- 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?
- 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.
- What is the maximum number of edges in an undirected graph with eight vertices?
-
- How many edges does a complete tournament graph with n vertices have?
- How many edges does a single-elimination tournament graph with n vertices have?
- Determine whether the following sequences are graphic. Explain your logic.
- (6, 5, 4, 3, 2, 1, 0)
- (2, 2, 2, 2, 2, 2)
- (3, 2, 2, 2, 2, 2)
- (5, 3, 3, 3, 3, 3)
- (1, 1, 1, 1, 1, 1)
- (5, 5, 4, 3, 2, 1)
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.