Consider the undirected complete graph having the following cost matrix:

1 2 3 4 5 6

X	3	9	8	7	5	1
3	X	8	1	11	7	2
9	8	X	6	4	7	3
8	1	6	X	9	8	4
7	11	4	9	X	10	5
5	7	7	8	10	X	6

a) The Nearest Neighbor Method is a greedy scheme that works on a complete graph as follows:The Traveling Salesman Problem is to find the cheapest possible tour in the graph. That is, a single simple cycle that starts at node 1, visits every node exactly once, and returns to node 1.

Start at node 1

For steps := 1 to n-1

Travel on the cheapest link from the present node to an unvisited node

3. Travel on the link from the last node to node 1

Perform this method to obtain a solution for the compete graph above and give its total cost.

b) Using any other method, find a different tour. Does it have a cheaper total cost?

c) "Starting the Nearest Neighbor Method algorithm from a different node may result in a solution having a different cost." True or False? Why?