(组合数学)第5章区间设计.ppt

2011.11.09,1,组合数学第二部分讲课老师：张承钿,2011.11.09,2,第5章区组设计,2011.11.09,3,内容问题的提出拉丁方与正交的拉丁方域的概念Galois域GF(p)正交拉丁方的构造正交拉丁方的应用举例均衡不完全的区组设计区组设计的构成方法Steiner三元素Kirkman女生问题,2011.11.09,4,问题的提出有一块梯田种植3种不同的农产品A、B、C。由于高度、方位不同，所有其自然条件有差异。按图5-1的(a)种植，每种产品只在同层出现；而按图5-1的(b)种植，则每种产品只在同一方位出现；按图5-2种植，则每种产品即在同层出现，又同一方位出现。显然，按图5-2种植，实验结果较准确。测试4种轮胎，同一牌子在汽车不同位置磨损程度不同，所以每种不能只测试一个轮胎，用4辆小汽车A、B、C、D参加测试，如右图所示。这个测试的特点是，每一种品牌的轮胎都在不同的汽车和不同的位置作了安排。每种轮胎都用了4次。测试的次数也均衡，其中A、B、C、D是汽车的代号，矩阵的元素是轮胎的品牌代号。,2011.11.09,5,问题的提出再论梯田种植问题农作物类：、梯田高度：高、中、低日照方向：东、南、西进一步的问题：种子是买来的，三家种子公司都提供这些种子，价钱差不多三种农作物的出售价格也差不多，只是播种方式不一样实验的目的是比较出哪家公司的种子质量好，哪种作物产量高。？怎样安排实验分析一：下面方法是否可行如果把上面每块地（共九块）再分成三小块，每小块种上一家公司的作物问题：每个小块的面积太小的话，无法判别产量分成三次播种季节，每个季节种一家作物问题：分三个季节的话，时间太长分析二：下面结论是否成立种子公司生产水平高，它的种子质量好，即公司X比公司Y好，则X的种子A、B、C应该比Y的种子A、B、C都相应的质量好。农作物的产量不依赖于公司，即作物A比B产量高，则每家公司的作物A比B产量都高。,2011.11.09,6,问题的提出重新描述梯田种植问题农作物类：、梯田高度：高、中、低日照方向：东、南、西种子公司：、假如各个公司的实际产量如下：即：公司X的A作物产量最高？：有没有办法，只在一个季节内种植后，就能判别出结果？,2011.11.09,7,问题的提出重新描述梯田种植问题农作物类：、梯田高度：高、中、低日照方向：东、南、西种子公司：、在九块田分别种植三家公司的三种农作物，寻找如下方案的解：每行（梯田高度）包含三个公司，及三种作物每列（日照方向）包含三个公司，及三种作物例如下图方案：具体产量：正交拉丁方：各个作物的产量：各个公司的产量：,2011.11.09,8,拉丁方与正交拉丁方拉丁方的定义：由数1,2,.,n构成的nn矩阵：如果数1,2,.,n中的每个都在每行和每列各出现一次，则称其为n阶拉丁方。前面的4阶矩阵是拉丁方。如果把图5-2中的A、B、C用1、2、3代替，则我们得到一个3阶的拉丁方。36军官问题有6个不同地区的6种不同军衔的军官各一名，共36名。现要将他们排成66的一个方阵，要求做到：(a)每行、每列都有军官来自6个地区；(b)每行、每列都有6种军衔的军官每个军官都有二个标志，即军衔和地区。我们把军衔按1至6编号，把地区也按1至6编号，用(i,j)表示某军官的来自i号地区，其军衔是j号。如果我们不考虑军衔，只寻找满足条件(a)的矩阵，则问题是求66的拉丁方。同样，不考虑地区，只寻找满足条件(b)的矩阵，则也是求6阶拉丁方。当我们把66方阵中的军官用其军衔号i和地区号j组成的数偶(i,j)替代后，组成的方阵就满足：数偶(i,j)的第一个数组成一个6阶拉丁方，第二个数也组成一个6阶拉丁方，且数偶(i,j)是唯一的。,2011.11.09,9,拉丁方与正交拉丁方正交拉丁方的定义：中的nn个数偶互不相同，则称A和B是互相正交的拉丁方。例子5-1矩阵都是3阶拉丁方，而方阵中的9对数偶不同，故A和B是正交的。36名军官问题实际上就是求一对6阶的正交拉丁方。并不是任意的n阶都有正交拉丁方。36名军官问题就是没有解的。,2011.11.09,10,拉丁方与正交拉丁方正交拉丁方的应用正交拉丁方问题有实际的应用，例如测试药物：有三种治发烧的药和三种治感冒的药配合起来给三位病人进行医疗实验，要求在三天内每人都服过这几种药，要试验出哪种退烧药和感冒药配合起来的疗效最佳。用上述的二个3阶正交拉丁方，就可解决这个问题。假设第h行、第k列的元素是(i,j)，我们就在第h天让第k号病人服用第i种的治发烧的药和第种的治感冒的药。具体例子就是，在第二行、第三列是数偶(1,3)，则在第二天三号病人服用第一种治发烧的药和第三种的治感冒的药。引理5-1设A是拉丁方，则A的转置A仍是拉丁方。引理5-2设A是拉丁方，则通过置换p得到的方阵仍是拉丁方。引理5-3设A是拉丁方，则存在置换p，使得通过它得到规范拉丁方，即A的第一行（或第一列）是1,2,.,n。例子：,2011.11.09,11,正交拉丁方及其性质一阶、二阶、三阶正交拉丁方一阶拉丁方只有一个：1。也无所谓正交不正交。二阶拉丁方只有二个：它们不是正交。三阶正交拉丁方至少有一个，就是前面的列5-1：引理5-4设A和B是正交拉丁方，p是对换，A是A经过p置换后的拉丁方，则A和B仍是正交拉丁方。引理5-5设A和B是正交拉丁方，p是置换，A是A经过p置换后的拉丁方，则A和B仍是正交拉丁方。引理5-6设A和B是正交拉丁方，A是A的行规范方，B是B的行规范方，则A和B仍是正交拉丁方。对于都是列规范的情况也成立。这里附带说明一下，二个行规范的正交拉丁方，其第一行组成的数偶是：(1,1)(2,2).(n,n)所有从第二行开始，它们没有相同的元素，即：，如果i1。,2011.11.09,12,正交拉丁方及其性质定理5-1若存在r(1)个n阶拉丁方两两互相正交，则：r(n-1)。按引理5-6，不妨设其都是行规范的。考察它们的第二第一列的元素，共有r个。这些元素满足：首先，都不能是1，即它们只能是2,.,n（共n-1个数）中的数；其次，由于r(n-1)，故至少有二个元素相等；即有二个行规范的正交拉丁方，它们在(2,1)这个位置是相等的，这就与引理5-6相矛盾。故尔只能是：r0的二个多项式s(x),t(x)GFp,x，使得：p(x)=s(x)*t(x)则称s(x)和t(x)是p(x)的因子。公因子：若p(x),q(x)GFp,x，且有相同的因子，则称此因子是公因子。互素的：若p(x),q(x)GFp,x无公因子，则称它们是互素的。引理5-7若p(x),q(x)GFp,x是互素的，则存在a(x),b(x)GFp,x，使得：p(x)*a(x)=q(x)*b(x)+1引理5-8若p(x),q(x)GFp,x，且p(x)的次方大于q(x)的次方，则存在二个多项式r(x),s(x)GFp,x，使得下式成立p(x)=s(x)*q(x)+r(x)其中r(x)的次方小于。同余类：设p(x),q(x),r(x),m(x)GFp,x，且r(x)的次方小于m(x)的次方。若下述成立：p(x)r(x)(modm(x)，q(x)r(x)(modm(x)则称p(x)和q(x)是关于m(x)的同余类，记为p(x)q(x)(modm(x)。域GF(p)设m(x)GFp,x是不可约的n次多项式，GFp,x可化为关于m(x)的一些同余类，记为GF(p)，它是GFp,x中所有次方小于n的多项式的集合，其元素个数个数是p，它和n位p进制数是一一对应。,2011.11.09,21,Galois域GF(p)例子：p=2,n=2GFp,x=0,1,x,1+x,x,1+x,x+x,1+x+x,x,。直接计算可以验证多项式m(x)=1+x+x是二次不可约的。而GFp,x关于m(x)的同余类为GF(2)=0,1,x,1+x，在其上的同余加法和同余乘法如下：,2011.11.09,22,Galois域GF(p)例子：GF(2)=0,1,x,1+x关于m(x)=1+x+x的同余加法和乘法把x用2替换，1+x用3替换，就得：用前面的公式a(k)ij=k*i+j对k=1,2,3进行计算可得：把0用4替换，就得到3个4阶的正交拉丁方：,2011.11.09,23,Galois域GF(p)定理5-2若u是GFp,m(x)的非零元素，则：pow(u,k)1，其中k=p-1这表明非零元素的逆元素总存在。定理5-3若GFp,m(x)=a0,a1,a2,ak，其中a0=0,k=p-1，则有：(x-a0)(x-a1)(x-a2)(x-ak)=x(pow(x,k)1)这是多项式根与系数的关系的一种表达式。正交拉丁方的构造定理5-4设m=p2（且p是素数及n0）。则存在(m-1)个互相正交的拉丁方。证明的过程就是就是构造的过程。设GFp,m(x)=a0,a1,a2,am，其中a0=0,m=p。构造(m-1)个mxm矩阵A1,A2,如下：第k个矩阵Ak=(Ak(i,j)，k=1,m-1，在(i,j)处的元素是Ak(i,j)=ak*ai+aj,i=0,1,m-1,j=0,1,m-1再用同余加法和同余乘法就可验证。定理5-5设n1的素数幂（因子）分解式是n=pow(p1,a1)pow(p2,a2)pow(pk,ak)若m=min(pow(p1,a1),pow(pk,ak)-1则有r个n阶的正交拉丁方。从定理5-4可知对于n=3,4,5都有(n-1)个正交拉丁方。但当n=6时，我们不能从上面定理中判断是否有正交拉丁方。,2011.11.09,24,正交拉丁方的构造欧拉猜想：不存在6阶的正交拉丁方。直到1900年才获得证明。定理5-6设A1,A2,Ak是n阶正交拉丁方，B1,B2,Bk是m阶正交拉丁方。则按下述方法构造的k个nxm阶矩阵也是正交拉丁方：Cr=(Cr(i,j),r=1,k，在位置(i,j)的值是Cr(i,j)=(Ar(s,t)-1)*n+(Br(u,v)-1)*m+1,r=1,k其中角标(i,j)和(s,t),(u,v)之间的关系是：i=(s-1)*m+u,j=(t-1)*m+v例子：,2011.11.09,25,正交拉丁方的应用举例前面我们讨论了四种品牌的轮胎的测试问题，用四辆汽车进行测试，从而引进了四节拉丁方：若同时考察四种不同的刹车车闸对轮胎的磨损，则需满足下面测试安排：每种牌子的轮胎在每辆汽车出现一次轮胎在四个不同的位置上各出现一次不同牌子的轮胎和车闸恰好配合一次四种车闸在四辆车的四个不同位置分别出现一次。下面二个拉丁方，第一个是轮胎的测试安排，第二个是车闸的测试安排：,2011.11.09,26,正交拉丁方的应用下面的方阵是车轮与车闸的配合测试：这个方阵是正交的，所有没有重复的一对数出现，即每种轮胎和每种车闸都恰好配合一次。假定有四种感冒药、四种退烧药和四种止咳药，试验它们的配合效果，找四位病人，在四天内进行试验。如果只考虑一种感冒药的试验，可用四阶拉丁方：其中A,B,C,D是病人代号，而I,II,III,IV是日期。如果考虑二种药的配合，则需要一对四阶的正交拉丁方，而三种药都考虑的话，则需要三个四阶正交的拉丁方。,2011.11.09,27,均衡不完全的区间设计基本概念刚才我们讨论了四种品牌的轮胎，用四种汽车进行测试，每辆汽车上各种轮胎一个，每辆汽车的被测试的轮胎称为一个区组。如果参加测试的轮胎有五个品牌，但是汽车（一个区组）只有四个轮胎，每次只能测试四个轮胎，这样的测试称为不完全的区组设计。我们可以用五辆汽车对五种轮胎按下面方式测试：每一区组只包含四种轮胎，所以是不完全的，每种品牌都作了四次试验。(b,v,r,k,)-设计设X=x1,x2,xv是试验对象的集合，它包含v个元素。所谓均衡不完全的区组，是指由X中的子集构成区组的集合。b为区组的个数，即为B1,B2,Bb。每组包含X的k个元素，且满足下面条件：(1)X中的每一个元素在b组中正好出现r次；(2)任意一对属于X的元素在b组中正好同时出现次；(3)kv；满足上面条件的BIBD(BalancedImcompleteBlockDesign)记为(b,v,r,k,)-设计。,2011.11.09,28,均衡不完全的区间设计例子：X=x1,x2,x7，分组如下：B1=x1,x2,x4；B2=x2,x3,x5；B3=x3,x4,x6；B4=x4,x5,x7；B5=x5,x6,x1；B6=x6,x7,x2；B7=x7,x1,x3;它是7,7,3,3,1-设计。为了讨论方便且不引起混乱，有时把xi简写为i，如上例可写为：B1:124；B2:235；B3:346；B4:457;B5:561；B6:672；B7:713；定理5-8(b,v,r,k,)-设计满足：bk=vr，r(k-1)=(v-1)证明：(1)每组k个元素，共b组，bk是元素出现的总次数；另外，集合X中的v个元素，每个在b组中都出现r次，故vr也是元素出现的总次数，所以它们相等：bk=vr。(2)集合X中某个元素x出现在r个组中，把x从这r个组中除去，则还剩下r(k-1)个元素；又x与其他(v-1)个元素成对地出现在这r个组中，而且每对出现次，故其它(v-1)个元素出现在这r个组中的次数就是(v-1)，所以我们有：r(k-1)=(v-1)。,2011.11.09,29,均衡不完全的区间设计区组矩阵v个元素出现在b个组中，我们可以用0-1矩阵来描述，即A=A(i,j),i1,b,j1,b矩阵在(i,j)的位置的取值是：A(i,j)=1,如果第i个元素在第j个组里否则：A(i,j)=0对于刚才的例子我们有：定理5-8对于(b,v,r,k,)-设计，下列等式成立：AA=(r)I+J其中I是vv的单位矩阵，J是所有元素均为1的vv矩阵。证明：矩阵AA在位置(i,j)值就是A的第i行与第j行之积。按照矩阵A的定义就是i号元素和j号元素在这二组中同时出现的次数。,2011.11.09,30,均衡不完全的区间设计当ij时，是i号元素在b组中出现的次数，也就是r次；当ij时，是i号元素和j号元素同时在b组中出现的次数，也就是次；总结起来就是：=(r)I+J证毕引理5-9det(AA)=(r+(v-1)pow(r-v,v-1)0。对其使用消元法，可以很容易证明上面等式。定理5-10对于(b,v,r,k,)-设计，恒有bv。证明：用反证法，若不然，即bv，矩阵A的行多于列，增加(v-b)列到A里，且新增元素全取值0，记新矩阵为B。因为A中二行的内积和B一样，所以：det(AA)=det(BB)。因为B的新列都是0，故上式右边为0，但按引理5-9上式左边不是0。这个矛盾反证了本定理。,2011.11.09,31,均衡不完全的区间设计对称的BIBD：当b=v时的BIBD称为对称BIBD。因bk=vr，故有k=r。对称的BIBD记为(v,k,)-设计。定理5-11对称的BIBD的任意二组都正好有个共同元素。区组设计的构成方法定理5-12若B1,B2,Bv是集合X=x1,x2,xv的对称BIBD，则(v-1)个区组B2B1,B3B1,BvB1构成一个关于集合XB1的BIBD。证明：显然若x属于某个BiB1，则它也属于XB1。同时，若x属于XB1，则它仍然出现在k组中，XB1中的每对元素仍然同时出现次。最后，由前一个定理可知，B2,Bv中每个区组与B1有个元素相同，这就证明了B2B1,BvB1组成(v-1),(v-k),k,(k-),)-设计。,2011.11.09,32,区组设计的构成方法定理5-13若B1,B2,Bv是集合X=x1,x2,xv的对称BIBD，则(v-1)个区组B2B1,B3B1,BvB1构成一个关于集合XB1的BIBD。证明：显然若x属于某个BiB1，则它也属于B1，所以x在B2,B3,Bv中的（k-1）组出现，即x在B2B1,B3B1,BvB1中的（k-1）组出现B1中的任意一对元素，在这（v-1）个组中同时出现（-1）次。同时，每个组BiB1中有个元素相同，这就证明了B2B1,B3B1,BvB1组成(v-1),k,k-1,-1)的BIBD。从结论中，可以看到必须大于1。例子：b=v=15,r=k=7,=3B1：1,2,3,4,5,6,7B2：1,2,3,8,9,10,11B3：1,2,3,12,13,14,15B4：1,4,5,8,9,12,13B5：1,4,5,10,11,14,15B6：1,6,7,8,9,14,15B7：1,6,7,10,11,12,13B8：2,4,6,8,10,12,14B9：2,4,7,8,11,13,15B10：2,5,6,9,11,12,15B11：2,5,7,9,10,13,14B12：3,4,6,9,11,13,14B13：3,4,7,9,10,12,15B14：3,5,6,8,10,13,15B15：3,5,7,8,11,12,14,2011.11.09,33,区组设计的构成方法前面的（15,7,3）对称BIBD，其区组矩阵为：,2011.11.09,34,区组设计的构成方法这个矩阵的下面部分就是B2B1,B15B1：,2011.11.09,35,区组设计的构成方法这个矩阵的上面部分就是B2B1,B15B1：,2011.11.09,36,Steiner三元系k=3的区组设计称为三元系，（b,v,r,3,l)-设计存在的必要条件是：3b=rv和2r=l(v-1)bk=rv,r(k-1)=l(v-1)或改写为r=l(v-1)/2和b=rv/3=lv(v-1)/6。因为r和b都是整数，所以l(v-1)是偶数，lv(v-1)是6的倍数，即l(v-1)0mod(2)和lv(v-1)0mod(6)定义：l=1的三元系称为斯梯纳（Steiner）三元系。定理（科克曼Kirkman）：v个元素的斯梯纳三元系的必要条件是：v=6n+1或v=6n+3证明：从前面式子，当l=1得v必须满足：(v-1)0mod(2)和v(v-1)0mod(6)(5.9-1)即v是奇数，故v能用下面式子表达：v=6n+1或v=6n+3或v=6n+5在前面二种情况下，v(v-1)都是6的倍数，所以v满足(5.9-1)。在第三种情况下：v(v-1)=6(6n+9n+3)+22mod(6)，这与v必须满足上面的式子(5.9-1)相矛盾。,2011.