Euler’s And Hamilton’s Path Through One-Dimension Space

Аннотация

This article will present a technique for traversing a graph. Several questions arise here. For example, can we walk along the edges of a graph starting from a vertex and returning to it by visiting each edge of the graph exactly once? Similarly, can we walk along the edges of a graph starting from a vertex and returning to it while visiting each vertex of the graph exactly once? As can be seen, both questions are identical, but what is important is to consider two circuits that answer the above questions, namely the Euler circuit and the Hamilton circuit. Solving the Hamilton circuit for most graphs is very difficult. In this section, we will examine these questions and discuss the difficulty of solving them. Keywords: Graph, Euler’s Path, Hamilton’s Paths, Analysis of path circuit. Introduction: To better understand the path, we must first have a brief introduction to graphs first. Graphs are discrete structures consisting of vertices and the edges that connect these vertices. There are different types of graphs, depending on whether the edges are directed, whether multiple edges can connect a pair of vertices, and whether the graphs are cyclic. Traversing on the graph edges and crossing the vertices a path are created. Given the importance of these two topics, Euler and Hamilton paths are one of the fundamental concepts in graph theory, a branch of mathematics that European International Journal of Multidisciplinary Research 13 https://eipublication.com/index.php/eijmrms and Management Studies European International Journal of Multidisciplinary Research and Management Studies studies the properties and applications of graphs. We The path ∝ = (v0, v1, v2, . . . , , vn – 1, vn) is closed if v0 will give examples to show how graphs can be used as = vn, i.e. its origin (∝) is equal to the limit (∝). A path is a model in the context of using graph models to called a circuit if the path is closed and all vertices except determine whether it is possible to walk all the streets v0 = vn are distinct. A circuit of length k is called a k- of a city without going down a street twice, or whether circuit. a circuit can be implemented on a flat circuit domain. Note: A circuit in a graph G must have length equal to Graphs with weights assigned to their edges can be or greater than three [8]. used to solve problems such as finding the shortest In general, as it is briefly stated in [6], If u and v are path between two cities in a network. We will also vertices in the graph G, then the distance between u and examine the complexity of Euler and Hamilton paths. v is represented by d(u, v). Now we start discussion on Euler and Hamilton’ path. Euler’s Paths and Circuits: Now we are going to show Paths: Before we consider the Euler and Hamilton how Euler path look like, for a better understanding we paths, let us explain the path itself. Suppose we have a are going to describe with a historical representation of city, we know that a city has a certain area, we consider the path. the vertices of this area as cities and the edges as Here as it is mentioned in [6], the subject of graph roads, a path is a distance that starts in a city, passes theory began in the year 1736 when the great through several cities, and ends in a city [3]. mathematician Leonhard Euler published a paper giving In [1] a path ∝ in a graph G, with origin v0 and endpoint the solution to its puzzle i.e. Konigsberg Bridges. vn, is an alternating sequence of n + 1 vertices and n Konigsberg Bridges: Here we consider a city, which is edges of the form the city of Konigsberg, which in the 18th century in East v0, e1, v1, e2, v2. . . en – 1, vn – 1, en, vn Prussia consisted of two islands and seven bridges. Here Where each edge ei is located at the vertices vi – 1 and a question arises as follows: a person wants to walk vi. And the n edges of a graph are called path lengths. through the city and, starting from any point in the city, cross all seven bridges but do not cross any bridge twice We show the path ∝ by a sequence of its edges ∝ = (e1, and reach another point in the city? The people of e2. . . en – 1, en ) or by a sequence of its vertices ∝ = Konigsberg wrote a letter to the famous Swiss (v0, v1, v2, . . . , , vn – 1, vn) [2]. mathematician Euler about this question. In 1376, Euler Theorem: There is a path from a vertex u to a vertex v proved that such a walk is impossible. if and only if there exists a simple path from u to v [4]. He replaced the islands and the two sides of the river For more discussion, we describe what a simple path with points and the bridges with curves and showed it is. in the figure below. Simple path: A path ∝ = (v0, v1, v2, . . . , , vn – 1, vn) is simple if all its vertices are distinct. Or a path is called simple if none of its edges is repeated [1, 6,7 ]. Figure: Graphical representation of Euler Path European International Journal of Multidisciplinary Research 14 https://eipublication.com/index.php/eijmrms and Management Stud