# Efficient Algorithm to Determine Whether a given

Graph is Hamiltonian or not with all Possible Paths Narendra Pratap Singh ? , Ramu Agrawal ? & Indra Paliwal ? Abstract -Given a Graph G (V, E), We Consider the problem of deciding whether G is Hamiltonian, that is-whether or Not there is a simple cycle in E spanning all vertices in V. [1] However to Verify that the given cycle is Hamiltonian by checking whether it is permutation of the vertices of V and whether each of the consecutives edges along the cycle actually exists in the Graph. This Verification Algorithm can certainly be implemented to run in O (n 2 ) time, where n is the length of the encoding of G [2]. But to predict in Advance that the Graph has Hamiltonian Cycle or not was still Exponential before this Algorithm. This Problem is known to be NP-Complete hence cannot be solved in Polynomial time in |V| unless P=NP. However till today there was no known Criterion we can apply to determine the existence Hamiltonian Circuit in General [3] 


# Introduction

amiltonian Problem is Decision Problem in which G (V, E) should be traversed from any one vertex to same vertex without repeating any vertex again (means, Vertex should be traverse exactly once).

We look for n long sequence of vertices v 0 , v 1 , v 2 , .?., v n-1 visit all vertices in v such that
n i ? ? 0 , (vi, v(i+1)mod n) E ? , along with the element of Adjacency Matrix Ai, j= 1,if ) , ( j i E ? ?
, 0, otherwise. From the general prediction as prescribed in literature that Hamiltonian Cycle exists if and only if there is an nlong Author ? ? ? : Department of Computer Science, BSA College of Engineering and Technology, Mathura, U.P, India. E-mail ? : narendrapratapbsa@gmail.com E-mail ? : ramuagrawalbsa@gmail.com E-mail ? : indrapaliwal@gmail.com tour that cover all the vertices and returns to the standing point.

Scientist around the globe deduced the Method based on the number of edges and degrees of graph, some for planarity and some for connected but they all failed for a general graph and was not sufficient. It follows the CNF-satisfiability also [4].

But we put through the above statement from the mathematical and logical point of view.

By this algorithm, now the scientist will have reasonable condition to determine the Hamiltonian Circuit in Advance without traversing it vertex to vertex manually on the paper.

Till today this problem which spurred the computer scientist around the globe to be able to draw an Algorithm which Culminate the possibilities, the usage of global information was shown to speed up the process: however it has cost in communication and complexity of individual agent. Now in our Algorithm there is no foundation for an undirected, directed, planarity, colorability, and connectedness of a graph, it can be applied to the all types of graphs.

Rest of the paper is organized as follows. Section2 present the related work. The proposed method algorithm has been described in section3. In section4, experimental results and sample run have been presented and paper is concluded in section5.


# II.


# Related work

Since, its (Hamiltonian Cycle Problem) origin, by famous Irish Mathematician Sir William Rowan Hamilton, 1859, was still unsolved. There was no known criterion we could apply to determine the existence of Hamiltonian circuit in general. A circuit is a connected graph G is said to be Hamiltonian if it includes every vertex of G. Hence a Hamiltonian Circuit in a Graph of n vertices cost of exactly n edges. Obviously, not every connected Graph has Hamiltonian Circuit. For example, neither of the Graph shown in figures (2.1 and 2.2) and has a Hamiltonian circuit. This raise the Question: What is the necessary and sufficient condition for a connected Graph G to have Hamiltonian Circuit? [5] Also, No known Characterization to determine Hamiltonian graph in any given Graph G has been found [6].
( D D D D ) C 2012

# Year

However several Scientist has proposed several methods on the basis of degree and edges with the reference to any specific graph (like connected, planarity, etc.). But they had not found full success with necessary condition to predict Hamiltonian cycle in advance for every Graph. Most of works has been presented before the 1975. Hence there was no programming based algorithmic approach had been considered? Some famous works are as follows:

? Every Graph G with 3 ? n vertices and minimum degree at least n\2 has a Hamiltonian Cycle [7] (Dirac 1956).

[Note that this theorem bound prediction within limit of The following theorem characterizes all Hamiltonian Sequences.
3 ? n .] ? Every Graph G with |G| 3 ? and K(G) ? ?(G)
? (Chvatal 1972), An integer Sequence (a 1 , ?., a n ) such that 0? a 1 ???? a n <n and n?3 is

Hamiltonian if and only if the following holds for every i<n/2: [11]   ? An integer sequence (a1, ?an) such that n ? 2 and 0 ?a1???? an < n is path Hamiltonian if and
a i ? i ? a n-1 ? n-i.only if every i ? n/2 is such thata i < i ? a n+i-2 ? n-1
Hamiltonian Cycle in the square of a graph For k=1, this is preciselyDirac's theorem the case k=2 had already been conjecture by Posa in 1963 and was proved for large n by kamlos, Sarojy & Szemerdi, 1996. [13] Beyond the above given thesis, the age comes to programming and computer scientist developed several algorithms in the same context but did not get succeed to make sure exact prediction for a graph to be Hamiltonian or not. These are given as follows:
? (Fleischner 1974), if G is a 2-Connected
? 1. Vertex ant walk (VAW) has the Hamiltonian cycles as its limit cycle; however we do know if those are the only limit cycles of the process which are longer than the n variables.


# A probabilistic Version of VAW rule does not

determine the next neighbor specifically, but assigns each neighbor a probability according to its current (µ, t) mark (e.g) the probability of jumping from u to v be Prob(u ? v) =(1/(1+µ(v)))/(? w? N(u) (1/(1+µ(w))

Where, clearly, ? w? N(u) prob (u ? w) =1N(u) stands for the sets of vertices v?V such that (u, v) ? ?

). In such a semi-Random process faster, (In recognizing a Hamiltonian Graph), on the average, or lower than the deterministic one? [Note that, the prediction in above method is probabilistic, means of having some amount of Uncertainty.] ? Solving the Hamiltonian cycle Problem using symbolic determinant by V.Ejov ? Bitonic Euclidean traveling-salesman problem [2] The Euclidean traveling-salesman problem is the problem of determining the shortest closed 
©

# The proposed method

In this section, we will present our original approach to determine all Hamiltonian paths for a Given Graph G. G(V, E) is the ordered pair consists two sets, V for vertices(v1, v2, v3, ?., vn) and E for edges (e1, e2, Algorithm (for First Basic method*):

1. Draw the Adjacency matrix ( Inputting graph):

Let take adjacency matrix for any undirected graph without parallel edges or loops. Adjacency matrix for directed/undirected having loops and parallel edges. 
![graph then G 2 has a Hamiltonian Graph.[11] ? (Seymour 1974), let G be a Graph of order n ?3 , and k be positive integer. If G has a minimum degree ? (G) ? (k / k+1)*(n), there G has Hamiltonian Cycle H such that H k ? G.[12].](image-2.png "")
![2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XII Issue XIV Version I Tour that connects a given set of n points in the plane Figure 2.1(a) shows the solution to a 7-point problem. The general problem is NP-complete, and its solution is therefore believed to require more than polynomial time Figure 15.9: Seven points in the plane, shown on a unit grid. (a) The shortest closed tour, with Length approximately 24.89. This tour is not bitonic. (b) The shortest bitonic tour for the same set of points. Its length is approximately 25.58. J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the leftmost point, go strictly left to right to the rightmost point, and then go strictly right to left back to the starting point. Figure (b) shows the shortest bitonic tour of the same 7 points. In this case, a polynomial-time algorithm is possible. Describe an O(n 2 )-time algorithm for determining an optimal bitonic tour. You may assume That no. two points have the same x-coordinate. (Hint: Scan left to right, maintaining optimal Possibilities for the two parts of the tour.) (a) (b) But, we have introduced a Newer Algorithm which over comes all the Hurdles suggested in above given recent research, by applying logical and mathematical operations. Hence it proves itself as a sufficient condition for a Graph to be Hamiltonian. III.](image-3.png "Year")
![e3, ?., en)[or ek?E, k N ? . the vertices are the basic nodes types which stores the information of Graph, itself a mathematical structures and finds its application in many areas of interest in which problem need to solved using Computers. In case of Hamiltonian, e.g., Indian Railways may need to expand its tracking belongs to each station in such a manner that the train running on this must visit each station exactly once by starting from any station and reached at the same. It represented in the Data Structures. These representations commonly used Adjacency Matrix, Adjacency list and Multi-list representation. Firstly, we will use these for Adjacency Matrix A ij = 1, if â??" ? ? vi e ( v j ), A ij = 0, otherwise, takes O(n 2 ) space to represent graph with n vertices, even for Sparse Graph.](image-4.png "")
31![Fig. 3.1 : n*n-matrix for undirected graph](image-5.png "Fig. 3 . 1 :")
3233![Fig. 3.2 : n*n matrix for graph having loop and parallel edges](image-6.png "Fig. 3 . 2 :Fig. 3 . 3 :")
. For its Exponential time We can Refer to theorems: -Vertex Cover problem is polynomially transformable to the Hamiltonian circuit Problem for Directed graphs, hence the Hamiltonian Circuit problem for Directed Graph is NP-Complete and the Hamiltonian Circuit Problem for Directed Graph is Polynomialy transformable to Hamiltonian Cycle Problem for Undirected Graph, hence the Hamiltonian Cycle Problem for undirected Graph is NP-complete[4]. Note that these derivations are based on the CNF-Satisfiability.Through this Paper we have introduced a
			© 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology
			© 2012 Global Journals Inc. (US)
		
		
			

## Year

Do the same operation for all the sequences, we get P 1 , P 2 , P 3 ,?,, P n .


## B. Then we apply logical OR(||) operator between all

the path values. *fortunately this algorithm provides sufficient conditions for a Graph to be Hamiltonian and also print all the possible paths but Unfortunately takes more time for large Graphs, so we were in search for next Algorithms which take less time than this, therefore we developed second Algorithm which facilitate all the requirements.

We prepare second Algorithm using the concept of Graph theory, means of having linked list, structures and few pointers.  

If all nodes are reachable from A, than flights may seek to any Airport, Note that this step will make just one comparison and proceed to next one (say, B).

On the next point, it will decide to move on the next Airport Except the later traversed Airport (A). If this node is reachable to another then it will move on by making just single Comparison again. This sequence of comparison at one time and moving on the next node will remain next Node will remain continue till it did not reach at the initial vertex (Airport).


## T (n ) = 1+1+1+??+1

(n times) T (n) = n T (n) For Worst Case:

In the worst case, the Airplane will choose the move to specific Airport by making (n-1) comparison for itself; therefore the airplane at the next step will decide the next move to further proceeding after making n-1 comparison. The routine will remain till the Airplane did not reach at the initial Airport (or Standing point).

= n (n-1)! Hence, this Algorithm runs near to polynomial for small vertices sets.

V.


## Conclusion

Our method exploits the ways to find Hamiltonian Circuit using Sequential and predicate logic and opens up opportunities for future researcher interested in this problem succinctly in much advance way. However our method has successfully find out all possible paths but still working near to polynomial not exactly polynomial, but it opens opportunities to think about this problem by applying advance methods of predicate calculus to find out all possible paths in polynomial time.
			
			

				


* 
	
		An Ant Inspired Heuristic for Recognizing Hamiltonian Graphs
		
			AIsrael
		
		
			AlfredMWagner
		
		
			Bruckestein
		
		
			
		
	




* 
	
		
			THCormen
		
		
			CELeiserson
		
		
			RLRivest
		
		Introduction to Algorithms
				Cambridge, MA
		
			MIT Press
			2009
		
	




* 
	
		Graph Theory with Application to Engineering and Computer Science
		
			NarsinghDeo
		
		
			20007
			Prentice Hall India
			
		
	




* 
	
		The Design and Analysis of Computer Algorithms
		
			AlfredVAho
		
		
			JohnEHopcroft
		
		
			JeffereyDUlman
		
		
			2008
			
		
	




* 
	
		
		
			EllisHorowitz
		
		
			SatajSahni
		
		
			SanguthevarRajshekharan
		
		
			2009
		
	




* 
	
		
			ReinhardDiestel
		
		Graph Theory Electronic edition
				New york
		
			Springer-verlog
			2000. 2000
			
		
	




* 
	
		External Graph Theory
		
			BBollobas
		
		
			1978
			Academic Press
		
	




* 
	
		
			RHalin
		
		Graph theorie, Wissen Schatliche Buchgessellschaft
				
			1980
		
	




* 
	
		
		
			CThomassen
		
	
	
		J.Graph
		
			7
			
			1983
		
	




* 
	
		
			JA S RBondy & U
		
		
			Murthy
		
		Graph Theory With Applications
				Macvmillan
		
			1976
		
	




* 
	
		
		
			JCombinFleischner
		
		
			Theory
		
		
			1991
			
		
	




* 
	
		
		
			PD PSeymour ; T
		
		
			VCMc Donough
		
		
			Marron
		
		
			1974
			OD) Combinatorics, Camridge University Press
			3
		
	




* 
	
		
			JKomlos
		
		
			GNSarkozy
		
		
			&ESzemredi
		
		Random Structures and Algorithms
				
			1976