Route inspection and travelling salesperson 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 network has all nodes of even degree. The shortest closed route traversing every arc has length
- A. equal to the total weight of the network
- B. equal to the total weight plus the shortest arc
- C. equal to twice the total weight
- D. equal to the weight of the MST
2. A network has four odd nodes. How many pairings must be checked?
- A.
- B.
- C.
- D.
3. The nearest neighbour algorithm gives
- A. the optimal tour
- B. a lower bound
- C. the minimum spanning tree
- D. an upper bound
4. The deleted vertex lower bound is
- A. the MST of all nodes plus the shortest arc
- B. twice the weight of the MST of all nodes
- C. the MST of the remaining nodes plus the two shortest arcs at the deleted node
- D. the MST of the remaining nodes plus the longest arc at the deleted node
5. The practical travelling salesperson problem differs from the classical problem because
- A. each node must be visited exactly once
- B. a node may be visited more than once, so shortest distances are used
- C. the route need not return to the start
- D. all arcs are one-way