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.