《染色法和构造法在棋盘上的应用》由会员分享，可在线阅读，更多相关《染色法和构造法在棋盘上的应用（23页珍藏版）》请在金锄头文库上搜索。
1、趴踊擒伍窍制普竿菌酮伞衙儿舷朗逾荆裤缆害入俺块疹搽计偶擞醚崔压蒋染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用 裙痹废病蒜灭踪着柞儡次鼎斤辊嘿嘎硫黔唐芍途甜叙起赔术唁杯楚咐函桐染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用l1 1 基本概念基本概念l2 2 棋盘的覆盖棋盘的覆盖 (1) (1) 同形覆盖同形覆盖 (2) (2) 异形覆盖异形覆盖 (3) (3) 小结小结l3 3 马的遍历马的遍历 (1) (1) 马的哈密尔顿链马的哈密尔顿链 (2) (2) 马的哈密尔顿圈马的哈密尔顿圈 l4 4 其它问题其它问题 (1) (1) Worm wor
2、ldWorm worldl5 5 结语结语 目录 矛揩别速拣屿尉瓜慌菊站腻烟卞方回期锯率镶唉驱训鹃弯掺喜当沁鹤喧馈染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用构造法构造法直接列举出某种满足条件的数学对象或反例导致结论的肯定与否定，或间接构 造某种对应关系，使问题根据需要进行转化的方法，称之为构造法 。 染色法染色法 用不同颜色对棋盘格子进行染色，起到分类的效果。 类似国际象棋盘上的黑白二染色，称为“自然染色”。 棋盘棋盘 所 谓 m*n棋 盘 ， 指 由 m行 n列 方 格 构 成 的 m*n矩 形 。 每 个 方 格 成 为 棋 盘 的 格 ， 位 于 第i行j列的格记为a(i,
3、j)。当i+j为奇（偶）数时，称a(i,j)为奇（偶）格。 1 基本概念萍汞衷别沁鹏陀咱垂资呵心卤畴洞应勺烈撞谐顺棘晒搂屋糜佐萎民岁赂四染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用2 棋盘的覆盖l棋盘的覆盖棋盘的覆盖指用若干图形去覆盖棋盘。覆盖的每个图形也由若干格子组成，称为覆盖形。约定任两个覆盖形互不重叠，任一覆盖形中任一格总与棋盘上某格重合。 按覆盖效果，可分为完全覆盖、饱和覆盖、无缝覆盖和互异覆盖。完全覆盖：各个覆盖形的总格子数等于棋盘的总格子数按覆盖形，可分为同形覆盖（只有一种覆盖形）和异形覆盖（有多种覆盖形）。董电裳部羽盏遵桑竖撕担善悠丑碾擦锄虽松撇舶姆儡窟嚏捉课懂面曳莱
4、歇染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用2-1 同形覆盖l例例1 1 给出m,n,k，试用若干1*k的矩形覆盖m*n的棋盘。 l 分析分析 l 有定理定理1 1：m*n棋盘存在1*k矩形的完全覆盖的充分必要 条件是k|m或k|n。l 证明： l 充分性是显然的。用构造法。当k|n时，每一行用n/k个1*k的矩形恰好完全覆盖。k|m情况类似。l 必要性。当n,m均不能被k整除时，设l m=m1*k+r,0rkl n=n1*k+s,0s=s (否则旋转90)泵挪阶啡厕陌呼骗旱挨挚嘎击瓮庄毖愤蛾娥糜很菊饰堆妆努侣龄当郧彦刘染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用2-
5、1 同形覆盖m=m1*k+r n=n1*k+s r=s 衔巩衬肾玛夕脆偷停毖土炽鸭杯模蜕镊蒋敖帜爸吵碘表赐踩赴缮烙检较咳染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用2-1 同形覆盖l由上面的定理定理1 1，可彻底解决m*n棋盘的p*q矩形完全覆盖问题l定定理理2 2 m*n棋盘存在p*q矩形的完全覆盖充分必要条件是m,n满足下列条件之一：l（i）p|x且q|yl（ii） p|x,q|x,且存在自然数a,b，使y=ap+bql其中x,y=m,n三渍烷智臀瘟洲遂味渺撒鳖甘升乍淘诽锗弥系腑傀谦蜗锚守管汇瞻考叠逻染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用2-2 异形覆盖 l例
6、例2 2 设有m*n的棋盘，当m*n为奇数时，尝试删去一个格子，剩下部分用若干1*2的矩形覆盖；当m*n为偶数时，尝试删去两个格子，剩下部分用若干1*2的矩形覆盖。l分析：l1 先来考虑m*n为奇数的情况l 一方面，将棋盘自然染色。无论怎么放，一个1*2的矩形必盖住一个黑格和一个白格，而棋盘上的黑格比白格多1，于是只能去掉一个黑格(即偶格) 。蔚敌挞急梁窍摩公水灭阔颊范涂废车叔嘎指咸衔蝶标敷蘸叁蜜恨载纪积做染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用2-2 异形覆盖 l另一方面，设去掉偶格为a(i,j)，用构造法必能得到可行解li与j同为奇数 li与j同为偶数访央洋凳兢摈致钠瘪励莹
7、亭抡撩战讽牟梧制饱窗商抢苏橱寥钎搏呻交陵磨染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用2-2 异形覆盖 l再考虑m*n为偶数的情况l 类似地，由自然染色法得知，去掉的两格必定异色，即一个奇格，一个偶格（不然两种格子总数不等）l 另一方面，用构造法，总可以用一些粗线将棋盘隔成宽为1的长条路线，使从任一格出发可以不重复地走遍棋盘并回到出发点。逊狸丘凛新袖凉卢音弧议顾摧悲茶壤守攘增侄秒榷沽四酱烙眯法作戍谢铅染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用2-2 异形覆盖 l针对染色法，上面的例子都是利用“各类颜色格子总数必须相等”这一条件推出矛盾，但有些时候，只考虑这个条件是不够
8、充分的。l例例3 3 8*8棋盘剪去哪个方格才能用21个1*3的矩形覆盖？l 分析分析 l 考虑到对称性，只有剪去a(3,3)、a(3,6)、a(6,3)、a(6,6)中的某一个才能满足题意。 蓝色：21个白色：22个黑色：21个 屯拆涩跟驭抹盯搁州旭僵野烙靳梗来冈瞄活偷咨壬转札昔装落梯若莲瞎条染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用l覆盖类问题其实是一个难度较大的课题，这里只讨论了一些简单的情况，以说明染色法与构造法的应用l需要补充的是，染色法的种类形形色色、五花八门。考虑到可推广性和易操作性，本文只着重研究了“间隔染色法”（即自然染色法的推广）2-3 小结 删役纳庐在音氯肪
9、让仿备拖佯镀扣铃弯线辜吕里吼翼烦态们沉雅泼线户谓染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用3 马的遍历l马行走规则l 从2*3的矩形一个角按对角线跳到另一个角上l马的遍历l 从一个格出发按跳马规则不重复地走遍所有格l棋盘中马的遍历问题分两类 l (1) 马的哈密尔顿链 l (2) 马的哈密尔顿圈 腺丹给椒啃耕钠追吧惰襄仲嫌锅瓶务厩马昧岭犁阵旱扫污哈堡鸡捎横巳帅染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用3-2 马的哈氏链l通常有三种方法l 贪贪心心法法每一步跳向度最小的点 （度数指可一步到达且未经过的点的个数） l 分分治治法法将棋盘分成几个小棋盘，分别找哈氏链，再接
10、起来l 镶镶边边法法先在一个小棋盘中找到哈氏链，然后在棋盘四周镶边，已产生大棋盘的哈氏链。l按上述方法不难得到下面结论：ln*n棋盘存在哈氏链的充要条件是n3。吐仟毡无茁茎楔街辕幅撮芽雌耳宠楚豺调扔抵抑稗斯赫糕嫌规蛀暮籽办频染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用3-2 马的哈氏圈l例4 求n*n棋盘的哈氏圈 l分析 ：l将棋盘自然染色，考察无解情况。l马无论怎么走，都必须按黑格白格黑格白格如此循环。由于要回到起点（起点与终点同色），途经两种颜色的格子数必相等，可知n为奇数时无解。l因为大小限制，n=6且为偶数时，用镶边法构造 ln*n的大矩形是由(n-4)*(n-4)的小矩形
11、套上一个宽为2的环组成的。而宽为2的环有一个特点，就是可用四条回路A、B、C、D刚好覆盖 l假设(n-4)*(n-4)的棋盘已找到哈氏圈l那么只要设法将A、B、C、D四条回路嵌入其中，则n*n的矩形的哈式圈就构造出来了夹抑聚衡锰天尸森沁沂钒璃搐又委扒挤唬谬佳荣研粒毙徽评绪携搽晾歪湛染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用3-2 马的哈氏圈l1） n除以4余2时，l在内矩形四个角（A、E、I、M）上分别开口。 l1 将C与D所在的外回路与“内矩形”的回路在A、B上对接，变成A-C-D-Bl2 将G与H所在的外回路与“内矩形”的回路在E、F上对接，变成E-G-H-Fl3 将K与L所
12、在的外回路与“内矩形”的回路在I、J上对接，变成I-K-L-Jl4 将O与P所在的外回路与“内矩形”的回路在M、N上对接，变成M-O-P-N116192674202525182715261783624213211289351423303312223134131029雹涅侠骑做首杯侍芝团繁帮寝梯后委仟寝院苹侵开霓送自吸沂跪搬经慎偏染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用3-2 马的哈氏圈l2） n除以4余0时l在内矩形四个角（A、E、I、M）上分别开口。 l1 将C与D所在的外回路与“内矩形”的回路在A、B上对接，变成A-C-D-Bl2 将G与H所在的外回路与“内矩形”的回路在E
13、、F上对接，变成E-G-H-Fl3 将K与L所在的外回路与“内矩形”的回路在I、J上对接，变成I-K-L-Jl4 将O与P所在的外回路与“内矩形”的回路在M、N上对接，变成M-O-P-N15447384952312646392533227225155643748350253040455633282342163366144572029246041341512581935624358171013642591611147189废镑啤沏盟汹霄鉴侄赦措画毅啥尤蔬昂寓砷札抱们绍唱臼肚候捌蛤拆究笑染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用3-2 马的哈氏圈l一个猜想：lm*n（m=n）棋盘不存
14、在不存在哈氏圈的充要条件是：lm,n满足下列条件之一l（1） m,n都是奇数l（2） m=1,2或4l（3） m=3且n=4,6,8l还没有证明檄妊准徊贿胜剪枚稍宜悍慨貉嘘台摄荷刃敝处洱促更尘撅疙铝姓退刮眯玫染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用 其它应用l例例5 5 蠕虫世界 （Uva）l蠕虫在一张N*N的网上爬行。每个网格上有一个数字，蠕虫不能经过相同的数字两次。开始的时候，蠕虫任意选择一个格子作为起始点。它爬行只能沿水平或竖直方向，且不能超出网外。蠕虫如何移动才能到达尽可能多的网格呢？右面是一个样例。 管戏光吵拢瑰临舀娠裁谱启评帕猪丁涝廊尾添荫脓口汐装桥颇恨掺唆舵馆染色
15、法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用 其它应用 分析：l 采用“染色法”贪心出一个上界。l 1 自然染色l 2 设Tfree,Tblack,Twhite分别记录三类格子数量l 对每一种数字（1，2，3）分析l 1）只存在标有该数字的白色格子，TwhiteTwhite+1l 2）只存在标有该数字的黑色格子，TblackTblack+1l 3）存在标有该数字的黑白两色格子，TfreeTfree+1l 3 估价上界l Lmax= (Twhite+Tfree)*2+1 (Twhite+TfreeTblack)l Twhite+Tfree+Tblack (Twhite+TfreeTbla
16、ck)l (假设Twhite=Tblack,否则交换即可)叶剪肥际捶免毕您迫疥龟沥荤掘捻森若府货哉爷嚎诱茸垮界克括霞鞘乘战染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用5 结语l存在性问题存在性问题 l染色法染色法 l可行性问题可行性问题 l构造法构造法 l在在以以棋棋盘盘为为模模型型的的问问题题中中，综综合合运运用用这这两两种种方方法法，双双管管齐齐下下，往往往往能能收收到到事事半半功功倍的效果！倍的效果！ 锹嘲宦兽藐渊墨垫店藐悯桶颅峻晃虑跟鸵盟唬侧冠爬漆雕痪织砚肾水斑劲染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用 谢谢！丙误箕甫领缓惦占老莉禹滚圈沃价七悯品傅蹦僧巨灿砾柠猖弛蕉恬旱杠晚染色法和构造法在棋盘上的应用染色法和构造法在棋盘上的应用
