



下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、例1:下图是一个3X3的数字拼图。13265478图1它要还原成图212345678图2将问题一般化,在M*N的方格里有M*N-1个不同元素和一个空元素,只有空元素可以与上下左右相邻的元素交换位置。M*N方格中M*N-1个元素和一个空元素的位置确定一个图形。拼图游戏的问题是:一个图形经过一连串的交换能否得到另一个图形,如何得到。从交换方式的可逆性看出这种关系满足等价三性质,如果图形A通过交换变成图形B我们则称它们是等价的。把M*N-1个元素用1至M*N-1编号,空元素编号0。然后展成一个排列。每个图形对应一个排列。确定了展开方式,图形和排列是一一对应的。这里用到的展开方式是行优先的顺序(其他方
2、式展开也能到相应的结果)。将例1的两个图形展开有:图1对应1 3 2 6 0 5 4 7 8,图2对应1 2 3 4 5 6 7 8 0。定理1:图形A与图形B等价的充要条件图形A的排列的逆序数加上0元素行号和列号的奇偶性等于图形B的排列的逆序数加上0元素行号和列号的奇偶性。为方便表述,把图形排列的逆序数加上0元素行号和列号的奇偶性称为图形的奇偶性。先看定理1如何起作用,图1:展开的排列 1 3 2 6 0 5 4 7 8,它的逆序数为8,0元素行号为2,列号为2。逆序数加行号,列号的奇偶性为偶。图2:展开的排列 1 2 3 4 5 6 7 8 0,它的逆序数为8,0元素行号为3,列号为3。逆
3、序数加行号,列号的奇偶性为偶。两个图形的奇偶性相同,根据定理1判断它们等价。首先证明必要性,即如果图形A与图形B等价,则图形A的奇偶性等于图形B奇偶性。0元素和某个元素交换位置,则排列的逆序数的奇偶性就改变一次。交换后0元素的行号或者列号会加1或减1,即行号,列号之和的奇偶性也改变一次。这说明拼图的交换方式不改变图形的奇偶性,也说明拼图中至少有两组等价类,奇偶性不同的图形不等价。下面证明充分性,如果图形A的奇偶性等于图形B的奇偶性,则图形A,B等价。如果证明了拼图只有两组等价类,从必要性的证明过程可知,奇性图形是一组等价类,偶性是一组。从而证明了充分性。先考虑一般的排列1 2 3 . N。某个
4、元素连续与后面M相邻的元素交换位置,称为向后M步移动。如排列:1 2 3 4 5 6。元素2的向后3步移动,排列变成1 3 4 5 2 6。同样的方式定义向前M步移动。如果排列A能够通过有限向前M步移动和向后M步移动变成排列B,称排列A与排列B M步等价。容易看出这也是等价关系。引理1:任何一个1至N的排列M步等价于1 2 . N-M(.)。括号里是N-M+1至N的某个排列。证明:如果N=M,这显然成立。假设N=k时成立,下面证明k+1的情况。1元素的位置记为i情况1:假设i=1,显然,余下的元素减1,就变成N=k的境况,得证。情况2:如果1iM,则元素1有限次向前M步移动,使i有1=i=M,
5、可变成情况1或2。从而得证。当M=2时,只有两组等价类。由于移动不改变排列的奇偶性,从而奇排列是一组等价类,偶排列是一组等价类。考虑N*M的拼图。当N=M=2,穷举法可证明只有两组等价类。当N,M不同时为2时,设N不等于2(如果N等于2,M不等于2可颠倒行列讨论)。只考虑第二行最后一个元素是空元素的情形,因为空元素在其他位置总可以等价某个空元素在第二行最后一个元素的图形。不考虑空元素以之字形方式展开图形,即第一行最后一个数字和第二行倒数第二个数字相连。如:12435图3展开成1,2,4,5,3。下面证明两行拼图的交换方式可以实现排列的向前2步和向后2步移动。要实现元素a的向前2步移动,则可顺着
6、展开的方式循环移动拼图,使a在第一行第二列的位置,使空元素在第二行第二列的位置,此时可把元素i可与空元素对换。然后再沿着展开的顺序还原拼图。例如:图3的元素4向前2步移动。可以如下操作,24513图425143图541235图6展开成4,1,2,5,3。实现了向前2步移动。使i在第二行第二列的位置,使空元素在第一行第二列的位置可以实现向后2步移动。根据引理1及,两行拼图可以分成两组等价类。假设M=k图形可以分成两组等价类,下面证明M=k+1,只需要证明任何M=k+1图形总等价于第一行元素为1 2 . N的某图形即可。如果这N个元素都在第一行,把空元素移到第二行,从上面的证明可知,交换两个不同的非空元素,图形的奇偶性改变,属于不同的等价类。N大于2,第二行就有两个非空元素可供交换。所以两行图形可以等价与第一行为1 2 . N的某个图形。如果1至N的某个a元素不在第一行,设它在第i行。把空元素移动到i行,这样第i行和第i-1行可以看成M=2的图形。可以把a移动到第i-1行,并保证第i
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 企业财务报表分析与投资价值评估咨询合同
- 2025年大数据技术工程师考试试题及答案
- 2025年的基层治理理论与实践考核试卷及答案
- 2025年心理健康与疾病管理职业资格考试试题及答案
- 果树病虫害综合防治与绿色防控
- 【课件】命题、定理、证明 课件 2024-2025学年人教版数学七年级下册
- 2型呼衰患者的护理查房
- 旅游车队租赁运营管理担保协议
- 新材料研发基地厂房转租及科研成果转化合同范本
- 工伤死亡赔偿协议书
- 饮食与营养试题及答案
- 公司岗变薪变管理制度
- 影像科招聘试题及答案
- 关于中心医院“十五五”发展规划(2025-2030)
- 2024年江苏省昆山市事业单位公开招聘教师岗考试题带答案分析
- 2025年六五环境日生态环保常识及法律知识有奖竞答题库及答案(共90题)
- 上海市社区工作者管理办法
- 湖南师范大学学位英语历年考试真题
- 中医肿瘤临床路径
- 中考数学《分式及分式方程》计算题(附答案)
- 用人单位用工备案花名册
评论
0/150
提交评论