正方棋盘中广义马步哈密顿圈问题的若干研究结果  

Research on Knight's Circuit with Irregular Moves on Square Boards

作　　者：宁安琪[1] 宁宣熙[1] 

机构地区：[1]南京航空航天大学经济与管理学院,江苏南京210016

出　　处：《小型微型计算机系统》2005年第9期1551-1555,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(79970003)资助.

摘　　要：研究了在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）.

关 键 词：骑士旅游圈 哈密顿圈 图论 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]