关于knight’s tour problem 的图论解法new

《关于knight’s tour problem 的图论解法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn关于Knight’sTourProblem的图论解法吴英，李传文兰州大学数学与统计学院，甘肃兰州（730000）摘要：本文通过分析欧拉所给出的Knight’sTourProblem的解法,结合哈密尔顿路和哈密尔顿圈的相关知识，得出其解法对应着二部图中的一条哈密尔顿圈。由此再充分利用8×8棋盘所对应的8×8表格的对称性及同构图的特性，对欧拉所给出的Knight’sTourProblem的解法作了进一步的探讨，得出了以欧拉的解法为基础的以任一棋格为骑士周游起点的另外一系列解法。最后，把Knight’sTourProblem推广到了

2、m×n棋盘上，考虑到移动规则的特殊性，利用图论的相关知识，得到了3×4、8×16和16×16棋盘上的Knight’sTourProblem的解法，同时给出了8m×8n（m＞2,n＞2）棋盘上Knight’sTourProblem的猜想。关键词:Knight’sTourProblem哈密尔顿路哈密尔顿圈同构图图的对称性中图分类号：O157.61问题的提出及有关理论Knight’sTourProblem是由印度棋手在大约公元前200年时直观地提出并解决的，该问题用现代语言描述的话，仍是在一个具体的图中找寻哈密尔顿圈的问题。其中，图G中的哈密尔顿圈指的是经过图G中每个顶点且只经

3、过一次的闭迹；而图Ｇ中哈密尔顿路指的是经过Ｇ中每个顶点且只经过一次的开迹。Knight’sTourProblem：给出一个8×8棋盘，用一个棋子代表骑士。一个骑士从当前位置通过向垂直方向移动2格，水平方向移动1格，或向垂直方向移动1格，水平方向移动2格的方式移动，那么，是否存在这样的可能：让骑士能够落在棋盘的每一格上恰好一次，而又不违反规则呢？这样的旅行称为骑士周游（knighttour）。还可以要求一个骑士周游具有这样的性质：从最后一格移到第一格时，仍满足一个合法的骑士移动，具有这种性质的骑士周游称为重复周游（Reentrant）。[1，2]在给出该问题解法之前，我们先

4、介绍如下定义、定理及相关理论。定义1在图G中，如果一条边的两端点相同，就称它为环（loop）。定义2设G是无向图（该图中的每条边都没有方向），x∈V(G)的顶点度（vertexdegree）定义为G中与顶点x相关联的边的数目（一条环要计算两次）。定义3两个图G=(V(G),E(G),ψG)和H=(V(H),E(H),ψH)称为同构的（isomorphic）,记为D≌H,如果存在两个双射θ:V(G)→V(H)和Φ:E(G)→E(H)使得对任意a∈E(G),ψG(a)=(x,y)当且仅当ψH(Φ(a))=(θ(x),θ(y))∈E(H).映射对（θ,Φ）称为G和H之间的一个同

5、构映射(isomorphicmapping).定义４若无环图的顶点集可以划分为两个非空子集X和Y（其中∣X∣=m和∣Y∣=n）,使得X中任何两顶点之间无边相连并且Y中任何两顶点之间也无边相连，则称该图为２部*分图(偶图，bipartitegraph或bigraph),记为Km,n,{X,Y}称为２部划分(bipartation).定理1在8×8棋盘中，令aij表示第i行第j列公共的棋格（1≤i,j≤8），akl表示第k行第l列公共的棋格（1≤k,l≤8）。由移动法则可知，从aij到akl是合法的移动，当且仅当︱i-k︱=1,︱j-l︱=2或者︱i-k︱=2,︱j-l︱=1

6、.证明：由于aij表示第i行第j列公共的棋格，akl表示第k行第l列公共的棋格，如果从aij到-1-http://www.paper.edu.cnakl是合法的移动，则其必然是向垂直方向移动2格，水平方向移动1格，或向垂直方向移动1格，水平方向移动2格的方式移动，所以︱i-k︱=1,︱j-l︱=2或者︱i-k︱=2,︱j-l︱=1。反之，如果︱i-k︱=1,︱j-l︱=2或者︱i-k︱=2,︱j-l︱=1，则表明从aij到akl必然是向垂直方向移动2格，水平方向移动1格，或向垂直方向移动1格，水平方向移动2格的方式移动，显然满足移动法则。□另外，当︱(i+j）-(k+l)

7、︱为偶数时，aij到akl绝不是合法移动；也就是说，只有当(i+j）与(k+l)奇偶性不同时，aij到akl才可能是合法的移动。把每个棋格看作某个图G的顶点，并且给每个顶点分别标上对应的标号aij，那么只有当(i+j）与(k+l)奇偶性不同时，顶点aij与akl之间才可能存在一条公共边；也就是说，当(i+j）与(k+l)奇偶性相同时，顶点aij与akl之间不存在公共边。所以，我们可以根据(i+j）的奇偶性把顶点归类为两个不同的顶点子集M，N，从而在此意义下8×8棋盘可被视为二部图，在同构的意义下该二部图是唯一的，记作*K32，