Travelling Salesman Problem

A walk which visits every vertex, returning to its starting vertex, is called a ...?

• tour

• extended walk

• spannig tree

• path

The travelling salesman problem involves finding a tour of minimum length.

• True

• False

How does the practical travelling salesman problem differ from the classical travelling salesman problem?

• In the practical travelling salesman problem each vertex can only be visited once

• In the practical travelling salesman problem each vertex can be visited more than once

• In the practical travelling salesman problem each edge can only be visited once

• In the practical travelling salesman problem each edge can be visited more than once

Is it possible to solve the classical travelling salesman problem for this network?

• Yes

• No

If we must start at A, which of the following is the route used for the classical travelling salesman problem?

• ABCDE

• AEDCBA

• AEDCB

• ABCDEBA

Which of the following is the correct term for the route ABCDEA?

• Hamiltonian cycle

• Eulerian cycle

• Circuit

Solve the classical travelling salesman problem by inspection. What is the length of the shortest route?

• 26

• 22

• 21

• 20

Solve the practical travelling salesman problem by inspection. What is the length of the shortest route?

• 22

• 21

• 20

• 19

Starting from A, which of the following is the shortest route for the practical travelling salesman problem?

• ABCEDEBA

• ABECEDEBA

• ABCDEBA

• ABEDEBCBA