关于骑士旅游问题的几个定理

关于骑士旅游问的几个定理 柏 森 杨 晓 帆 瞿 晓 鸿 柏 林 ( ) 重庆大学计算机研究所, 重庆, 400044; 第一作者 33 岁, 男, 讲师 摘 要 研究了骑士旅游问题以及广义骑士旅游问题。给出了不存在和存在 H am ilto n ()的几个充分条件。圈 路 H am ilto n 关键词 图论; 哈密顿圈; 哈密顿路; 充分条件 骑士旅游问题; 广义骑士旅游问题;ƒ 2完全性N P 中国图书资料分类法分类号 O 157. 9 引言0 在国际象棋和中国象棋里, 都曾提出过是否存在马的周游路线问题, 该问题通常称为骑 2 () ()士 马旅游问题 2如果将 ×棋盘上 个格子的每一个用图的一个 . k n igh tto u r p ro b lem n n n 1 顶点代替, 两个顶点连边当且仅当骑士一步可以跳到, 这样的图称为棋盘上的马步图, 那 么 骑士巡游问题就可以转化成马步图中是否有 圈或路的判定问题。 一般图中H am ilto n 2 完全的, 因此很可能不存在多项式时间算法。而骑 H am ilto n 圈或路的存在性问题是 N P - 士旅游问题是一类特殊图上的 H am ilt2n 圈或路的判定问题, 很有进一步研究的价值。 肖金 3提出了下列猜想:声 猜想 1: 当 < 5 时, 任何初始点都无解。n 猜想 2: 当 ?5 且为偶数时, 任一初始点都有解。n () 猜想 3: 当 ?5 且为奇数时, 若初始点纵横坐标 以四角之一为原点之和为偶数便有n 解, 为奇数则无解。 4 < 5 的情况已有现成的结论, 即猜想 1 已为真, 不应再称为猜想。 文献 4 中还给出 n () 了 = 6、= 8 的一种解 如图 1 和图 2, 它构成了 圈。 这实质上说明了 = 6 和 n n H am ilto n n n ( = 8 时猜想 2 是正确的。值得一提的是, 为了更清晰, 图中将方格用一个格点 格点就是纵横 ) 坐标都是整数的点, 也就是图论中的顶点代替。文献1 中没有找到判定棋盘马步图是否有 () 圈 或路存在的方法。文献 5 给出了一些判定图有 圈或路存在的充分 H am ilto n H am ilto n 条件, 但是, 这些条件大都是很强的。 通过研究, 对 为奇数, 我们得出了本文最重要的定理n 1 至定理 5. 从而削弱了判定马步图是否有 圈或路存在的条件, 也部分地证明了上 H am ilto n 述猜想。 在此基础上, 提出了两个更进一步的猜想。 图 1 n = 6 时棋盘马步图的 H am ilto n 圈 图 2 n = 8 时棋盘马步图的 H am ilto n 圈 1 预备知识 为了进一步讨论, 下面给出几个概念的定义, 凡未给出的概念与文献 6 相同。 定义 1 平面坐标格点就是以棋盘格子的宽为单位, 纵横坐标都是整数的点。 定义 2 一个马称为 [ , ] 广义马, 如果它在平面坐标格点上跳跃于边长分别为 和 rs r s () 的矩形的对角顶点。 自然, 象棋马称为 1, 2 马 或 2, 1 马。 定义 3 一个棋盘称为 ×棋盘, 如果棋盘纵向有 个格子横向有 个格子。 自然,n m n m 国际象棋棋盘是 8×8 棋盘。 定义 4 将 ×棋盘上的每个格子用图的一个顶点代替, 两个顶点连边当且仅当象棋 n m 马一步可以跳到, 这样的图称为 ×棋盘上的马步图。n m () 定义 5 骑士旅游问题 2就是国际象棋中的骑士在 ×棋盘上按k n igh tto u r p ro b lem n n 2 使骑士跳 - 1 步而1, 2 马走动, 让骑士从任一初始格点开始跳动, 要求给出一个,n () 遍历棋盘上的所有格点 使每个格点恰好经过一次。 骑士旅游问题实质就是在 ×棋盘上的马步图中找 路或圈的问题。n n H am ilto n 定义 6 广义骑士旅游问题就是骑士按广义马走动的骑士旅游问题。2 主要结论 本文的主要结论可用如下的定理示。 定理 1当 为奇数时, 骑士旅游问题不存在 圈。 n H am ilto n 定理 2当 为奇数时, 广义骑士旅游问题不存在 圈n H am ilto n ( ) 定理 3当 为奇数时, 若初始点纵横坐标 以四角之一为原点之和为奇数, 则骑士旅n ()游问题无解 即无 路. H am ilto n ( ) 定理 4 当 为奇数时, 若初始点纵横坐标 以四角之一为原点之和为奇数, 则广义骑 n ()士旅游问题无解 即无 路。 H am ilto n () ( ) 定理 5 当 = 5?1 且为奇数时, 若初始点纵横坐标 以四角之一为原点之和为 n m m ()偶数, 则骑士旅游问题有解 即有 路。H am ilto n 3 定理的证明 3. 1 定理 1 的证明 定理 1 的证明要用到如下结论: 7如果马从 A 点用一种方法跳到 B 点走了偶数步的话, 那么这只马用任意一引理 1 种方法从 A 点跳到 B 点都需要走偶数步。 从引理 1 很容易得到如下推论: 推论 1如果马从 A 点用一种方法跳到 B 点走了奇数步的话, 那么这只马用任意一种 方法从 A 点跳到 B 点都需要走奇数步。 推论 2如果广义马 [ r, s ] 从 A 点用一种方法跳到 B 点走了奇数步的话, 那么当 r + s 为奇数时这只广义马用任意一种方法从 A 点跳到 B 点都需要走奇数步。 () 推论 1 的证明是很容易的, 现在证明推论 2. 假定A 点的坐标为 x , y , 广义马跳一步跳到 ()()()(了A 1 点, 则A 1 点的坐标只能是 x + r, y + s、x + r, y - s、x - r, y + s、x - r, y - )()()() () s、x + s, y + r、x + s, y - r、x - s, y + r或 x - s, y - r, 于是A , A 1 两点坐标和之 ( ) ( ) 差为: ? r + s或 ? r - s.因为 r + s 为奇数, 则 r - s 也为奇数。如果广义马[ r, s ] 从A 点 跳了偶数步跳到B 点, 那么A 、B两点的坐标和之差一定是偶数; 而如果广义马[ r, s ] 从A 点跳了 奇 数步跳到B 点, 那么A 、B 两点的坐标和之差一定是奇数。又因为象棋盘上任意两点的坐标和 之差是奇数或偶数是完全确定的, 故当 r + s 为奇数时, 推论 2 是成立的。 () 用反证法来证定理 1. 假设存在 H am ilto n 圈, 那么不失一般性, 马从点 A 0, 0出发在 2 () () 遍历 每个格点被走一次且仅被走一次了除点B 2, 1以外的所有 n - 1 个格点之后, 最终 2 () 能够走到 B 点。此时, 马跳的步数 = n - 1 为偶数。然而, 马从 A 点可用 1 步 奇数步跳到 () B 点 如图 3, 这与上述推论 1 矛盾。所以它不存在 H am ilto n 圈。 图 3 马跳步子的坐标关系图 4 n = 3 时, A 点马不能跳到 3. 2 定理 2 的证明 定理 2 的证明要用到如下结论:8( 引理 2 一个 [ r, s ] 广义马是遍及的 它在有限步之内可以从一点跳到任意的另一 ) 点, 当且仅当 r、s 互素且一奇一偶。 下面来证明定理 2. 当 r + s 为偶数时, 则 r、s 同奇或同偶, 由引理 2 知 [ r, s ] 马是不能遍及棋盘的, 故无 H am ilto n 圈。 () 当 r + s 为奇数时, 利用 3. 1 中的推论 2, 其证明方法与定理 1 的证明完全类似 从略。 3. 3 定理 3 的证明 当 n = 1 时, 马根本不能跳, 故骑士旅游问题无解。 () 当 n = 3 时 如图 4, 实线为马跳步子, 中间格点A 不能由一马从其余的任一格点所到 达, 故 n = 3 时骑士旅游问题亦无解。 ( ) 当 n ? 5 时, 建立坐标如图 3 所示, 则纵横坐标之和为偶数的点 用“?”表示的个数 2 )(() ()r= n + 1ƒ21 设为 r1 1 2 () (() )r= n - 12()ƒ纵横坐标之和为奇数的点 用“?”表示的个数 设为 r 2 2 2 () 注意到马一步只能从 ? 点跳到 ? 点, 或从 ? 点跳到 ? 点。这是因为: 马从点 C x , y 一步 (() 只能跳到点 D 、D 、E 、E 、F 、F 或 G 、G 八个点, 而它们的坐标分别是 x + 1, y + 2、x121212 12 ((((())))) + 1, y - 2、x + y + 1、x + 2, y - 1、x - 1, y + 2、x - 1, y - 2或 x - 2, y 2, )() () + 1、x - 2, y -1如图 3. 计算知 C 和这八个点中每一个坐标和之差都是奇数。 以 ? 作为初始点, 假设以 ? 作为终点, 即马的跳法为 ? ? ? ? ? ? ?? ? ? ? ? ? ? () () 则 ? 点的个数 = ? 点的个数, 这与 1和 2矛盾。即以 ? 作为初始点不能以 ? 作为终点。 以 ? 作为初始点, 假设以 ? 作为终点, 即马的跳法为 ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? () () 则 ? 点的个数 = ? 点的个数 + 1 > ? 点的个数, 这也与 1和 2矛盾。 于是有: 以 ? 作为初始点, 则骑士旅游问题无解。即定理 3 得证。 3. 4 定理 4 的证明 () 设广义马为[ r, s , 当 r + s 为奇数时, 其证明与定理 3 的证明类似 从略. 当 r + s 偶数时, () 由引理 2 知广义马是不能遍及的, 故广义骑士旅游问题无解 即无 H am ilto n 路. 定理 4 得证。 3. 5 定理 5 的证明 () 1当 m = 1 时, 其有 H am ilto n 路的情况如下: () 在图 5 a中, 由于 a 、b、c、d 分别与 a 、b、c、d 关于对角 OA 对称, 因此对于其他 1111 2, 2, 2, 2, () 纵横坐标为偶数的点: a 、b、c、d , 也可画出其以 0, 0开始分别以它们结束的 H am ilto n2222 () 路。即当 n = 5 时定理 5 是成立的。并且有以 0, 0作为初始点, 存在以任何纵横坐标之和为 () 偶数的点 除原点外结束的 H am ilto n 路。即以纵横坐标为偶数的点作为初始点, 骑士旅游 问题有解。 () 2当 m = 3, 即 n = 15 时, 用阴影“# ”字将其分为 9 个 n = 5 的小棋盘, 将它们分别称为: 左上块, 中上块, 右上块, 左中块, 中中块, 右中块, 左下块, 中下块和右下块。并对其中 纵横坐标之和为偶数的点加上“?”, 现在要证的即是图 6 中所有加“ ?”点作为初始点均有 ()解 即有 H am ilto n 路。 () () 假设马从原点O 0, 0起跳, 则根据图 5 a的 H am ilto n 路按图 6 的实线方式连接, 存在 以右上块中任意一加“ ?”点结束的 H am ilto n 路。于是, 在右上块, 所有加“ ?”点作为初始 点, 则有解。 ()() () 根据对称性, 让马从 A 14, 0、B 14, 14、C 0, 14起跳, 则同理可以证明在左上块, 左 下块, 右下块所有加“ ?”点作为初始点均有解。 对于中中块, 按图 6 中虚线的方式连接, 可以在中中块内任意一加“ ?”点结束。即在中 中块内所有加“ ?”点作为初始点均有解。 剩下的只需证明在左中块, 中上块, 中下块和右中块内的加“ ?”点作为初始点有解。这 ()要用到 10 × 5 棋盘的 H am ilto n 圈 图 7. 图 5 n = 5 时棋盘马步图的一些 H am ilto n 路 () () 以 a 1, 9作为初始点时, 则根据图 7, 在左上块和左中块内存在以点 3, 8为终点的 1 () () H am ilto n 路。设马从 3, 8点跳到中中块的 5, 9点, 然后按图 8 中实连线的跳法, 可以得到 一条以左下块内任意加“ ?”点为终点的 H am ilto n 路。 () () 以 a 3, 9作为初始点时, 则根据图 7, 在左上块和左中块内存在以点 4, 7为终点的2 () () H am ilto n 路。设马从 4, 7点跳到中中块的 5, 9点, 然后按图 8 中实连线的跳法, 可以得到 一条以左下块内任意加“ ?”点为终点的 H am ilto n 路。 () () 以 a 3 0, 8作为初始点时, 则根据图 7, 在左中块和左下块内存在以点 2, 9为终点的 () () H am ilto n 路。设马从 2, 9点跳到左上块的 0, 10点, 然后按图 8 中虚线的跳法, 可以得到 一条以中中块内任意加“ ?”点为终点的 H am ilto n 路。 () () 以 a 2, 8作为初始点时, 则根据图 7, 在左中块和左下块内存在以点 0, 9为终点的4 () () H am ilto n 路。设马从 0, 9点跳到左上块的 1, 11点, 然后按图 8 中锯齿线的跳法, 可以得 到一条以中中块内四个角点之一为终点的一条 H am ilto n 的路。 () () 以 a 4, 8作 为 始 点 时, 则 根 据 图 7, 在 左 上 块 和 左 中 内 存 在 以 点 3, 6为 终 点 的5 () () H am ilto n 路。设马从 3, 6点跳到左下的 4, 4点, 然后按图 9 中实连线的跳法, 可以得到一 条以中中块内任意加“ ?”点为终点的 H am ilto n 路。 图 6证明左上块、左下块、右上块、右下块图 710 × 5 棋盘马步图的 H am ilto n 圈 及中中块加“ ?”点有解的图 图 8证明左中块加“ ?”点 a、a 、a 、a 有解的图图 9证明左中块加“ ?”点 a、a 、a有解的图 1234 567 () () 以 a 6 1, 7作为初始点时, 则根据图 7, 在左上块和左中块内存在以点 0, 5为终点的 () () H am ilto n 路。设马从 0, 5点跳到左下块的 1, 3点, 然后按图 9 中虚线的跳法, 可以得到一 条以中中块内四个角点之一为终点的 H am ilto n 路。 () () 以 a 3, 7作为初始点时, 则根据图 7, 在左上块和左中块内存在以点 4, 5为终点的7 () () ( H am ilto n 路。设马从 4, 5点跳到左下块的 2, 4点, 然后按图 9 中锯齿线的跳法, 跳到 4,) 根4点, 再按虚线的跳法, 可以得到一条以中中块内四个角点之一为终点的 H am ilto n 路。 据图 8 的对称性, 按上述类似的方法可以证得以 a 、a 、 、a 作为初始点时, 它存在8912 ( ) H am ilto n 路。于是, 在左中块内, 以纵横坐标之和为偶数的点 加“ ?”的点作为初始点均 有解, 且终点也为加“ ? 的点”。 根据对称性, 类似可证, 在中上块、中下块、右中块内所有加“ ?”的作为初始点均有解。 于是有: n = 5 × 3 = 15 时, 定理是成立的。 () 3当 m > 3 时, 证明方法与 m = 3 时的方法相同。 综上所述, 定理 5 得证。 4 结束语 关于骑士旅游问题我们得出了几个一般性的定理, 从而部分证明了文献 2 中的猜想。 ) () (从定理 5 的证明中, 可以看出: 当 n = 5m m > 1 且为奇数时, 若以 0, 0点作为初始点, 则 存在以任何纵横坐标之和为偶数的点结束的 H am ilto n 路。于是有如下更进一步的猜想。 () 猜想 1 对骑士旅游问题, 当 n ? 5 且为奇数时, 若以 0, 0作为初始点, 则存在以任何 (() ) 纵横坐标之和为偶数 除 0, 0以外的点结束的 H am ilto n 路。 () 猜想 2 对骑士旅游问题, 当 n ? 5 且为偶数时, 若以 0, 0作为初始点, 则存在以任何 纵横坐标之和为奇数的点结束的 H am ilto n 路。 参 考 文 献 () () 1 曹新谱, 肖宝麟. 国际象棋棋盘上马的周游路线问题. 重庆大学学报 自然科学版, 1988, 11 4: 63, 68 2 洪等译. 计算机算法和引论. 上海: 复旦大学出版社, 1985. 307, 308Sa ra B aa se () () 肖金声. 骑士游游问题的解. 中山大学学报 自然科学版, 1994, 33 3: 15, 183 4 . 醩 著, 郭照人译. 图论导引. 北京: 高等教育出版社, 1985. 79, 230BA nd r fa i 5 ( ) Ro na ld J. Go u ld. U p da t ing the H am ilto n P ro b lem —A su rvey. Jo u rna l o f G rap h theo ry. 1991, 15 2: 121, 337 著. 吴望名等译. 图论及应用. 北京: 科学出版社, 1984. 1, 284,6 Bo ndy J ZM u r ty U S R () 7 万哲先. 几个数学题目. 数学通报, 1956, 12: 13, 15 () 8 胡久稔. 象棋马与数学. 数学通报, 1964, 8: 50 9 () 陶克. 关于 维马步问题. 数学的实践与认识. 1982, 1: 26, 31n () 10 胡久稔. 格点上的一个离散数学问题. 数学通报. 1981, 3: 30, 31 - Seve ra l T h eo rem s abo u t K n igh tto u r P ro b lem B a i S en Y a n g X ia of a n Q u X ia oh on g B a i L in (), R e sea rch In st itu te o f Com p u te r Sc ien ceC ho n gq in g U n ive r sity 22. A BSTRACT K n igh tto u r p ro b lem an d gen e ra lized k n igh tto u r p ro b lem a re stu d ied 2A few su ff ic ien t co n d it io n s a re p re sen ted fo r th e no n ex isten ce an d ex isten ce o f H am ilto n ().c ircu it H am ilto n p a th ; ; ; ƒKEYW O RD S g rap h th eo ryH am ilto n cyc le sH am ilto n p a th ssu ff ic ien t co n d it io n 222; ; k n igh tto u r p ro b lem gen e ra lized k n igh tto u r p ro b lem N P com p le ten e ss