Hamiltonian circuit

(idea) by m_turner Wed Jan 03 2001 at 22:08:44
A graph cycle (closed loop) through a graph that visits each node exactly once. A graph possessing a Hamiltonian circuit is said to be a Hamiltonian graph. The Hamiltonian circuit is named after Sir William Rowan Hamilton, who devised a puzzle in which such a path along the edges of an icosahedron was sought.
(idea) by philihp Mon Sep 24 2001 at 2:06:08
Reference: Euler Circuit

Where an Euler circuit must pass each link (edge) exactly once, a Hamiltonian circuit pass go through each node (vertex) exactly once. Side note, I learned this week, it's pronounced 'Oil-er', like one who oils, and not 'Euler' like ruler. Please don't sound as ignorant as I did in front of your discrete math professor.

Reference: Hamiltonian Path

While a Hamiltonian path must pass each node exactly once, a Hamiltonian circuit must pass each node exactly once, and end at the node the path started at. This said, All Circuits are Paths.

Reference: Traveling Salesman Problem

Commonly referred to as a TSP, it simulates a salesman who must visit each node preferably once, go home at the end of the day, and have traveled the least distance needed. Any path the salesman takes is a Hamiltonian Circuit.
Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.