1、8.2 哈密顿图8.2.1 问题的提出 8.2.2 哈密顿图的概念 8.2.3 格雷码8.2.4 旅行推销商问题8.2.1 问题的提出 n 周游世界 问题 ， Hamilton(1805-1865)， 1857ecdab8.2.2 哈密顿图的概念 n 定义 8.2.1 设 无向图 G，经过图 G的每个结点一次且仅一次的路称作 哈密顿路 。经过图 G的每个结点一次且仅一次的闭路称作 哈密顿回路 。n 定义 8.2.2 给定有向图 D，经过 D中每个结点一次且仅一次的有向路称作 哈密顿有向路 。经过D中每个结点一次且仅一次的有向闭路称作 哈密顿有向回路 。8.2.2 哈密顿图的概念 n 定义 8.
2、2.3具有哈密顿回路的无向图，与具有哈密顿有向回路的有向图，统称为 哈密顿图 。n 判断一个给定的图是否是哈密顿图的问题，称为 哈密顿问题 。n 哈密顿问题是图论中尚未解决的难题之一。8.2.2 哈密顿图的概念 n 哈密顿图？ 割点？ 二分图？8.2.2 哈密顿图的概念 n 完全图 Kn(n3)与 哈密顿图？8.2.2 哈密顿图的概念 n 例 8.2.1 若无向图 G存在 哈密顿路 P，其两个端点为 x与 y，则图 GK2中存在 P的镜像 P*，相应的端点为 x*与 y*。如此，边 (x, x*)、边 (y, y*)、路 P与路 P*就组成了 GK2的 哈密顿回路 。8.2.2 哈密顿图的概念n 如GGK2y* x*x yyx8.2.2 哈密顿图的概念 n n维立方体 Qn是 哈密顿图？yx x*y*8.2.2 哈密顿图的概念 n 定理 8.2.1 设 G是任意 n(n3)阶图，且对 G的 每个 顶点 x，都有 deg(x) ，则 G是哈密顿图。n 定理 8.2.2 设任意 n(n3)阶图 G，对 所有 不同非邻接顶点 x和 y，若 deg(x)+deg(y)n，则 G是哈密顿图。
