Scroll to Top

Virtual Math Learning Center

Virtual Math Learning Center Texas A&M University Virtual Math Learning Center

Section 2.2 - Traveling Salesman Problem

Instructions

  • The first video below explains the concepts in this section.
  • This page also includes exercises that you should attempt to solve yourself. You can check your answers and watch the videos explaining how to solve the exercises.

Concepts

  • Traveling salesman problem
  • Using the brute force method to solve traveling salesman problems

If you would like to see more videos on the topic, click the following link and check the related videos.

Exercises

Directions: You should try to solve each problem first, and then click "Reveal Answer" to check your answer. You can click "Watch Video" if you need help with a problem.

1. Using the brute force method, find the least cost Hamiltonian circuit starting at B for the following graph.

A weighted triangular graph with an extra vertex in the center

BDACB or BCADB (mirror images)
Cost: 45

If you would like to see more videos on this topic, click the following link and check the related videos.

2. Using the brute force method, find the least cost Hamiltonian circuit starting at D for the following graph.

A triangular weighted graph with an extra vertex at the center

DBACD or DCABD (mirror images)
cost: 17

If you would like to see more videos on this topic, click the following link and check the related videos.

Change the section

Prev Section Next Section Return to Course