Discrete Math Chapter 15 Test ReviewName ______

Use the graph below for questions 1 and 2.

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.

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.

outside

Use the graph below to answer question 8 – 13.

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.

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?

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.

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.

18. Use Fleury's algorithm to find an Euler circuit in the graph below.

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.

21. Using the graph below, determine the weight of the Hamilton circuit A, B, F, G, D, E, C, A.

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

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.

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.