In the class discussions, we have talked about how the traveling salesperson (TSP) problem and how it can be modeled using graphs. We also looked at finding a minimum length in a graph as well as Hamiltonian cycles.
Graphs, graph algorithms and methods, and graph theory are integral to IT and computer science applications and coding. For this assignment, write a two- to three-page paper that responds to each of the following questions:
1. What is a Hamiltonian cycle?
2. What is a Euler cycle?
3. What is a minimum length Hamiltonian cycle?
4. Given a graph with n edges, what is the time complexity of finding a Euler path? Is this a polynomial time algorithm? Explain and show all work and the graph. Hint: Include the algorithm and pseudocode.
5. Given a graph with n edges, can one find a minimum Hamiltonian cycle (TSP) in polynomial time? Has anyone ever proved that a polynomial time algorithm does not exist for this problem? Explain your answers and show the graph. Hint: Consider NP complete problems.
6. Offer one example of an IT or computer application that can be modeled as the TSP problem. This must be at least one paragraph.