3 Algorithmic Problems with Graphs, Eulerian Path, Hamiltonian Cycle and Travel Salesman

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.

Note. Your calculations and work must be shown.

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Problem 6
Among the practical applications that can be modeled as TSP problem it can be highlighted the computer wiring problem. This can be formulated in the following way:
For an interface formed by modules (each of these having several pins), it is needed to be known the minimized total wire length such that to avoid signal cross-talk and to improve ease. A given subset of pins must be interconnected and the position of each module is already known.
Now we try to model this as TSP instance. It is considered the subset of pins that must be interconnected being P. It is known the distance between two pins i and j as being cij and H – the complete graph formed on the nodes from the set P and weights cij. Since the wiring path must pass through each node exactly one, the problem of minimizing the wire length is identical with finding the minimum Hamiltonian Path on the provided graph....