Discrete Math with SageMath: Learn math with open-source software

An Euler path is a path that uses every edge of a graph exactly once. An Euler path that is a circuit is called an Euler circuit.

The idea of an Euler path emerged from the study of the Königsberg bridges problem. Leonhard Euler wanted to know if it was possible to walk through the city of Königsberg, crossing each of its seven bridges exactly once. This problem can be modeled as a graph, with the land masses as vertices and the bridges as edges.

We can use Sage to determine if a graph is Eulerian.

Since this returns False, we know that the graph is not Eulerian. Therefore, it is not possible to walk through the city of Königsberg, crossing each of its seven bridges exactly once.

We can use path=True to determine if a graph contains an Euler path. Sage will return the beginning and the end of the path.

If the graph is Eulerian, we can ask Sage to find an Euler circuit with the eulerian_circuit function. Let’s take a look at the following graph.

If we are not interested in the edge labels, we can set labels=False. We can also set return_vertices=True to get a list of vertices for the path

A Hamilton path is a path that uses every vertex of a graph exactly once. A Hamilton path that is a circuit is called a Hamilton circuit. If a graph contains a Hamilton circuit, we say that the graph is Hamiltonian.

Hamilton created the "Around the World" puzzle. The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting all of the other cities exactly once, and returning back to the starting city.

We can represent the dodecahedron as a graph and use Sage to determine if it is Hamiltonian. See for yourself if the dodecahedron is Hamiltonian.

We can ask Sage to determine if the dodecahedron is Hamiltonian.

By running Graph.is_hamiltonian?? we see that Sage uses the traveling_salesman_problem() function to determine if a graph is Hamiltonian.

The traveling salesperson problem is a classic optimization problem. Given a list of cities and the lengths between each pair of cities, what is the shortest possible route that visits each city and returns to the original city? This is one of the most difficult problems in computer science. It is NP-hard, meaning that no efficient algorithm is known to solve it. The complexity of the problem increases with the number of nodes. When working with many nodes, the algorithm can take a long time to run.

Let’s explore the following graph:

We can ask Sage if the graph contains a Hamiltonian cycle.

The function hamiltonian_cycle returns True and lists an example of a Hamiltonian cycle as the list of vertices [1, 2, 3, 4, 5]. This is just one of the many Hamiltonian cycles that exist in the graph. Now lets find the minimum Hamiltonian cycle.

Now we have the plot of the minimum Hamiltonian cycle. The minimum Hamiltonian cycle is the shortest possible route that visits each city and returns to the original city. The minimum Hamiltonian cycle is the solution to the traveling salesperson problem. We can ask Sage for the sum of the weights of the edges in the minimum Hamiltonian cycle.

If there is no Hamiltonian cycle, Sage will return False. If we use the backtrack algorithm, Sage will return a list that represents the longest path found.