高等学校21卌纪教材 与欧拉圈和链(或回路和路)非常类似的问 题是哈密尔顿圈和链(或回路和路)的问题。1859 年,爱尔兰数学家哈密尔顿( WR.Hamilton)首 先提出“环球周游”问题。他用一个正十二面 体的20个顶点代表世界上20个大城市(见图 1.4a),这个正十二面体同构于一个平面图 (见图1114(b,平面图的定义稍后给出),要求 旅游者能否找到沿着正十二面体的棱,从某个 顶点(即城市)出发,经过每个顶点(即每座城市) 恰好一次,然后回到出发顶点?这便是著名的哈 密尔顿问题。 PT PRESS 人民邮电出版社
与欧拉圈和链(或回路和路)非常类似的问 题是哈密尔顿圈和链(或回路和路)的问题。1859 年，爱尔兰数学家哈密尔顿(W.R.Hamilton)首 先提出“环球周游”问题。他用一个正十二面 体的20个顶点代表世界上20个大城市(见图 11.1.4(a))，这个正十二面体同构于一个平面图 (见图11.1.4(b)，平面图的定义稍后给出)，要求 旅游者能否找到沿着正十二面体的棱，从某个 顶点(即城市)出发，经过每个顶点(即每座城市) 恰好一次，然后回到出发顶点?这便是著名的哈 密尔顿问题
19 图1114 14 15 PT PRESS (b)
图 11.1.4
高等学校21卌纪教材 按图1.4(c)中所给的编号进行旅游, 便是哈密尔顿问题的解。 对于任何连通图也有类似的问题。 PT PRESS 人民邮电出版社
按图11.1.4(c)中所给的编号进行旅游， 便是哈密尔顿问题的解。 对于任何连通图也有类似的问题
高等学校21卌纪教 18 d14 1216 16 10 8 17 20 C 图111.4 PT PRESS 民邮电出版社
图 11.1.4
高等学校21卌纪教材 定义1.3图G中的一圈(或回路),若它通 过G中每个结点恰好一次,则该圈(或回路)称为 哈密尔顿圈(或回路),具有哈密尔顿圈(或回路) 的图称为哈密尔顿无向(或有向)图。 由该定义可知,完全图必是哈密尔顿图。 PT PRESS 人民邮电出版社
定义11.1.3 图G中的一圈(或回路)，若它通 过G中每个结点恰好一次，则该圈(或回路)称为 哈密尔顿圈(或回路)，具有哈密尔顿圈(或回路) 的图称为哈密尔顿无向(或有向)图。 由该定义可知，完全图必是哈密尔顿图