Discrete Math Chapter 15 Test Review
Discrete Math Chapter 15 Test Review Name ______________________________
Use the graph below for questions 1 and 2.
[pic]
1. The graph models the football schedule for 5 area high schools. The vertices represent the teams and each game played is represented as an edge between two teams. How many games are schedule for West? East? Central?
2. List the teams Central will play. List the teams North will play.
3. Represent the graph below another way.
[pic]
4. What two parts do graphs consist of? 5. Model the following as a graph: AB, BC, BD, CC
6. In a group of 8 friends, many have dated other members of the group. Phoebe has dated Eric, Scott, and Russell. Ruth has dated Scott; Claire has dated Eric and Russell; and Anne has dated Eric, Scott, Russell, and Matt. Draw a graph that models the dating relationships of the friends.
7. Draw a graph that models the floor plan. Use vertices to represent the rooms and the outside, and edges to represent the doors.
[pic]outside
Use the graph below to answer question 8 – 13.
[pic]
8. What is the degree of vertex B? 9. What is the degree of vertex H? 10. Is vertex D odd or even?
11. Name at least two vertices that are adjacent to B. 12. Name a path starting at vertex A and ending at vertex F.
13. What edges are not included in the path A, B, C, D, E, G, F, D?
14. Determine whether the following is an Euler path, Euler circuit, or neither.
[pic]
F,G,E,D,G,B,C,D,B,A,F
15. The graph below has no Euler paths or Euler circuits. Why? What conditions must be met for an Euler path to exist? for an Euler circuit?
[pic]
16. The figure below shows the floor plan of a four-room house. Draw a graph to model the floor plan and then determine if it is possible to walk through every room and the outside, using each door only once.
[pic]
17. Determine whether the graph has an Euler path, Euler circuit, or neither. If the graph has an Euler path or circuit, use Fleury's algorithm to find one.
[pic]
18. Use Fleury's algorithm to find an Euler circuit in the graph below.
[pic]
19. Use the graph from #18 to find a Hamilton path.
20. Determine if each graph below has a Hamilton circuit. If so, determine the number of such circuits.
[pic] [pic]
21. Using the graph below, determine the weight of the Hamilton circuit A, B, F, G, D, E, C, A.
[pic]
22. Using the graph below and the Brute Force Method, which of the following is not an optimal solution?
I. A, B, C, D, A
II. A, C, B, D, A
III. A, B, D, C, A
IV. A, D, C, B, A
[pic]
23. Using the graph above and the Nearest Neighbor Method starting with vertex A, what is an approximate optimal solution?
24. From the graph below, draw a spanning tree.
[pic]
25. Use Kruskal's algorithm to find the minimum spanning tree for the weighted graph shown below. Give the total weight of the minimum spanning tree.
[pic]
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- fy2021 july 9 mblc minutes
- piecing together the united states the difference between
- 5 themes of geography project
- map showing inventory and regional susceptibility for
- thomas pickering under secretary of state
- misled by the map how basic reference works
- webquest on maps for first graders
- document id 01 13 10 1 nasa
- discrete math chapter 15 test review
Related searches
- 16 1 chapter 15 capital structure basic
- chapter 15 capital
- chapter 9 test review quizlet
- chapter 4 test review answers
- unit 4 test review math answers
- chapter 15 9 maintaining transmission based
- chapter 15 section 1 pages 532 537
- chapter 15 operating system
- chapter 15 answers
- chapter 15 metabolism answers
- solution of chapter 15 of operating system
- chapter 7 test review answers