Hamiltonian Circuit

Hamiltonian Circuit Presentation

1. HAMILTONIAN CIRCUIT William Rowan Hamilton

2. Content : Hamiltonian Cycles Brief History , definition . Diference between path and cycle. Few Interesting condition. Naive Algorithm and its time complexity .

3. Hamiltonian Cycl es History : Icosian game invented by Sir. William Rowan Hamilton (1805–1865) in 1857 and sold to a London game dealer in 1859 for 25 pounds. Game Description: The corners of a regular dodecahedron are labeled with the names of cities; the task is to find a circular tour along the edges of the dodecahedron visiting each city exactly once. . Solution Model: Hamiltonian cycle; i.e. look for a cycle in the corresponding dodecahedral graph which contains each vertex exactly once. The Platonic Solid used in Icosiangame; the corresponding Hamiltonian cycle is designated by darkened edges.

4. Dodecahedron - 3 dimensional Dodecahedron-2 dimensional

5. THIS IS HAMILTONIAN CYCLE . A GRAPH CONTAINS A CYCLE WHICH HAS ALL VERTICES OF GRAPH VISITING EACH VERTEX ONLY ONCE .

6. Basic Definition : Hamiltonian Cycle: If G = (V, E) is a graph or multi-graph with |V|>=3 , we say that G has a Hamiltonian cycle if there is a cycle in G that contains every vertex in V exactly once . Necessary and Sufficient Conditions: Condition for Hamiltonian based on Linear Diophantine Equation Systems with Cycle Vector, 2009 3rd Intl. Conf. on Genetic and Evolutionary Computing . Hamiltonian Path: A Hamiltonian path is a path (and not a cycle) in G that contains each vertex. It is possible, however, for a graph to have a Hamiltonian path without having a Hamiltonian cycle. Hamiltonian path having a cycle Hamiltonian cycle .

7. Graph contains Hamiltonian path but not cycle. Example

8. Some Interesting Facts about Hamiltonian cycle : Every complete graph with more then two vertices is hamiltonian graph . Definition of complete graph: In a undirected simple graph ever y pair of a graph is connected with a unique pair. If G=(V,E) has a hamiltonian cycle then for all v ∈ V , deg(v)>=2. If a ∈ V and deg( a )=2 then two edge incident with vertex a must appear in every hamiltonian cycle. There is no know particular condition which are both necessary and sufficient.

9. So we can define the hamiltonian-cycle problem, “Does a graph G have a hamiltonian cycle?” as a formal language: “A graph contains hamiltonian cycle if it is hamiltonian graph .” So how might an algorithm decide the language HAM-CYCLE? Naive - Solution : one possible decision algorithm lists all permutations of the vertices of G and then checks each permutation to see if it is a hamiltonian path . What is the running time of this algorithm? If we use the “reasonable” encoding of a graph as its adjacency matrix, the number m of vertices in the graph is Ω √ n , where n= length of the encoding of G . There are m! possible permutations of vertices ,and therefore the running time is

10. Ω m! = Ω( √ n !)= Ω(2 √ n) , which is not O(n k )for any constant k. Thus, this naive algorithm does not run in polynomial time. In fact, the hamiltonian-cycle problem is NP-complete,

11. Verification Algorithms Anshika Pandey 2051190 1 8

12. Verification Algorithms What is verification of Algorithms? Verification algorithm: two argument algorithm A where x is ordinary string and y is a binary string called certificate. Hamiltonian Algorithm Given: Vertices in order. And a graph G such that G is a hamiltonian. Proof: Check whether it is a permutation of vertices of V, and whether each of the edge exists in the graph. We can do this in O(n^2) time where n is length of encoding of G. Thus, a proof that a hamiltonian cycle exists in a graph can be verified in polynomial time.

13. Complexity Class NP What is NP complexity class Class of language that can be verified in a polynomial time algorithm. What is P class? Problems that are solvable in polynomial time, i.e. these problems can be solved in time O(n^k) in worst-case, where k is constant. Hamiltonian Cycle is a NP complete problem. If L belongs to P then L belongs to NP. P is a subset of NP. Areas of Research It is not known whether P=NP. It is also unknown that whether NP is closed under complement i.e if L belongs to NP does it imply complement(L) belongs to NP?

14. These are four possibilities for relationship among complexity classes.

15. PSEUDO CODE Arjun Singh 2051190 2

16. Algorithm Hamiltonian(k) { do { NextVertex(R); if(x[k]==0) return ; if(k==n) p rint(x[1:n]); else Hamiltonian(k+1); } while(true); }

17. Algorithm NextVertex(k) { do { x[k]=(x[k]+1)mod(n+1); if(x[k]==0) return ; if(G[k[k-1],x[k] !=0) { for j=1 to k-1 do if(x[j] == x[k]) break; if(j==k) if(k<n or (k==n) && G[x[n],x[1]] !=0 return ; } while(ture); }

18. Traversing Saurav Kr Gupta 2051190 92

19. Graph has Hamiltonian Cycles: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 1 1 -> 2 -> 6 -> 5 -> 4 -> 3 -> 1 1 -> 6 -> 2 -> 5 -> 4 -> 3 -> 1 … 2 -> 3 -> 4 -> 5 -> 6 -> 1 -> 2

20. Pendant Vertices Articulation Point

21. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Adjacency Matrix X 1 2 3 4 5