象棋吧 关注:276,106贴子:5,995,465

【杂谈胡扯】广义棋盘中的象棋马步哈密顿回路浅析

只看楼主收藏回复

1楼喂小白兔


1楼2011-11-23 14:12回复
    定理内容:在M×N 的广义棋盘中, 当M、N均≥5, 且M与N乘积为偶数时, 均存在象棋马步哈密顿回路。


    2楼2011-11-23 14:14
    回复
      象棋马步哈密顿回路。先给点解释嘛


      3楼2011-11-23 14:38
      回复
        啥解释?


        4楼2011-11-23 14:40
        回复
          定义1:已知其中哈密顿圈解的棋盘,称之为简单棋盘。
          定义2:对于一m*n的简单棋盘A,若其哈密顿圈可在一边界(维数为m或n)上与另一简单棋盘B的哈密顿圈合并为新的哈密顿圈,称A、B可链。
          定义3:简单棋盘中距边界最近的两行点集称为边界层。相邻的两个简单棋盘(维数相同)中相邻边界层构成的区域称为链接区。链接区内跨越边界的马步线称为链接边。
          定义4:链接区中由已知的哈密顿圈上的回路线与链接边构成的四边形称为链接四边形。


          5楼2011-11-23 15:03
          回复
            引理1:两个简单棋盘可链的充要条件是,链接区内存在由两条链接边和已知哈密顿圈上的回路线构成的四边形。
            证明如下:
            充分性:若链接区存在一个四边形, 则只能是一个由简单棋盘A中哈密顿圈上的一条回路线,简单棋盘B中哈密顿圈上的一条回路线及两条链接边构成的四边形。原因如下,考虑链接区内A、B各自的点集,链接A、B的边只能是链接边。因此链接区如果存在四边形, 该四边形只能
            由两条链接边及两个哈密顿圈上的各自一条回路线交错构成的链接四边形,考虑其马步性,充分性得证。
            必要性:假设A、B链接后形成的C是哈密顿圈。考虑链接边QW、ER(Q、E∈A,W、R∈B)与原A、B上未参与C的剩余边构成的是N边形(N>4), 则QW或ER之间必有其他点Z。因为Z存在,故A、B链后形成的C不可能通过各自点集一次且仅一次。与假设矛盾,必要性得证。


            6楼2011-11-23 15:28
            回复
              6楼说明的事情其实很简单,即两块存在哈密顿圈的,可拼合的棋盘拼在一块,可以生成新的哈密顿圈,证明的过程即阐述了构造方式。


              7楼2011-11-23 15:30
              回复
                推论:m*n与n*q的简单棋盘链接后形成(m+q)*n简单棋盘在维度(m+q)和n上,依旧可链。


                8楼2011-11-23 15:45
                回复
                  首先,5×6, 6×6, 7×6, 5×8, 6×8, 7×8的简单棋盘都是存在的(其存在性诸位可以验证,不赘述)下面证明,由这六个可链的简单棋盘可以链接出M*N大小的简单棋盘。这里,M≥10,N为偶数,N≥12。
                  对于≥12的偶数N,可以找出两个非负整数a和b,使得N=6a+8b。
                  又:对于≥10的自然数M,可以找出三个非负整数a, b 和c, 使得M=5a+6b+7c。
                  此二命题用数学归纳法即可简单得证,不赘述。
                  


                  9楼2011-11-23 16:00
                  回复
                    那么,对于M*N大小棋盘(M≥10,N为偶数,N≥12),由上可知,均可由5×6, 6×6, 7×6, 5×8, 6×8, 7×8的简单棋盘链接构造。举例如13×14棋盘,即为 6×6, 7×6, 6×8, 7×8棋盘链接而成。
                    特别的,再验证数个遗漏棋盘即可完成全部证明,不赘述。(我没验证,不过估计应该是存在哈密顿圈的)


                    10楼2011-11-23 16:11
                    回复
                      @impr


                      11楼2011-11-23 16:13
                      回复

                        如图,即是14×11棋盘的哈密顿圈,阐释了构造方法和生成过程,图中的马步虚线即是链接边。


                        12楼2011-11-23 16:18
                        回复
                          顶贴…纯地…


                          13楼2011-11-23 16:28
                          回复
                            9*10



                            IP属地:北京14楼2011-11-23 16:32
                            回复
                              9*10的,之前那贴给出了一个图解,事实上已经证明了


                              15楼2011-11-23 16:34
                              回复