# Graph Theory: Help and Review Chapter Exam

Choose your answers to the questions and click 'Next' to see the next set of questions. You can skip questions if you would like and come back to them later with the yellow "Go To First Skipped Question" button. When you have completed the practice exam, a green submit button will appear. Click it to see your results. Good luck!

### Page 1

#### Question 1 1. Which two vertices can you connect to Eulerize this graph?

#### Question 2 2. The start and end points must be which two vertices?

#### Question 3 3. How many vertices can be odd in a Eulerian graph?

#### Question 4 4. A weighted graph has what associated with each edge?

#### Question 5 5. How many vertices are in this graph?

### Page 2

#### Question 6 6. A complete graph with 6 vertices has how many Hamilton circuits?

#### Question 7 7. The total number of degrees in a graph is 20. How many edges does it have?

#### Question 8 8. Which of the following describes a loop?

#### Question 9 9. The best Hamilton circuit in a weighted graph is the one where the total cost is what?

#### Question 10 10. The traveling salesman problem involves visiting each city how many times?

### Page 3

#### Question 11 11. How many vertices in a graph do you visit by traveling a Hamilton path or circuit?

#### Question 12 12. How many vertices does this graph have?

####
Question 13
13.
Which method is efficient?

A. Brute force

B. Nearest neighbor

C. Repeated nearest neighbor

D. Cheapest link

#### Question 14 14. Which of the following will get you from point 3 to point 5?

#### Question 15 15. If you started at vertex 1, at which vertex will you end up if you are traveling a Hamilton circuit?

### Page 4

#### Question 16 16. How many Euler paths does this graph have?

#### Question 17 17. How many edges does this graph have?

#### Question 18 18. If vertex 3 is your starting point, which vertex can you not go to?

#### Question 19 19. Which of the following is a Euler path?

#### Question 20 20. What can be said about this graph?

### Page 5

#### Question 21 21. How many odd vertices can a graph have in order to use Fleury's algorithm?

#### Question 22 22. How many edges does this graph have?

#### Question 23 23. How many times are you allowed to pass an edge in an Euler path or circuit?

#### Question 24 24. Which is the nearest neighbor method?

#### Question 25 25. Find a Hamilton path.

### Page 6

#### Question 26 26. A graph with an Euler circuit can have at most how many odd vertices?

#### Question 27 27. What can be said about this graph?

#### Question 28 28. If a graph has 0 odd vertices, at which vertex must you start?

#### Question 29 29. Where do you end up in a traveling salesman problem?

####
Question 30
30.
Which of the following makes the traveling salesman problem more complicated?

A. A large number of cities

B. One way roads

C. Type of vehicle

#### Graph Theory: Help and Review Chapter Exam Instructions

Choose your answers to the questions and click 'Next' to see the next set of questions. You can skip questions if you would like and come back to them later with the yellow "Go To First Skipped Question" button. When you have completed the practice exam, a green submit button will appear. Click it to see your results. Good luck!