Directed Graph Solution Proposed by Hierholzer

In the realm of graph theory, we often encounter the intriguing task of finding an Euler circuit in a graph. Recently, we discussed the problem of determining whether a given graph is Eulerian or not for an undirected graph. Today, we delve into the process of printing an Euler circuit for a given directed Eulerian graph, using Hierholzer's Algorithm.

The algorithm, first implemented by the mathematician Hierholzer, visits each vertex and each edge exactly once. It utilises a depth-first search (DFS) approach and has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.

The algorithm starts with an empty Euler circuit and chooses any starting vertex, say vertex 0, for our given graph with 5 nodes: , and adjacency list . The path after visiting vertices 0, 3, 4, 0, 2, 1, 0 is initially created as .

The approach involves following a trail of edges from the chosen starting vertex until returning to the same vertex. As long as there exists a vertex that belongs to the current tour but has adjacent edges not part of the tour, the algorithm starts another trail from that vertex, following unused edges until returning to the same vertex, and joins the tour formed in this way to the previous tour.

With this method, the Euler circuit after adding vertices to it in the order they were visited for the last time is found to be . It's important to note that an Euler circuit is a path that traverses every edge of a graph exactly once and ends on the starting vertex.

For example, if we apply Hierholzer's Algorithm to the given graph, the example output for the Euler circuit would be . The space complexity of the algorithm is O(V + E), due to the use of a stack and a list.

It's worth mentioning that for a directed graph to have an Euler circuit, it must satisfy two conditions: (1) All vertices belong to a single strongly connected component, and (2) All vertices have the same in-degree and out-degree. In our given graph, all vertices are part of a single strongly connected component, and all vertices have the same in-degree and out-degree of 1, making it a suitable candidate for an Euler circuit.

In conclusion, Hierholzer's Algorithm offers a simple yet effective way to find and print an Euler circuit for a given directed Eulerian graph. By following a depth-first search approach and visiting each vertex and edge exactly once, we can efficiently determine and print the Euler circuit for various directed Eulerian graphs.