Copyright

Graph Theory Chapter Exam

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!

Page 1

Question 1 1. How many times do you visit a vertex when traveling either a Hamilton circuit or path?

Question 2 2. A complete graph with 3 vertices has how many Hamilton circuits?

Question 3 3. What kinds of graphs does Fleury's algorithm work for?

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

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

Page 2

Question 6 6. Find a Hamilton path.

Question 7 7. How many vertices can be odd in a semi-Eulerian graph?

Question 8 8. How many Euler paths are there in this graph?

Question 9 9. How many Euler circuits are in this graph?

Question 10 10. What is the traveling salesman problem equivalent to in graph theory?

Page 3

Question 11 11. A complete graph is a graph where each vertex is connected to how many of the other vertices?

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

Question 13 13. How many components does this graph have?

Question 14 14. What can be said about this graph?

Question 15 15. Which of the following describes a loop?

Page 4

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

Question 17 17. Which method is optimal?

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

Question 19 19.

Which method is efficient?

A. Brute force

B. Nearest neighbor

C. Repeated nearest neighbor

D. Cheapest link

Question 20 20. How many odd vertices does this graph have?

Page 5

Question 21 21. Which of the methods is both optimal and efficient?

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

Question 23 23. If a graph has 15 edges, what must the degrees of the vertices add up to?

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

Question 25 25. Eulerize this graph.

Page 6

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

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

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

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

Question 30 30. What is the brute force method?

Graph Theory 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!

Math 106: Contemporary Math  /  Math Courses
Support