Abstract
A cycle passing through all the vertices exactly once in a graph is a Hamiltonian cycle (HC). In the field of network system, HC plays a vital role as it covers all the vertices in the system. If uncertainty exists on the vertices and edges, then that can be solved by considering fuzzy Hamiltonian cycle. Further, if indeterminacy also exist, then that issue can be dealt efficiently by having neutrosophic Hamiltonian cycle. In computer science applications, objects may not be a crisp one as it has uncertainty and indeterminacy in nature. Hence, new algorithms have been designed to find interval neutrosophic Hamiltonian cycle using adjacency matrix and the minimum degree of a vertex. This chapter also applied the proposed concept in a network system.
TopIntroduction
The study of graphs is called graph theory where the realtion between the objects designed by the mathematical structures. A graph is made up of vertices and they are connected by the edges. Especially while solving shortest path problems, some of the concepts needed to be takec care namely walk (vertices and edges may be repaeated, open or closed) trail (vertices may be repeated but edges cannot be repeated, open), circuit (vertices may be repeated but edges cannot be repeated, closed), Path (both vertices and edges cannot be repeated, open) and cycle both vertices and edges cannot be repeated, closed). A cycle which passing through all the vertices in a network is a Hamilton cycle and the path is a Hamilton path (Hamilton, 1932).
A graph with HC is called a Hamiltonian graph. Every HC has Hamiltonian path (HP) and the cntraray is not inevitably true. The studies on HC and HP have been inspired by real life applications and the complexity issues (Rahman and Kaykobad, 2005). Identifying the existence of HC is a NP-complete problem and hence it’s a slow process for huge graphs (Csehi and Toth, 2011). When there is impreciseness on the vertices and edges of a graph then the crisp graph fails and at this junction fuzzy graph can be applied to deal the uncertainty. The notion of connectivity performing an essential role in theory and as well as applications of fuzzy graphs (FGs). There are many applications in current technology namely information theory, intelligent systems, medical analysis, neural network and cluster analysis (Nirmala and Vijaya, 2012).
(Broumi, et al., 2016) Graph theory is a branch of combinatorics and applied mathematics and has been applied in various fields’ namely number theory, topology, algebra, geometry, computer science and optimization. If there is indeterminacy exist in the relation between the vertices then FG fails. For this aspiration, Smarandache described neutrosophic graphs (NGs). Then single valued neutrosophic graphs (SVNGs) and interval valued neutrosophic graphs (IVNGs) have been introduced as a generalization of fuzzy and neutrosophic graphs. Also described degree, neighborhood degree of a vertex for SVNG. Smarandache, 2016 introduced IVNGs and described about adjacency vertices and matrices of IVNGs and degree of the vertices. Fuzzy set (Zadeh, 1965) is a concept introduced for handling uncertainty of the real world problems. It generalization called intuitionistic fuzzy set (Atanassov, 1986) deal membership as well as non membership of the elements of the set.
Fuzzy graph is capable of solving network problems when uncertainty exists on the vertices and edges (Rosenfeld, 1975). But indeterminacy can be handled by both fuzzy and intuitionistic fuzzy set and hence neutrosophic set (Smarandache, 2002) to deal indeterminacy of the data, vertices and edges. (Dogrusoz and Krishnamoorthy, 2015) Determining or identifying the Hamiltonian cycle in network or a problem is called Hamiltonian cycle problem (HCP). It has many applications if various fields especially in computer vision in formatting the object characterized by group of points. The relations in the fuzzy graphs are symmetric (Vanadhi et al., 2015).
If the number of vertices and edges are growing then identifying the Hamiltonian cycle will become a tedious process and hence simple algorithms are needed to be introduced. Adjacent matrices are useful to identify edge between the vertices easily and quickly. Network topologies can be designed using the notion of graphs namely traveling salesman problem, resources networking and designing of database. This causes the new algorithms and new theorems.
A graph is diagrammatic representation of the links (edges) between the objects (vertices) of the set. Adjacent vertices are connected by an edge. In a route map cities are the vertices and the roads connecting the cities are edges. Graph theory provides consolidated direction for specific problems and algorithms called graph algorithms can give the best solution (Nagoorgani and Latha, 2016).
Key Terms in this Chapter
Fuzzy Hamiltonian Cycle: In a fuzzy graph G, if a fuzzy cycle covers all the vertices exactly once then G is called Fuzzy.
Neutrosophic Hamiltonian Path: A neutrosophic path which covers all the vertices exactly once is called Neutrosophic Hamiltonian path.
Hamiltonian Cycle: Hamiltonian cycle is a cycle which visits each and every node exactly once.
Interval Neutrosophic Hamiltonian Cycle: In interval neutrosophic graph G, if the interval neutrosophic cycle covers all the vertices exactly once then G is called interval neutrosophic Hamiltonian cycle.
Adjacency Matrix: Is a connection matrix and represents the relation between the vertices whether connected or not.
Path: A path in a graph is a finite or infinite sequence of distinct vertices.
Neutrosophic Hamiltonian Cycle: In a neutrosophic graph G, if a neutrosophic cycle covers all the vertices exactly once then G is called neutrosophic Hamiltonian cycle.
Hamiltonian Path: A path which covers all the vertices exactly once is called a Hamiltonian path.
Cycle in a Network: At least three vertices are connected in a closed chain.
Degree of a Vertex: The number of vertices incident to the vertex is called degree of a vertex.