Graphing Applications and the TSP

Name:

Institution:

Graphing Applications and the TSP

Question 1

A Hamiltonian cycle is a closed loop within a graph that visits all its vertices exactly once. An example of the Hamiltonian cycle is the Travelling salesman problem. The solution to the minimum length of a Hamiltonian cycle is an NP complete problem that cannot be computed in polynomial time. This means that the minimum possible path cannot be computed by a deterministic machine. When completing a Hamiltonian cycle, one has to make sure that there are only two edges getting in and out of a vertex. In addition one has to ensure that there are no sub-cycles in the cycle. In a Hamiltonian cycle with n vertices, the number of different cycles that can be completed is (n-1)! /2 in a complete undirected graph and (n-1)! In a complete directed graph (Narasimhan, 2009).

Question 2

A Euler cycle is a path that passes through all the edges of a graph exactly once. It usually starts and ends at the same vertex. For one to construct a Euler cycle all the vertices in the graph must have an even degree. Therefore, one can conclude that any graph with all vertices of an even degree connected is a Euler cycle. Unlike the Hamiltonian cycle, the Euler cycle can be computed in polynomial time. The Euler cycle can be constructed using the Fleury’s or Hierholzer’s algorithm.

Question 3

The minimum length of a Hamiltonian cycle is the shortest path that can visit all the vertices of a graph exactly once. To evaluate it one needs to compare all possible routes through the cycle and find the one with least weight. The time complexity of finding the minimum length of a Hamiltonian cycle is exponential and cannot be accomplished in polynomial time. This time complexity makes it hard for one to evaluate it in a deterministic machine, thereby, making it a NP complete problem (Narasimhan, 2009).

Question 4

The determination of a Euler cycle is of polynomial time complexity. It can be evaluated in O(V+E) time where V is the number of vertices whereas E is the number of edges in the graph. A Euler cycle can be determined in polynomial time since it has only two vertices with an odd degree (the start and end vertices) (shown Fig.1). (Guckin, 1989).

[pic]

Fig.1:Euler cycle

Fleury’s Euler cycle algorithm

• Ensure that the graph has 2 odd vertices or none.

• In case there are no odd vertices one can start anywhere. However, if there are them start at one of those points.

• All edges must be followed sequentially. Where one encounters a bridge and non-bridge the latter is the optimal choice.

• Stop when all edges are covered.

Pseudo code

#cycle is a global array Find_euler_cycle Cyclepos = 0 Find_cycle(vertex 1)

# visited and nextvertex is a local array
# the trail will be established in reverse find_cycle(vertex x) if vertex x does not have neighbours then cycle(cyclepos) = vertex x cyclepos = cyclepos + 1 else while (vertex x has neighbours) select a random neighbour vertex y of vertex x remove_edges(vertex y, vertex x) find_cycle(vertex y) cycle(cyclepos) = vertex x cyclepos = cyclepos+ 1.

The algorithms above run in O (V+E) time, thus, can be completed in polynomial time. However, larger graphs may result in the overflowing of the run time stack. The above algorithm can handle multiple edges and self loops in a graph.

Question 5

The TSP is a combinatorial optimization problem that cannot be solve in a deterministic computer. Actually, the problem cannot be solved in polynomial time. This is because as the number of cities increases the running time for the solution increases exponentially. In this regards, the TSP can be concluded to be a NP-complete problem. There are no existing polynomial time solutions that exist for any NP complete problem. However, there is no proof to show that such a problem cannot be solved in polynomial time (Narasimhan, 2009).

An NP problem can be solved by an indeterministic computer in polynomial time. The machine is able to make a choice of the right decision among a given set of choices. However, NP-complete problems cannot be solved in polynomial time but through exhaustive solutions. A problem is said to be NP-complete if it is in NP and if it is reducible in polynomial time. The TSP is a decision and optimisation problem. This makes it harder for the computer as it has to compute the decision and optimisation for the route with minimum weight (Ferreira & Pardalos,1996).

[pic]

Fig. 2: Travelling Salesman problem

Fig.2 shows a simple TSP with 4 cities. The native solution for the optimal distance requires one to select a starting and ending point. Thereafter, one should calculate all the (n-1)! permutations for all the destinations. The cost of each permutation and the minimum cost permutation should be considered during the process. The last step will involve one returning the permutation with the lowest cost. The time complexity of this problem is O(n!).In a computer this problem can be solved through dynamic programming where one should develop recursive solutions in terms of sub-problems. Each set of a given size n the subsets considered will be n-2 each with the size n-1 such that they shall not have the nth term. From the recursive problems the solution will have O (n*2n) sub-problems that can be solved in linear time. The time complexity in this case is less than O(n!) but still has exponential space and time requirements.

[pic]

Fig.3: TSP problem representation with cities a- e.

Fig.3 shows a TSP that seeks to find the optimal distance from city a to e. Fig.4 shows a tree solution to the sales man problem.However, there is a limitation in the number of levels the the solution will have. Additionally one should also note that some of the chains that will show the route of travel may generate duplicity at various level thereby limiting a solution. As the number of vertices in the problem increases, the tree becomes harder to compute and interprate. (Lawler,1985).

[pic]

Fig.4: Solution tree for a TSP instance

Question 6

The TSP is a hard problem that would solve numerous challenges if an optimal solution were found. In this case a solution that could be completed in polynomial time. The fields of transport, delivery and routing would benefit greatly from this solution. One of its applications would be in postal delivery system, where the system would assign the postman with addresses for delivery, thereby, optimizing on delivery time.

If the TSP could evaluate the shortest routes in polynomial time, then it would save alot of time for postmasters and parcel delivery companies.

References

Ferreira, A., & Pardalos, P. M. (1996). Solving combinatorial optimization problems in parallel:

Methods and techniques. Berlin: Springer.

Guckin, A., Consortium for Mathematics and Its Applications (U.S.), & Faculty Advancement in

Mathematics Project. (1989). Euler circuits. Arlington, Mass.: COMAP

Lawler, E. L. (1985). The Traveling salesman problem: A guided tour of combinatorial optimization.

Chichester [West Sussex: Wiley.

Narasimhan, G. (2009). A note on the Hamiltonian circuit problem on directed path graphs. Madison,

Wis: University of Wisconsin-Madison, Computer Sciences Dept.