Introduction¶

A graph is a mathematical structure used to represent relationships between objects.

# Create a directed graph using the DiGraph method
G = nx.DiGraph()
G.add_edges_from([(1, 2), (2, 3), (3, 1)])

An Eulerian tour is a closed trail where each edge is traversed exactly once. A Hamiltonian cycle is a cycle where each vertex is visited exactly once, and a Hamiltonian path is a path where each vertex is visited exactly once.

Note the difference between trails, tours, and paths!

The definitions of Eulerian tours and Hamiltonian cycles are very similar, but this subtle difference (replacing edges with vertices) causes the problem of finding a Hamiltonian cycle to lack a polynomial-time algorithm, whereas for finding an Eulerian tour, a linear algorithm can be provided!

The Bridges of Königsberg¶

As the story goes, the concept of graphs originated from the Bridges of Königsberg problem. Königsberg was a city divided by a river into several regions, with bridges connecting the regions. Over time, the citizens began to wonder: Is it possible to start from one region, traverse every bridge exactly once, and return to the starting point? You can see that this problem is precisely equivalent to finding an Eulerian circuit.