3.16 Graph algorithms: trees, cycles and routes Quiz
Studying this course? Keep your progress in one place.
Pick an answer for each. Quizzes never use energy.
5 questions, one answer each
Each answer is checked as you go, with why.
See all 5 questions
1. A connected graph has exactly two vertices of odd degree. Which statement is true?
- A. It has an Eulerian circuit
- B. It has an Eulerian trail but no Eulerian circuit
- C. It has neither
- D. It has no Hamiltonian cycle
2. How many edges does a minimum spanning tree of a connected graph with 7 vertices have?
- A. 5
- B. 7
- C. 8
- D. 6
3. In the Chinese postman problem with four odd vertices, what is done?
- A. Pair the odd vertices so that the total repeated distance is least
- B. Delete the vertex of highest degree
- C. Find a minimum spanning tree
- D. Start at the nearest vertex
4. The deleted vertex algorithm gives which of these for the travelling salesman problem?
- A. An upper bound
- B. The exact optimum
- C. A lower bound
- D. A spanning tree of the whole graph
5. A walk that starts and ends at the same vertex and repeats no edge is called a
- A. path
- B. circuit
- C. cycle
- D. tree