环球旅行问题

来自计算思维百科
跳转至: 导航搜索

威廉·哈密顿1957年发明了一种游戏,就是在实心正十二面体的20个顶点处标以著名的城市名称,要求游戏者找一条沿着各边通过每个顶点恰好一次的闭合路径(称为回路),即“环球旅行”。由此引出了哈密顿回路和哈密顿图等概念。迄今为止,尚未获得图中存在哈密顿回路的充要条件。