# Asymptotically Effective Method to Explore Euler Path in a Graph

Authors: Muhammad Fahad; Sikandar Ali; Mukhtaj Khan; Mujtaba Husnain; Zeeshan Shafi; Ali Samad
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Euler path is one of the most interesting and widely discussed topics in graph theory. An Euler path (or Euler trail) is a path that visits every edge of a graph exactly once. Similarly, an Euler circuit (or Euler cycle) is an Euler trail that starts and ends on the same node of a graph. A graph having Euler path is called Euler graph. While tracing Euler graph, one may halt at arbitrary nodes while some of its edges left unvisited. In this paper, we have proposed some precautionary steps that should be considered in exploring a deadlock-free Euler path, i.e., without being halted at any node. Simulation results show that our proposed approach improves the process of exploring the Euler path in an undirected connected graph without interruption. Furthermore, our proposed algorithm is complete for all types of undirected Eulerian graphs. The paper concludes with the proofs of the correctness of proposed algorithm and its computation complexity.


---

## Body

## 1. Introduction

Graph is one of the discrete structures that consists of nodes (or nodes) and edges that connect these nodes. In order to avoid confusion, we will use the term node in the rest of paper. Generally, the graphs may be either directed or undirected [1]. Mathematically a graph can be defined as G = (V, E) which consists of V, a nonempty set of nodes and E, and a set of edges [2, 3]. Each edge has either two nodes v and w, associated with it, called its endpoints. The edges are unordered pairs of nodes in undirected graphs, also represented as (v, w). In directed graphs, the edges are ordered pairs (v, w) of nodes, where v is the tail and w is the head of the edge. A path in a graph is a finite or infinite sequence of edges which connect a sequence of nodes which, by most definitions, are all distinct from one another [2, 3]. These paths can be used in designing the framework of a number of graph-related issues. For example, the graph model can be used in determining whether a communication link is established among different computers in a network or not. Furthermore, a number of issues such as planning efficient routes in mail and postage delivery, diagnosis of transportation system, etc., can be efficiently planned using paths in graphs. It is noteworthy that all graphs discussed in this paper are assumed to be undirected. Furthermore, it is also supposed that these graphs have a finite number of nodes and edges.Among various types of paths in graph theory, Euler path is a special path that visits every edge of connected graph only once [4, 5]. In a connected undirected graph, there are no unreachable nodes and all the edges are bidirectional. A connected undirected graph will have an Euler path, but not an Euler circuit if and only if it has exactly two nodes of odd degree. The degree of node a is defined as the number of edges connected to that node. For the existence of the Euler path, it is necessary that exactly two nodes in a graph must have odd degree [4, 5]. A graph having the Euler path is called as the Euler graph. It is observed that while tracing the Euler graph, one may halt at any arbitrary node with some nodes (and its associated edges) remain unreachable.Some noteworthy classic work reported in [6, 7] concluded that the algorithm mentioned in Fleury’s algorithm [8–10] is an elegant but inefficient algorithm, since, at the end of the algorithm, there are no edges left, and the sequence from which the edges were chosen forms of an Eulerian cycle if the graph has no vertices of odd degree. Similarly, in [10], the proposed algorithm may also be implemented with the Deque. Because it is only possible to get stuck when the Deque represents a closed tour, one should rotate the Deque by removing edges from the tail and adding them to the head until unstuck, and then continue until all edges are accounted for. These issues were addressed in our proposed approach.In computers, there are a number of ways to represent graphs. One of these ways is to use adjacency lists. An adjacency list represents a graph as an array of linked list. The index of the array represents a node and each element in its linked list represents the other nodes that form an edge with the node [1, 2]. Figure 1 shows a simple graph G and its representation in adjacency list.Figure 1
A graph G (a) and its adjacency list (b).
(a)(b)In this paper, we have presented an approach in exploring deadlock-free Euler paths in Euler graphs by revising adjacency list. The rest of this paper is organized as follows. Section2 introduces the problem statement and traditional algorithm. In Section 3, the proposed approach is demonstrated in detail in comparison with conventional Euler path algorithm. Section 4 gives the proof of correctness of our proposed approach. Complexity of the proposed approach is given in Section 1. Some real-life applications of Euler path are discussed in Section 6. Concluding remarks are given in Section 7.


## 2. Problem Statement

Algorithm1 depicts the construction of the Euler path. While tracing the Euler graph according to Algorithm 1, one may halt (or stall) at any arbitrary node and fail to visit the remaining unvisited edges of the graph thus leading to an incomplete traversal of the Euler path. This situation of halting may result in exponential increase of the computation cost even if a single node with its associated edges is added in the Euler graph.Algorithm 1: Euler path [11, 12].
EularPathInConnectedGraph (G: connected undirected graph with exactly two nodes of odd degree)(1)
Make sure the graphG has 2 odd nodes.(2)
Start at any one of the two odd nodes.(3)
Traverse the edges one by one and then add in the array EP.(4)
While traversing abridge or a nonbridge edge, select the nonbridge edge.(5)
Stop when you run out of edges.return EPFigure2 shows Euler graph G and its two incomplete Euler paths halted at node a (Figure 2(b)) and b (Figure 2(c)), respectively.Figure 2
(a) Simple graph G. (b) A faulty-Euler path. (c) Other faulty-Euler path.
(a)(b)(c)The number on the edges shows the order of traverse. The order of traversal of the graph shown in Figure2(b) is b ⟶ a ⟶ c ⟶ d ⟶ a resulting to halting situation at node a, while the edges (c, e), (d, e), and (b, d) remain unvisited. Similarly, in Figure 2(c), the order of traverse is a ⟶ c ⟶ b ⟶ d ⟶ a ⟶ b that also freeze at node a with (c, e), (c, d), and (d, e) left unvisited.In other Euler graphH shown in Figure 3(a), two of many incomplete Euler paths halted at nodes d and b, respectively, are shown in Figures 3(b) and 3(c). The order of traversal of the graph of Figure 3(b) is b ⟶ d ⟶ c ⟶ f ⟶ g ⟶ e ⟶ d and thus results in halting at node d. The same scenario exists in the faulty traversal shown in Figure 3(c).Figure 3
(a) Simple graph H (b) A faulty Euler path. (c) Other faulty Euler path.
(a)(b)(c)Thebridge edge, as mentioned in Algorithm 1, is defined as an edge that when removed increases the number of connected components. The problem in faulty-Euler path lies when we accidentally visit the bridge edge. The procedure of finding the bridge edge by classical algorithm (Tarjan’s bridge-finding algorithm) [13] is itself a complicated task for strong connected Euler graphs because it finds out the bridge edge(s) by extracting spanning forest from the graph. This process incurs space and time complexity O(V × (V + E)) as computed by [1, 2]. Furthermore, the process becomes more complex when it tries to compute the size of multiplex computer network (represented by a graph) using conventional algorithm since, for every edge, another module is called in order to identify that the edge is bridge or not. Furthermore, the addition of extranode and its associated edges to an Euler graph (in a way that the resulting graph is also Euler) makes the graph too complex to explore the Euler path without being halted. In order to address this issue, we have proposed an informal solution to find the Euler path in any Euler graph without being halted, as discussed in Section 3.


## 3. Our Proposed Approach

Our proposed algorithm for finding deadlock-free Euler path in some Euler bidirectional connected graph is depicted in Algorithm2. We applied our proposed algorithm on a number of Euler graphs. Figures 4 and 5 show the simulation results on Euler graphs of Figures 2 and 3. The results showed that our proposed algorithm outperformed the conventional approach. The first column of the table depicts the edge currently being visited. The edges to be visited are shown in column “Remaining edges.” The last column shows the trace of our proposed approach to explore deadlock-free Euler path.Figure 4
Application of our proposed algorithm. The parenthesized labels of a node in the middle column indicate the nearest tree edge top to be selected; selected edges are shown in bold. The subscript inGi depicts the order of edge visited.Figure 5
Application of our proposed algorithm. The parenthesized labels of a node in the middle column indicate the nearest tree node to be selected; selected edges are shown in bold. The subscript inHi depicts the order of edge visited.Algorithm 2: Our proposed algorithm for Euler path.
EularPathRevised (G: undirected graph with exactly two nodes of odd degree)(1)
Make sure the graphG has 2-odd nodes.(2)
Start at any one of the two odd nodesv from the Degree column of new adjacency list.(a) Follow the edges to even-degree neighboring nodew of node v.(b) Add the visited edge in the list EP and remove it from GraphG.(3)
If there is no choice thenselect the other odd-degree node(4)
else repeat step a and b.(5)
Stop when you run out of edges.return EPStill another classical example will clearly explain the performance of our proposed approach and help in exploring a deadlock-free Euler path. Consider a simple graphM (see Figure 6) having two odd-degree nodes c and d. If we explore the Euler path from any node other than c or d, we will be stuck with some edges remained unvisited. For example, the path e ⟶ f ⟶ d ⟶ c ⟶ b ⟶ a ⟶ c will result to halt at node c with the edge (d, e) remain unvisited. If we apply our modified Euler algorithm, we can have deadlock-free path. Some of the many deadlock free Euler paths explored by our proposed algorithms are d ⟶ e ⟶ f ⟶ d ⟶ c ⟶ a ⟶ b ⟶ c and c ⟶ a ⟶ b ⟶ c ⟶ d ⟶ f ⟶ e ⟶ d. It is noteworthy that both the paths start from one odd-degree node and ends on other odd-degree node.Figure 6
Classical Euler graph M.Our proposed algorithm search for the odd-degree node first of an Euler graph from its revised adjacency list (see Figure1) and then visit its adjacent even-degree nodes one by one prior to visiting the other odd-degree node. In other words, as long as there exist edges connected to even-degree nodes and traverse these edges prior to the other odd-degree node in order to avoid any deadlock until there is no choice.


## 4. Proof of Correctness of Our Proposed Approach

Does our proposed approach always produce deadlock-free Euler path? The answer is yes. Let us prove by induction that each of the subgraphGi, of a Euler graph G, where i = 1, 2, ..., n, that is generated by removing the visited edges one by one by our proposed approach (Algorithm 2), leads to a deadlock-free Euler path. It immediately concludes that the last subgraph Gn (having only one edge with two nodes) will have at least one odd-degree node. The induction phase is trivial since G1 consists of a single edge connecting an odd-degree and even-degree node and also part of Euler path of the graph G. While solving the inductive step, we assume (for the sake of computation) that Gi −1 is among one of the deadlock-free Euler paths. We need to prove that Gi, generated from Gi −1 by our proposed approach, is leading towards a successful deadlock-free Euler path. We tried to prove this assertion by the contradictory rule by assuming that no Euler path of any undirected graph may have Gi. Let e=v,u be the edge from a specific node of Gi −1 to a node that is not in Gi −1. This assertion is used by our proposed method to expand Gi −1 to Gi. This assertion initiated our proposed approach by the assumption that e cannot belong to deadlock-free Euler path including G. As a result, by adding e to G, a cyclic path is constituted (Figure 7). Furthermore, the edge e=v,u, in this cyclic path, must have the other edge v′,w′ that is connecting a node v′ of Gi −1 to a node u′ that is not in Gi −1 (it is possible that v′ coincides with v or u′ coincides with u but not both). By removing the edge v′,w′ from this cyclic path, the resultant graph is with two disconnected components since the only edge e is confirming the deadlock-free Euler path. Hence, this Euler path of Gi −1 leads a deadlock-free Euler path which is clearly contradicting the assumption that no deadlock-free Euler path will exist in graph Gi. This completes the correctness proof of our proposed approach.Figure 7
Correctness proof of our proposed approach (dashed edge is critical edge since its removal will produce the graph in two disconnected components).


## 5. Complexity of Our Proposed Approach

While computing the complexity of our proposed algorithm, we considered the revised adjacency list (see Figure1). We start the Euler tour by selecting one of the odd-degree nodes from the revised adjacency list. This selection can be done in O(1) time as the adjacency list is sorted in the descending order according to the degree of each node. After selecting one odd-degree node, we then select its neighboring even-degree node from the revised adjacency list that will take O(e−1) because remaining edges are now e−1. This process will work in an iterative way until we have no choice other than visiting the other odd-degree node or all the edges are visited. It is pertinent to mention that the numbers of edges are equally important as the number of nodes since every edge has two end points and visiting one edge is the same as visiting the two nodes. Now, putting all together, we have the initial constant work done on first odd-degree node plus the work done on each edge on a Eulerian graph of n nodes, described above(1)2n+1/2π−0.5e−n2/2+nn−2n+1/21+On−0.5+eforn⟶∞,where n is odd.A detail discussion of the complexity of the proposed algorithm for Euler path is given in [14]. The proof of correctness of the complexity is given below.


### 5.1. Proof of Correctness

This equation is derived from the classic work on the Euler path and circuits reported in [14, 15]. Since n⟶∞, without loss of generality, we assume e<0.5; then, the statement of the second part of equation (1) can be considered as random regular circular tournament on n nodes on average 2n+1e0.5nn−21+On−0.5+e is considered or both the directed (and directed) spanning trees rooted at the nth node. It is noteworthy that it is e0.5 more than the average for a random Euler tournament that needs not to be a regular tree.It is noteworthy that these computations have several favorable interpretations in applied statistics models. Assume having an Eulerian graphG having start node v; the random walk may proceed to each adjacent edge that might be used at most once.


## 5.1. Proof of Correctness

This equation is derived from the classic work on the Euler path and circuits reported in [14, 15]. Since n⟶∞, without loss of generality, we assume e<0.5; then, the statement of the second part of equation (1) can be considered as random regular circular tournament on n nodes on average 2n+1e0.5nn−21+On−0.5+e is considered or both the directed (and directed) spanning trees rooted at the nth node. It is noteworthy that it is e0.5 more than the average for a random Euler tournament that needs not to be a regular tree.It is noteworthy that these computations have several favorable interpretations in applied statistics models. Assume having an Eulerian graphG having start node v; the random walk may proceed to each adjacent edge that might be used at most once.


## 6. Applications of Euler Path

In real world, we come across many applications that ask for a path that traverses each street in a neighborhood, each road in a transportation network, or each link in a large computer network exactly once [1, 2, 12]. Among the other areas where Euler path are applied is in the layout of circuits, in network multicasting, and in molecular biology, where Euler paths are used in the sequencing of DNA [5].


## 7. Conclusion

In this paper, we have proposed an efficient approach in finding a deadlock free Euler path in the Euler graph. Our proposed algorithm presented here is in fact optimal to within a constant factor, since every edge and node of a graph must be examined in order to explore a deadlock-free Euler path.



---

*Source: 8018373-2021-12-07.xml*