计算机2011组合数学—CHO1节.ppt

* 当n=4k+2,所谓的单偶数的情况。 首先把n×n的方阵分成上、下、左、右四个(2k+1)×(2k+1)的方阵,为了表达方便，依次把左上、右下、右上、左下的方阵编号为A,B,C,D。 采用连续摆数法，把1～(2k+1)2放在A中做成第一个幻方；把(2k+1)2 ＋1～2(2k+1)2放在B中成第二个幻方。 * 把2(2k+1)2＋1～3(2k+1)2放在C中成第三个幻方。 把3(2k+1)2＋1～4(2k+1)2放在D中成第四个幻方。 然后，在A的各行从第1列开始向右取m个(m=(n-2)/4)方格，但中间一行（k+1行）从第2列开始。 把这些方格中的数字与D中相应位置的数字对换。 在C中各行最后一列右起向左各取m－1个方格，把这些方格中的数字与B中相应位置的数字对换。最后，就得到了幻方。 * * 例1.4 构造6阶幻方 1 5 9 28 32 6 7 2 33 34 26 21 22 17 12 19 23 27 10 14 8 3 4 35 30 36 29 13 18 31 24 25 20 15 16 11 A C D B m=1 * 1 32 9 28 5 6 7 2 33 34 26 21 22 17 12 19 23 27 10 14 35 3 31 8 30 36 29 13 18 4 24 25 20 15 16 11 * （三）幻方的计数问题 3阶幻方 基本形式只有一种 经过旋转和翻转可获得8种变形 1 6 6 1 8 5 7 7 5 3 9 2 2 9 4 4阶幻方 分类枚举 基本形式有880个 变形有7040个 5 阶幻方 基本形式有275305224个 6 阶及以上幻方 即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值范围 * * §1.2 拉丁方问题 * * 拉丁方是另一类典型的组合数学问题 n阶拉丁方定义为由数字1,2,…,n构成的n×n的方阵，使得在每1行、每1列中每个数字都恰好出现1次。 拉丁方存在性问题 * * 2阶拉丁方是存在的 1 2 2 1 * * n阶拉丁方是存在的 构造方法如下： 第1行为（1,2,3…,n） 第2行是(2,3,…,n,1)，… 第k行为(k,k+1,…,n,1, …,k-1)，…， 第n行为（n,…,3, 2, 1）。 * 例1.5 设计一个药物临床试验以测试五种药物对人体的药效。这五种药物编号1,2,3,4,5。然后选取5个人，并给每人不同的药。为了消除个体对药物的反应偏差，要求在连续5天里进行测试，每人每天吃一种药物。而为了消除服药时间造成药效的偏差，要求2个人不能在同1 天吃相同的药。 * 最后满足要求的实验是要形成由1,2,3,4,5构成的5×5的方阵，其中每行每列中没有相同的数字，即5阶拉丁方的构造问题。 * 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 1 2 3 4 5 行（人） 列（天） 例 36军官问题 有36名军官来自六个不同的团，具有六种不同的军衔，而且每个团每种军衔的军官各有一名，能否把他们排成一个6?6方阵，使得对每一个团与每一种军衔，在每一行或每一列都有一位军官来自这个团，也都有一位军官有此军衔？ 是由Euler首先提出的，实际上是组合设计中的正交拉丁方问题，属于构造问题。 猜想？6、10、。。。。 将这36名军官排成6×6方阵, 使得 1)每行每列都有任一军团的军官 2)每行每列都有任一军衔的军官. i :军衔, j :军团, 军官对应数偶(i, j), i, j?[1,6] 问题等价于构造数偶(i,j)排成的6阶方阵, 使得 1) 数偶第一个数字构成拉丁方; 2) 数偶第二个数字构成拉丁方; 3) 每个数偶只出现一次. 两个拉丁方称为互相正交，即正交拉丁方. 定义:设A=(aij)n×n,B=(bij)n×n是两个n×n拉丁方. 令C=((aij, bij))n×n,若C的n2对数偶互不相同, 则称A与B正交. 上述是两个3阶正交拉丁方。2阶哪？ 36军官问题即不存在6阶正交拉丁方。 6猜想不对。 对于只有9个军官的类似问题有解： * §1.3 涂色问题 在实际应用中，很多计数问题都可抽象成涂色问题。 作为典型的组合计数问题，根据涂色问题难度的不同，将反映出各