|国家预印本平台
首页|关于Knight’s Tour Problem 的图论解法

关于Knight’s Tour Problem 的图论解法

he solutions of Knight’s Tour problem in Graph Theory

中文摘要英文摘要

本文通过分析欧拉所给出的Knight’s Tour Problem 的解法, 结合哈密尔顿路和哈密尔顿圈的相关知识,得出其解法对应着二部图中的一条哈密尔顿圈。由此再充分利用8×8棋盘所对应的8×8表格的对称性及同构图的特性,对欧拉所给出的Knight’s Tour Problem 的解法作了进一步的探讨,得出了以欧拉的解法为基础的以任一棋格为骑士周游起点的另外一系列解法。最后,把Knight’s Tour Problem推广到了m×n棋盘上,考虑到移动规则的特殊性,利用图论的相关知识,得到了3×4、8×16和16×16棋盘上的Knight’s Tour Problem的解法,同时给出了8m×8n(m>2,n>2)棋盘上Knight’s Tour Problem的猜想。

ccording to the analysis of the solution to Knight’s Tour Problem given by Euler earlier and the knowledge of Hamilton path and Hamilton cycle, we obtain that the solution denotes a Hamilton cycle in the defined bigraph. With the use of the symmetrics of 8-by-8 chess-board and the special properties of isomorphic graphs, we botain a series of solutions of this problem whose each square can be the initial position of the knight from the advanced discussions about the solutions given by Euler. Finally, we take the Knight’s Tour Problem to m-by-n chess-board. According to the spectral of the precinple to legal moves and some knowledge about Graph theory we can obtain the solutions of Knight’s Tour Problem on 3-by-4 chess-board 8-by-16 chess-board and 16-by-16 chess-board,and obtain a conjecture to Knight’s Tour Problem on 8-by-8 chess-board(m>2,n>2).

吴英、李传文

数学

Knight’s Tour Problem 哈密尔顿路 哈密尔顿圈 同构图 图的对称性

Knight’s Tour Problem Hamilton path Hamilton cycle isomorphic graph the symmetrics of graphs

吴英,李传文.关于Knight’s Tour Problem 的图论解法[EB/OL].(2006-10-31)[2025-08-18].http://www.paper.edu.cn/releasepaper/content/200610-578.点此复制

评论