论文部分内容阅读
可分组设计(GDD)在组合设计理论中有着极其重要的作用,它们被广泛地用来构造各类设计。例如,在组合设计理论奠基人Wilson和Hanani证明成对平衡设计存在的充分必要条件时,可分组设计是他们递归构造过程中不可缺少的一部分。类似地,可分解可分组设计和frame在构造具有可分解性质的设计的时候同样起着基础性的作用。我们称一个GDD是型一致的如果它所有组的大小均相同。本文研究了多类可分组设计的存在性问题,包括型不一致的4-GDD,型一致的5-GDD,4-RGDD,4-frame以及G-GDD等。同时,我们也讨论了可分组设计在信息科学当中的应用,这些应用包括光纤网络中的业务疏导问题以及非线性纠错码。 在第2章中,我们研究了型为gum1的可分组设计存在性问题。当区组大小为3时,这个问题已被Colbourn,Hoffman和Rees于1992年解决。而区组大小是4的情形还没有被解决。目前关于此类4-GDD的存在性结果多集中于gu是偶数的情况。本文将考察此类4-GDD整个存在性问题。我们证明了对任意给定的g,除了很小一部分的u外,型为gum1的4-GDD存在的必要条件(关于参数u和m)也是充分的。作为这类型不一致的GDD的应用,我们构造了一些其他类型的设计,包括成对平衡设计,有向成对平衡设计,Kirkman frame,以及可分组覆盖设计。 在第3章中,我们继续研究了5-GDD,4-RGDD以及4-frame的存在性问题。虽然整个问题还没有彻底解决,但我们已取得了很大的进展。我们的结果主要集中在组相对比较大的情形。我们取得这些结果要归功于两类强有力的递归构造,它们是“双可分组设计构造”和“Rees型乘积构造”。在应用的时候我们对这两类构造都做了一些改进。此外我们还构造了一些较小的设计,包括型为2184,944,1818和3611的4-RGDD。 在第4章,可分组设计的概念扩展到了G-可分组设计。我们利用G-GDD构造了五个顶点的G-设计。此类设计的存在性问题最早由Bermond,Huang,Rosa和Sotteau于1980年提出,并与光纤网络中的业务疏导问题密切相关,但至今仍未彻底解决。我们完全解决了这个问题,同时对几乎所有的n,确定了n阶C-疏导的最小成本,这里C≤9。 在第5章,我们考察了长度为n的完备的q元t-删位纠错码码字个数所有可能的取值。由于在Levenshteǐn距离下半径为t的球可以有不同的大小,所以完备的t-删位纠错码的码字个数可以是不一样的,因而确定所有可能的取值是有意义的。当t=n-2时,t-删位纠错码和有向填充问题密切相关,后者的构造主要基于组合设计理论中的工具。在本章中,我们通过构造大量的不完全有向填充,基本上确定了完备的(4,2)q-DCC所有可能的大小,这里还剩下大小为62的(4,2)19-DCC和大小为196的(4,2)34-DCC没有解决。 第6第7两章主要研究常重码(CWC)和常重复合码(CCC)。已有许多种工具被用来确定常重码和常重复合码码字个数的最大值,其中包括了一些组合的手段。我们对其中的可分组码(GDC)和完全可约超单(CRSS)设计比较感兴趣。Chee,Ge和Ling提出了可分组码的概念,并用来确定重量为三的最优常重复合码的大小。在第6章中,我们研究了重量为四、极小距离为六的最优三元常重复合码的构造问题。除了一小部分的长度外,我们基本上将这个问题解决了。完全可约超单设计与多元常重码相关,一个(v,k,λ)-CRSS设计就是一个最优(v,2(k-1),k)λ+1-码。在第7章中,我们基本上解决了(v,5,2)-CRSS设计的存在性问题,除了可能的例外值v=25。利用这个结果,我们确定了当n≡0,1,4,5(mod20)且n≠25时最优(n,8,5)3-码的大小。