组合数学 绪论.pptx

绪 论;绪 论;绪 论;绪 论

组合数学研究的核心问题是“把有限个离散对象按一定规则或模式进行安排”，这种安排被考究地称为组态

（Configuration）。关于幻方的几个问题也正是组合数学要解决的问题，即组态的存在性问题、组态的计数问题和组态的构造问题。此外，还涉及组态的优化问题。;绪 论

1.组态的存在性

组合数学中解决组态存在性的方法很巧妙，其构思过程往往出人意料，让人拍案叫绝。其中，著名的例子就是众所周知的哥尼斯堡七桥问题。1736年，年轻的大数学家Euler将人们在娱乐中提出的一个数学难题抽象为点线构成的图及寻找走边的一笔画问题，并给出了精巧的解答，即七桥问题无解。由此引出了一门新型数学学科——图论。Euler也被后人誉为图论之父。;绪 论;绪 论

例2若用1×2格的骨牌铺砌去掉了两个对角处格子的8×8残缺棋盘，问能否用31枚骨牌恰将其砌满？

解答案是否定的。证明方法很巧妙，可以先将8×8棋盘黑白间隔染色，去掉的两个对角处格子不是同白，就是同黑。因此，8×8残缺棋盘剩余的64-2=62个格子中黑格数与白格数相差为2。反之，若设能用31枚1×2格的骨牌，每枚覆盖相邻的2个方格，恰将残缺棋盘砌满，则黑格数与白格数应该相等。这就产生了矛盾。因此，存在要求的覆盖。如果对不去掉对角处格子的64格8×8完好棋盘，则存在用32枚1×2格的骨牌恰将其砌满的许多方法。这时要讨论的就是确定有多少种不同覆盖方法的计数问题。;绪 论;绪 论;绪 论;绪 论;绪 论;绪 论;绪 论;绪 论;绪 论;绪 论;绪 论

4.组态的优化

优化问题是在一定的条件下找出一个(或几个)最优或较优的安排方案。有些组合问题求精确解是很困难的，所求结果有时只能给出一种接近的解。

例7把一个3×3×3的立方体木块切割成27个1×1×1的小立方块。如果切割过程中允许重新排列已切割木块的位置，求完成整个切割的最少次数。;绪 论

解这里的最优即指具有最少切割次数的方案，采用穷举方案并比较切割次数的方法一般不可取。本例的解法是先指出6次即可完成全部切割，即水平切2次，竖直、交叉各切2次。其次，可以证明少于6次不能完成题目???求的切割。事实上，对中心位置产生的小立方体而言，因其也具有6个面，且每个面都须被独立地切割一次才能出现。故至少需要6次才能切割完。;绪 论;绪 论;绪 论

组态的存在性、分类计数及构造，一般都不是互相独立的，它们常集中在同一组合问题中。一般而言，若一组合问题的存在性需要大量研究时，则其计数问题的难度将难以想象。但若一组合问题已有一特定的解，则还是有机会计算其解的个数或对其进行分类。