Resolving Eulerian path with inchrosil

Eulerian paths could define as graph which visits every edge exactly once, with singularity starts and ends on the same vertex. Therefore, an Eulerian path is a cycle which contains all edges of a graph just once. This problem was posed and resolved by Leonhard Euler himself in 1736 in a problem which has the name of the seven bridges of the city of Königsberg. The problem is enunciated in the following form: two islands in the Pregel River, in Königsberg are joined together and with land by seven bridges.

• Is it possible to take a walk starting by any of the four parts of land, crossing each one of the bridges just once?

Euler approached the problem representing each part of land by one point and each bridge by a line, joining the corresponding dots. Then, the previous problem can be transferred to the following question:

• Is it possible to travel round the representation without repeating the lines?

Euler demonstrated that it was not possible because the number of lines that affect each dot is uneven (a necessary condition to be able to enter and exit each dot). Therefore, this problem posed questions such as the following;

• How is it possible to cover the cable of this electricity grid without repeating sections of grid?
• How can this route be performed, passing through specific streets?

There is a complexity to solve these cycles’ problems, by this reason, we have considered inversely, i.e. all vertices could be converted in edges and all edges could be converted in vertices, with simple conversion, we can calculate any Hamiltonian path associated of conversion. On the other hand, since now the vertices represent the edges and it is necessary to know what sequence of vertices we should follow to be able to pass through all the edges.

Let us suppose the directed and non-weighted graph of Figure 1, which would be a multi-graph, i.e. a non-deterministic automaton.

Figure 1: Eulerian path.

The graph of Figure 8 can also be represented as follows, where V₁ is the set of vertices and E₁ is the set of edges.

G₁=(V₁,E₃) with V₁=(v₁,v₂,v₃) and E₁=(a₁,a₂,a₃,a₄,a₅,a₆)

Furthermore, we have the following vertex links, by means of edges;

U={(v₁,v₂,a₁),(v₁,v₂,a₂),(v₁,v₂,a₃),(v₂,v₃,a₄),(v₂,v₃,a₅),(v₂,v₃,a₆),(v₃,v₁,a₆)}

Where the nomenclature used for these links is (source vertex, destination vertex, edge). If said inversion is made, and if the edges are considered as vertices and the vertices as edges, we would obtain the following graph.

G₂=(V₂,E₂) with V₂=(a₁,a₂,a₃,a₄,a₅,a₆) and E₂=((v₁,v₂),(v₂,v₃),(v₃,v₁))

Furthermore, we have the following vertex links, by means of edges;

W= {(a₁, v1, v2, v2, v3, a4) . . .}

Therefore, the graph will have the form shown in Figure 1. Consequently, if the Hamiltonian path of the previous graph G₂ is shown, it can be stated that there is a solution or Eulerian path G₁. It can also be considered that the graph is weighted, the total costs of each one of the paths can be calculated and, therefore, sorted by cost, although the Eulerian paths do not have weight, new problems of optimization in the Eulerian paths could be posed. In conclusion, if a Hamiltonian path exists in graph G₂, it can be stated that there is an Eulerian path in graph G₁. Finally, it can be stated that Eulerian cycles can be resolved, for which purpose, when encoding the base of strands or banks of strands, it was established that the initial node was the same as the final. In this way, cycle problems can be resolved using the Hamiltonian Path device.