Hamilton and Euler Tour

When it comes to graph theory, path calculations on graphs are also inevitable. Today, let’s learn about Hamilton and Euler tours, which are very common in the literature with you.

Hamilton Tour

The Hamilton Path is the problem of deciding whether there is a Hamilton path or a Hamilton Circuit in a directional or non-directional graph. In the case of the Hamilton chart, all the hills on the chart must be crossed only once and the lap must be completed. If this path is completed off, it is called The Hamilton Graph.

HamiltonianPlatonicCycles

On Hamilton Path, which is one of the NP-Complete problems, all edges may or may not be closed. But the edges should certainly not be repeated.

If you remember the original chart that I mentioned earlier for you, let’s continue our path with this chart in this section. What is it about? Because we had a chance to examine it by activating the search algorithms for the given graph. For this reason, I want to continue with the same graph.

Let’s make an example together!

This image has an empty alt attribute; its file name is Ekran-Resmi-2020-07-29-12.18.15.png

As shown in the figure, the road must be completed, assuming that all Hills will be crossed only once when it is required to be examined in terms of the original graph Hamilton tour.

The combination of all possibilities is taken into account when calculating Hamilton laps. While the hills are controlled, it is necessary to be adjacent and the selected Hill is not on the road.

Now, let’s create the C code together to better master the subject.

Neighborhood and Road Control Function C Code
Hamilton Recursive Function C Code

Euler Tour

If a non-directional graph has a path that travels through all nodes, this path is called Eulerian path( Eulerian Path, Eulerian Trail, Eulerian Walk).

▪ If the degree of all the nodes of a non-directional connected graph is double, this graph is the Euler graph.
▪ In order for a non-directional graph to have an Euler path, it must have two or zero members with a single node degree.

Of course, let’s go a little deeper and look at the coding together.

Edge Erase Function

If you want to see more visual details on the graph where the Euler path is created graphonline.ru/en you can try it on your link and make it more fun!

NOTE: The conditions written above for the Euler path are based on the Fleury algorithm so that they apply to the Euler trail.

First, unlike Hamilton Road, if the degrees of the hills are one degree, in order for a lap to be considered the Euler tour, it will be either 0 or 2 pieces. To control this, the previously created printDegrees( ) function will be used.

As shown in the figure, this graph is likely to be the Euler tour. For this reason, another check should be made and the edges between the hills should be visited. As shown in the figure, all the hills in the graph are navigated and the single state of the Hill found during navigation is kept in a variable. The number of variables that are odd must be either 0 (none) or 2.

Printing the Euler Tour

In the image I give below, there is a complete version of the Euler tour function.

As I showed in the code, all edges can be navigated, starting from the u hill and going to the next current hill recursively every time. In the figure below, the function that provides pass control between hills is given.

As a result, we have learned about Euler and Hamilton paths, which are often included in Graph Theory. I hope to see you in my next post. Have a healthy day.

REFERENCES

https://mathworld.wolfram.com/HamiltonianGraph.html

https://www.gatevidyalay.com/hamiltonian-graphs-hamiltonian-path-hamiltonian-circuit/

From Wikipedia, “Hamilton Path”, February 2020, https://tr.wikipedia.org/wiki/Hamilton_yolu, The free encyclopedia.

Bilgi Sayamıyorum Beta, “What is Hamiltonian Graph ?”, http://bilgisayamiyorum.com/post/38/.

Computer Concepts, Sadi Evren Seker, “Eulerian Path”, June 2009.

http://bilgisayarkavramlari.sadievrenseker.com/2009/06/17/oyler-yolu-eulerian-path/.

From Wikipedia, The free encyclopedia, “Euler tour technique”, February 2019, https://en.wikipedia.org/wiki/Euler_tour_technique.

Related Posts

Leave a Reply