摘要
研究了在n×n的正方形棋盘中,骑士马走非正规马步(r,s)、r≥1、s>2(或称广义马步),是否能经过棋盘中每个点一次,且仅一次又回到出发点的问题,即广义马步哈密顿圈问题.论文首先给出了已有的研究成果,然后从理论上证明了在n×n,n≤r+s+1的正方形棋盘中不存在广义马步哈密顿圈.最后用实证的方法,提出了在n×n,n≥2(r+s)的棋盘中存在广义马步哈密顿圈的猜想,并利用实证与链接构造法,证明了对于(r=1,s=4)的广义马步情况,当n≥10时,存在广义马步哈密顿圈.
This paper is about the research on knight's circuits with irregular moves (r, s), r ≥ 1, s 〉 2, on square hoards. Knight's circuit means the knight moves to every square on the board exactly once and then back to the start, what is a Hamil- ton circuit. First the paper gives the results already made on this field, then we proof that there is no knight's circuit on a board equal to or smaller than (r+s + 1)×(r+s+ 1). Afterwards the results of practical research are presented to show that there are knight's circuits on boards 2(r+s)× 2(r+s). At last we make the supposition that there exists a knight's circuit on boards n×n with n≥2 (r+s) and proof by the method of connecting boards that it is true for a knight with move (r=,s=4).
出处
《小型微型计算机系统》
CSCD
北大核心
2005年第9期1551-1555,共5页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(79970003)资助.
关键词
骑士旅游圈
哈密顿圈
图论
knight's circuit
hamilton circuit
graph theory