3-一致完全超图的-分解

朱 莉

（南通职业大学 数学教研室，江苏 南通 226007）

1 问题提出

超图是有限集合的子集系统，是离散数学中的最一般结构。超图H 定义为一个有序二元组H=（X，E），其中：X 是一个有限非空集合，其元素称为超图H 的顶点；E 是X 的一组非空子集簇，其元素是X 的一个非空子集，被称为边或超边。如果超图H 的每一条边都恰好包含k 个顶点，则称它是k-一致的。2-一致超图就是传统意义上的图。关于超图的相关概念和理论，可参阅文献[1-2]。

2 预备知识

3-一致超图的图分解可看作组合设计中3-设计的推广。3-设计（记为t-（v，K，λ）），是一个关联结构（V，B），满足条件：（1）V 是v 元点集；（2）B是V 的子集族（B 中的元素称为设计的区组），且每一个区组b∈B 有∈K；（3）V 中的任意一个3-元子集恰好出现在λ 个区组中。3-设计的相关内容可参见文献[9-10]。下列两个结论分别来自Hanani[11]和Ji[12]。

定理23-（v，{k：4≤k≤34}，1）存在的充分必要条件是v≥4。

定理33-（v，{4，5，6}，1）存在的充分必要条件是v≡0，1，2（mod 4）且v≥4，v≠9，13。

将λ 划分为λ≡1（mod 2）和λ≡0（mod 2），则引理1 的条件可有两种情形：当λ≡1（mod 2）时，v≡0，1，2（mod 4）；当λ≡0（mod 2）时，v≥4。

3 定理1 的证明

（1）λ=1，v≡0，1，2（mod 4）；

（2）λ=2，v≥4。

结合引理4，引理5 和引理1，完成了定理1的证明。