天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，
寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。
这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不 一定是双向的。比如A→B,但B→A是不允许的。
换一种说法，对于一个给定的网络，确定起点和终点后，如果存在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。
从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。
要满足两个条件：
1.封闭的环
2.是一个连通图，且图中任意两点可达
经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。
经过图中所有顶点一次且仅一次的回路称为哈密顿回路。
具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。
平凡图是哈密顿图。
一种寻找哈密顿环的简单方法
假设有一个图G，图中不存在交叉线（即如果有交叉线就认为交叉点也是图的一个顶点），以图G中任取的一个环T(即除了与环中相邻的顶点有连接外，与其他属于该环的顶点无连接)为起点，逐步扩展该环的范围，直到图G的所有顶点都在环中为止,此时所得的环一定是哈密顿环。扩展规则为：
任取环T的一边，如果该边不是图G最外围的边且去除该边后不会导致环的断裂（即不产生某个顶点只有一条边与其相连的情况），就将其去除。由此产生一个更大的环，以该环为新的选择，重复上面的去边操作，直到图G的所有顶点都在环上或者去除环的任何一边再也不会导致环的扩大，如果是前一种情况，则表明找到了一个哈密顿环，否则该图不存在哈密顿环。