Hamiltonian path

Imagine a map of dots.

You want to draw a line. This line must touch every dot. But you can only touch each dot once. This is a special path.

A path that ends where it began is a cycle.

You can make a path from a cycle. Just remove one line. This makes a new way to travel.

A man named William Hamilton liked these paths. He made a puzzle for them. People studied these paths a long time ago. Some even used them on chessboards.

Finding these paths can be very hard. It is like a big puzzle to solve. Some maps have no paths at all. You can try to find them!

Imagine a map made of dots and lines.

You want to draw a single path through the dots. This path must visit every dot exactly once. We call this a Hamiltonian path. If the path ends at the start, it is a Hamiltonian cycle. A cycle is like a loop that visits every dot.

These ideas have a long history. In the 9th century, people in India and the Islamic world studied them. They looked at how a knight moves on a chessboard. This is called a knight's tour. Later, a man named William Rowan Hamilton made a puzzle. He used a shape called a dodecahedron.

Not every map has these paths. Some maps are very tricky. The Herschel graph is a small example. It has no Hamiltonian cycle.

Finding these paths can be a hard task. Computers find it difficult to solve them for big maps. This is because the number of ways to move grows very fast. It is a big puzzle for math experts to solve.

Imagine a map made of dots connected by lines. In math, we call these dots vertices and the lines edges. A Hamiltonian path is a special way to travel through this map. You must follow the lines to visit every single dot exactly once. If you find a path that ends where it started, you have found a Hamiltonian cycle. This cycle is like a complete loop that touches every point on the map.

Not every map allows for these special paths. Some maps are called traceable if they have a path. Others are called Hamiltonian if they have a full cycle.

There are different ways to look at these paths. A graph is called Hamiltonian-connected if you can find a path between any two dots. You can also have a Hamiltonian decomposition, which means splitting all the lines into several cycles. Some paths are directed, meaning the lines have arrows that show which way you must go. You can only move from the tail of an arrow to its head. Finding these paths can be a very hard job for computers. This difficulty is part of a category of problems called NP-complete.

These ideas have been around for a very long time. In the 9th century, mathematicians in India and the Islamic world studied them. They looked at the knight's tour on a chessboard. This is a path where a knight visits every square once. Later, in the 18th century, Abraham de Moivre and Leonhard Euler published work on these tours. William Rowan Hamilton gave his name to these paths through a puzzle. He created the icosian game using a shape called a dodecahedron.

Even before Hamilton, others were looking at these shapes. Thomas Kirkman studied cycles in polyhedra one year before Hamilton. He even found a shape that had no Hamiltonian cycle at all. The Herschel graph is another famous example of a shape without a cycle. It is the smallest possible polyhedral graph that lacks a Hamiltonian cycle.

Mathematicians like Dirac and Ore also found rules for these paths. They discovered that a graph is more likely to have a cycle if it has enough edges. In 1972, the Bondy-Chvátal theorem provided an even better way to describe these graphs.

You can see these patterns in many places. Every platonic solid is considered a Hamiltonian graph. A complete graph with more than two vertices is also Hamiltonian. You can even find these paths in the way we move through certain mathematical groups. Some people use these ideas to create logic puzzles called Hamilton mazes. The goal is to find the one unique cycle hidden in the map. It is a way to turn math into a game of discovery.

In the mathematical field of graph theory, a Hamiltonian path is a specific route through a network. This network is made of vertices, which are points, and edges, which are the lines connecting them. A Hamiltonian path is a sequence of edges that visits every single vertex in the graph exactly once. If this path is a cycle, meaning it ends at the same vertex where it began, it is called a Hamiltonian cycle or a Hamiltonian circuit.

A graph that contains such a path is known as a traceable graph. If a graph contains a Hamiltonian cycle, it is simply called a Hamiltonian graph.

There are several ways to define the relationships between these vertices and paths. A graph is considered Hamiltonian-connected if a Hamiltonian path exists between every possible pair of vertices. In some cases, a graph can undergo a Hamiltonian decomposition. This is an edge decomposition where the entire graph is split into several distinct Hamiltonian circuits. Some paths are also directed, meaning the edges act like one-way streets with arrows. In a directed graph, you must follow the direction from the tail of the arrow to its head.

Finding these paths is a major challenge in computer science. Determining whether a graph contains a Hamiltonian path or cycle is categorized as an NP-complete problem. This means it is a computationally difficult task for computers to solve as the graphs grow larger. Mathematicians use different tools to study these paths, such as the Hamiltonian cycle polynomial. This is an algebraic representation used for weighted digraphs. The polynomial is not zero if and only if the digraph is Hamiltonian.

The history of these ideas stretches back much further than the 19th century. In the 9th century, mathematicians in India named Rudrata and in the Islamic world named al-Adli ar-Rumi studied these concepts. They focused on the knight's tour, which is a Hamiltonian cycle on a chessboard's knight's graph. Later, in the 18th century, Abraham de Moivre and Leonhard Euler published work on these tours. William Rowan Hamilton, for whom these paths are named, invented the icosian game. This was a puzzle involving finding a Hamiltonian cycle on the edges of a dodecahedron.

Other researchers made important discoveries around the same time as Hamilton. Thomas Kirkman studied Hamiltonian cycles in polyhedra just one year before Hamilton did. Kirkman was notable for finding a polyhedron that did not have a Hamiltonian cycle. The Herschel graph is a famous example of this, as it is the smallest polyhedral graph without a Hamiltonian cycle.

While Hamilton used icosian calculus to solve his puzzle, that specific method does not work for all arbitrary graphs.

Mathematicians have developed theorems to predict when a graph will be Hamiltonian. In 1952, G. A. Dirac and Øystein Ore provided theorems stating that a graph is Hamiltonian if it has enough edges. In 1972, the Bondy-Chvátal theorem expanded on this by using the concept of a graph's closure. This process involves repeatedly adding edges between nonadjacent vertices until a specific property is met. If the resulting closure is a complete graph, the original graph is Hamiltonian.

Many different types of mathematical structures are Hamiltonian. For example, every platonic solid is considered a Hamiltonian graph. A complete graph with more than two vertices is always Hamiltonian. Every cycle graph is also Hamiltonian. Even certain complex structures, like the Cayley graph of a finite Coxeter group, have been found to be Hamiltonian. These patterns show how deeply these paths are embedded in the study of shapes and symmetry.