网页
资讯
视频
图片
知道
文库
贴吧
地图
采购
进入贴吧
全吧搜索
吧内搜索
搜贴
搜人
进吧
搜标签
日
一
二
三
四
五
六
签到排名:今日本吧第
个签到,
本吧因你更精彩,明天继续来努力!
本吧签到人数:0
一键签到
可签
7
级以上的吧
50
个
一键签到
本月漏签
0
次!
0
成为超级会员,赠送8张补签卡
如何使用?
点击日历上漏签日期,即可进行
补签
。
连续签到:
天 累计签到:
天
0
超级会员单次开通12个月以上,赠送连续签到卡3张
使用连续签到卡
09月24日
漏签
0
天
象棋吧
关注:
276,106
贴子:
5,995,465
看贴
图片
吧主推荐
视频
玩乐
1
2
3
下一页
尾页
43
回复贴,共
3
页
,跳到
页
确定
<返回象棋吧
>0< 加载中...
【杂谈胡扯】广义棋盘中的象棋马步哈密顿回路浅析
只看楼主
收藏
回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
1楼喂小白兔
送TA礼物
1楼
2011-11-23 14:12
回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
定理内容:在M×N 的广义棋盘中, 当M、N均≥5, 且M与N乘积为偶数时, 均存在象棋马步哈密顿回路。
2楼
2011-11-23 14:14
回复
收起回复
三军夺帅
八蹄踏雪
8
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
象棋马步哈密顿回路。先给点解释嘛
3楼
2011-11-23 14:38
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
啥解释?
4楼
2011-11-23 14:40
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
定义1:已知其中哈密顿圈解的棋盘,称之为简单棋盘。
定义2:对于一m*n的简单棋盘A,若其哈密顿圈可在一边界(维数为m或n)上与另一简单棋盘B的哈密顿圈合并为新的哈密顿圈,称A、B可链。
定义3:简单棋盘中距边界最近的两行点集称为边界层。相邻的两个简单棋盘(维数相同)中相邻边界层构成的区域称为链接区。链接区内跨越边界的马步线称为链接边。
定义4:链接区中由已知的哈密顿圈上的回路线与链接边构成的四边形称为链接四边形。
5楼
2011-11-23 15:03
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
引理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
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
6楼说明的事情其实很简单,即两块存在哈密顿圈的,可拼合的棋盘拼在一块,可以生成新的哈密顿圈,证明的过程即阐述了构造方式。
7楼
2011-11-23 15:30
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
推论:m*n与n*q的简单棋盘链接后形成(m+q)*n简单棋盘在维度(m+q)和n上,依旧可链。
8楼
2011-11-23 15:45
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
首先,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
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
那么,对于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
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
@impr
11楼
2011-11-23 16:13
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
如图,即是14×11棋盘的哈密顿圈,阐释了构造方法和生成过程,图中的马步虚线即是链接边。
12楼
2011-11-23 16:18
回复
收起回复
醉描蓝桥
九宫洛书
9
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
顶贴…纯地…
13楼
2011-11-23 16:28
回复
收起回复
闫六二
七星聚会
7
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
9*10
?
IP属地:北京
14楼
2011-11-23 16:32
回复
收起回复
齐地潇湘
遥遥领先
11
该楼层疑似违规已被系统折叠
隐藏此楼
查看此楼
9*10的,之前那贴给出了一个图解,事实上已经证明了
15楼
2011-11-23 16:34
回复
收起回复
登录百度账号
扫二维码下载贴吧客户端
下载贴吧APP
看高清直播、视频!
贴吧热议榜
1
S赛历届fmvp选手谁最强
1589730
2
华为秋季全场景新品发布会
1391565
3
黑神话IGN年度投票支持率暴跌
980420
4
我发S14版本新装备大伙打分
976347
5
战神5PC版MC评分94
876018
6
LOL玩家日系列皮肤曝光
732450
7
Xun和Wei疑似轮流打训练赛
668208
8
炉石国服回归指南
553449
9
KPL夏季赛最佳阵容候选名单
528330
10
以军空袭黎巴嫩492死1645伤
422709
贴吧页面意见反馈
违规贴吧举报反馈通道
贴吧违规信息处理公示