染色法在组合数学中的应用.docVIP

棋盘染色法的分类与应用 华师大二附中 王崇熙 指导教师 施洪亮 摘 要 组合数学是数学应用中非常重要的一门分支，染色法是其中非常重要的一种方法，随着染色法的发明，一大系列难解的组合问题都得到了非常简便地解决，本研究着重将过去比较模糊的染色法的概念做了一个系统的分类，创造了一种可行的发现新的染色方案的比较系统的思想，并将普遍的二维染色法做了一个推广，解决了一个三维中的组合问题。 研究得出的主要结论为： 二维染色法的分类： 双色染色法（国际象棋盘染色法）； 多色规则染色法（高度对称）； 不规则染色法（根据问题灵活转变）； 三维染色法的初步结论：三维染色法基于二维的一些情况进行推广，解决了一个较为困难的三维覆盖问题。 关键词： 　　染色法；博弈问题；覆盖问题；分类；推广 一、引言： 组合数学是一门研究离散的量的变化规律的学科。组合数学的方法千变万化，没有一种适用于所有问题。这些方法有一些共同点： 1、所有的方法追求的是简单与清晰。 2、所有的方法都较难想到，而说破了却又很简单，解决问题后经常有一种恍然大悟的感觉。 作为一名数学爱好者，很多人喜欢解组合数学的问题，其中染色法是颇受欣赏的方法。但是在中学或大学数学教与学的过程中缺乏对染色法的系统研究，这使得人们很难学习与掌握该方法。做题时并不能真正的掌握问题的本质，在下一次遇到可能用染色法解决的问题时并不能很好地找到正确的解决方法。我们不妨来看一下过去使用染色法解决问题的过程，一道问题的解答一半多以这样开头：“这道问题我们用染色法来解决，把点A涂上红色……，如图，分析一下各类不变量，我们得到……”。在做了大量的练习之后，笔者初步掌握了棋盘染色方法，对该染色法进行了分类，并研究了该染色法在解决组合问题中的具体应用。 二、棋盘染色法的分类: 棋盘染色法是一类借助国际象棋棋盘通过染色解决组合问题的解踢方法的简称。经过对染色法问题的系统研究，分析每种方法的解题特点，经过归纳整理，可将棋盘染色法大致分为以下几类： 双色相邻染色法（国际象棋棋盘染色法） 这个染色法的基本构图（如右图），正如它的名字所言，是分析问题的奇偶本质。我们可以发现这种染色法得到的一个图像有以下几个特点： 这张图具有高度的对称性，不管是平移还是旋转或是翻折，都无法改变它的性质。 这张图总体来说黑白格子的个数相等，关键的一点是，所有的黑格都只与白格相邻，同样所有的白格都只与黑格相邻。 于是，在这张图中任何一条格子到格子之间的路径都经过几乎相同的黑白格数，至多相差一个；在这张图内任取一块以黑白格子的边界为边界的区域所包含的黑白格数也至多只相差一个，这就导致了一个很强的性质。 多色染色法 多色染色法的基本构图（右图为三色染色）： 该构图的特点如下： （1）类比与双色染色法，多色染色法也有高度的对称性，只是缺少了翻折对称性。 （2）这张图中所有颜色的格子的个数全都相同，但各种颜色的格子只与两种颜色的格子相邻。 在这类图中没有二色染色中非常强的性质，但令人意外的是，它却能解决不少有关于模n性质的问题。 不规则染色法 不规则染色法的构图（这种染色法的构图不唯一，右图为一个简单的例子）： 特点如下： 灵活多变，没有明确的形式。 问题的解决明快，简单，但不容易想到。 右图在用这个图形 覆盖时就有非常有用的特点，永远覆盖到奇数个黑格。 三、棋盘染色法的推广——三维染色法 一般来说，棋盘染色法都只在二维的范围内应用，但若将棋盘一个一个叠放在一起就构成了一个三维的图形，这就导致了三维染色的可能。三维染色法是基于二维染色法的一些情况进行推广，方法更多变。在后文中有一个较为成功的染色法的例子，它解决的是三维覆盖的问题。 四、棋盘染色法的应用 1、双色染色法的应用 问题1 一个5*5的房间网，相邻房间是相通的，问能否从箭头房间进入走遍整个房间网并且不重复的走入一个房间？ 右图黑线就是这样一条路径。 这个问题的可以这样来考虑，5*5=25是一个奇数，可以利用染色法尝试，由前面所推得的性质3得到：这条路径所经过的黑白格的格数相差至多为1，但是若走遍整个房间网的话，黑白格数不是也只相差1吗？又由题意发现，起点在黑格，无论终点在黑格还是白格，都无法使白格数多于黑格数，于是，不存在这样的路径。有这个问题了以后，自然的想到了推广，若是用1*2的小方块覆盖棋盘的话会有什么结果，巧的是，有一个著名的银行家曾经提出过类似的问题，下面的问题就来自那位银行家。 问题2 一个8*8的格子纸，去掉对角两格，是否能用1*2的方块来覆盖它？ 第一个思路就是看总格数能否被2整除，答案是可以。这个问题曾经困扰过许多人，在没有染色法以前，一般想到的都是半枚举的做法，这个做法一般为（如右下图），一行一行的去试，根据行与行之间的关系来推导出