Discrete math – GRAPH APPLICATIONS AND THE TRAVELING SALESPERSON

Learning Goal: I’m working on a discrete math exercise and need an explanation and answer to help me learn.

Graphs, graph algorithms and methods, and graph theory are integral to IT and computer science applications and coding. For this assignment, write a 3–4 page paper that responds to each of the following questions:

1. Define what it means for a graph to have an Euler cycle.
2. Provide a real-world example that can be modeled by a graph that has an Euler cycle and explain how the Euler cycle can be found.
3. Given a graph with n edges, what is the time complexity of finding a Euler path? Is this a polynomial time algorithm?
4. Define what it means for a graph to have a Hamiltonian cycle and minimum-length Hamiltonian cycle.
5. Provide a real-world example that can be modeled by a graph that has a Hamiltonian cycle (TSP) and explain how a minimum-length Hamiltonian cycle can be found.
6. 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.

Your calculations and work must be shown. Include references to any resources you use to complete the assignment.

Review the Graph Applications and the Traveling Sales Person Scoring Guide to understand how the assignment will be graded.