Question

5) Consider the following weighted graph G below. Lima 91 Mansted зе 96 63 50 so Newark A) Find a Hamilton Circuit with Columbus as the start and finish. B) Do the same thing except suppose you start and end in Newark. What happens?

Answer 1

We will use Nearest Neighbor Algorithm to find a Hamilton circuit

Start: Start from any vertex A.
First Step: Travel along the edge of minimal weight joined to A.
Middle Step: From a given vertex select the edge of minimal weight among all of the edges joined to vertices that have not been visited yet.

Last Step: Return to starting point A.

A)

From Columbus, the nearest unvisited city is Newark with distance 40. So, the next visited city is Newark.
From Newark, the nearest unvisited city is Mansfield with distance 55. So, the next visited city is Mansfield.
From Mansfield, the nearest unvisited city is Marion with distance 38. So, the next visited city is Marion.
From Marion, the nearest unvisited city is Lima with distance 54. So, the next visited city is Lima.
From Lima, we will return to first vertex Columbus with distance 96.
So, the Hamilton circuit is Columbus, Newark, Mansfield, Marion, Lima, Columbus with distance = 40 + 55 + 38 + 54 + 96 = 283

B)
From Newark, the nearest unvisited city is Columbus with distance 40. So, the next visited city is Columbus.
From Columbus, the nearest unvisited city is Marion with distance 50. So, the next visited city is Marion.
From Marion, the nearest unvisited city is Mansfield with distance 38. So, the next visited city is Mansfield.
From Mansfield, the nearest unvisited city is Lima with distance 91. So, the next visited city is Lima.
From Lima, we will return to first vertex Newark with distance 116.
So, the Hamilton circuit is Newark, Columbus, Marion, Mansfield, Lima, Newark with distance = 40 + 50 + 38 + 91 + 116 = 335