all example 2

The previous example demonstrates a TSP that involves a complete graph ke Of all graphs with vertices and no multiple edges, the complete graph Khas the most edges. Consequently, of all graphs with N vertices and no multiple edges, the complete graph ks will have the most Hamilton circuits How many possible Hamilton circuits (including mirror image circuits) are there in the complete ks graph to the right? D The following TSPs involve graphs with 5 vertices that are not complete graphs. Example 2 Solve the TSP for persons based at vertex D and vertex E. Make a list of all possible Hamilton circuits starting first at vertex D then at vertex E. How many possible Hamilton circuits (including mirror image circuits) are there in this graph starting from vertex D? From vertex E? Now complete the table below. A. 170 B Possible Routes and Distances Starting a Vertex D Total Distance Mirror Image Circuit 220 C 220 Possible Routes and Distances Starting a Vertex E Circuit Total Distance Mirror Image 130 - D 130 and b. What are the optimal routes starting at vertex D? What is the distance of these routes? and c. What are the optimal routes starting at vertex E? What is the distance of these routes? d. Do the solutions change for persons based at different vertices? Example 3. Solve the TSP for a person based at vertex Y. How many possible milion circuits (including mirror image circuits) are there in this graph starting from vertex Y? Possible Routes and Distances Starting a Vertex Y Circuit Total Distance Mirror Image b. What are the optimal routes starting at vertex Y? What is the distance of these routes? c. Will the solution change for a person based at another vertex