Traveling Salesperson Problem

What is the shortest route using Nearest Neighbor Algorithm starting with vertex A?

• 63

• 58

• 55

• 52

Find a Hamilton circuit from D using the Nearest Neighbor Algorithm.

• DAEBCD

• DBEACD

• DABECD

• DCABED

Using the Brute Force Algorithm, find the optimal route starting at A.

• ACDBA

• ABCDA

• ABDCA

• ACBDA

What is the weight of the circuit ABDCA?

• 165

• 155

• 160

• 145

How many possible Hamiltonian Circuits are in the graph?

• 120

• 24

• 50

• 68

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

• Hamiltonian circuit

• Eulerian circuit

• Hamiltonian path

• Eulerian path

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

• True

• False

Using the Nearest Neighbor Algorithm, find the optimal route starting at A.

• ACDBA

• ABCDA

• ADBCA

• ACBDA

What is the weight of the Hamiltonian circuit starting at A and using Nearest Neighbor Algorithm?

• 180

• 190

• 200

• 170

How many Hamiltonian Circuits can you find in this graph?

• 4

• 6

• 8

• 10