论文部分内容阅读
图的分解起源于Walecki解决的完全图Kn的Hamilton圈分解,之后国内外学者开始研究Hamilton圈分解问题,并拓展到超图中去。超图H是一个二元组(V,E),其中V是有限集,V中的元素称为顶点,E是V的有限非空子集族,E中的元素称为超边。超图H的Γ分解是指将超图H分解成多个子超图的集合,使得每个子超图(称为区组)(block)与Г中某一个超图同构,超图H的Γ分解被称为是一个(H,Γ)-设计((H,Γ)-design)。本文利用组合设计的思想研究超图的Г分解问题。首先,根据已有超图分解的结论结合Γ的特征给出可分解的必要条件,进而具体分析必要条件,刻画小阶数超图的分解问题,并基于相应的递推结构证明上述给出的必要条件的充分性。本文解决了λ-重完全二部3-一致超图Γ={W4(3)},Г={O}分解的问题,并且给出了完全3-一致超图Γ={W5(3)}的部分分解结果。文章结构如下:第一章给出了几个典型的组合设计,介绍了超图的发展历程,超图分解的意义,以及相应的研究动态。第二章研究λKm,n(3)的W4(3)分解问题。首先考虑当m=n时λKn,n(3)的W4(3)分解的存在性。通过计算其存在的必要条件为λn(n-1)≡0(mod4)且n≥3。因此需要考虑λ=1,n≡0(mod4),n≡1(mod4)时λKn,n(3)的W4(3)分解的存在性,以及λ=2,n≡2(mod4),n≡3(mod4)时λKn,n(3)的W4(3)分解的存在性。其次,基于烛台系统的结果,给出该分解的递推结构,探究小阶数超图的分解问题。针对小阶数超图分解不存在的情况用“挖洞”和定义满足规定条件的新超图的方法解决。最后,通过证明得出了λKn,n(3)的W4(3)分解的充要条件。当m≠n时,运用上述方法可得到λKm,n(3)的W4(3)分解的充要条件。第三章研究Kn(3)的W5(3)分解问题。通过计算该分解存在的必要条件为n≡0,1,2(mod5),n≥6。由于所需子设计阶数比较大没能完全找出该分解存在的充要条件。仅通过计算机搜索得到了部分完全3-一致超图分解为W5(3)的结果。第四章研究λKm,n(3)的O分解问题。通过计算Sλ(3,O,m,n)存在的必要条件为λmn(m+n-2)≡0(mod 16),λm(2n+m-3)≡0(mod 8),λn(2m+n-3)≡0(mod 8),λm≡0(mod2),λn≡0(mod2),λ(m+n-2)≡0(mod2),m+n≥6。本章研究方法同第二章,由于正八面体结构的特殊,在分解时可以先进行C4分解,进而对C4插入上顶点和下顶点生成八面体。基于此方法给出了一些递推构造,以及小阶数超图分解结果。最后通过证明得到λKm,n(3)的O分解的充要条件。