超图的横贯

摘要

超图是普通图的推广，普通图的覆盖在图的理论中占有重要地位，而超图的横贯作为普通图的覆盖的推广，其研究意义自然更加深刻，适用范围自然更为广泛。
　　 第一部分介绍了与本论文有关的基本概念。
　　 超图的横贯超图在许多领域有着广泛的应用，而如何确定横贯超图则是研究工作的重点，第二部分着重介绍了确定任一超图的横贯超图的一种算法（我们称之为Boole算法）和与此算法相关的结果。
　　 第2.1节、第2.2节结合Boole运算定律和相关的概念，给出并证明了Boole算法。
　　 第2.3节通过Boole算法，并结合Boole代数中的对偶原理证明了Berge超图著作中有关横贯超图的两个经典结论：
　　 推论2.3.1若H和H'是两个简单超图，那么H'=TrH当且仅当H=TrH'。
　　 推论2.3.2若H是一个简单超图，则有Tr(TrH)=H。
　　 并由此提出问题：哪类超图满足其横贯超图是其自身的性质？作者给出了具有此性质的三类超图，它们分别是：Lavaszs超图，扇形超图和射影平面PG(3)，并给出了Boole算法的证明。
　　 研究超图的横贯数有其实际的应用背景，尤其是在优化论方面，第三部分给出了三类超图的横贯数（或它们的界）。
　　 第3.1节、第3.2节分别给出了p-划分完全超图的横贯数与阶数与边数固定了的一致超图的横贯数的界。
　　 第四部分更深入地研究了著名学者Erdos等提出的有关超图(p,t)性质的问题，第4.1节、第4.2节结合相关的概念、定义，主要得到了一个超图具有(p,t)性质的充分条件：
　　 定理4.2.2设正整数t≥2,H'是超图H的任意p条边构成的部分超图，对任意的H'，如果在V(H')中找不到这样的t+l个顶点和与之相对应的t+l条边，使得这t+1个顶点中的每个顶点恰好只含在这t+1条边的一条边中，那么H就具有(p,t)性质。
　　 第4.3节根据射影平面的定义推导出了r阶射影平面PG(r)具有(p,t)性质的有关结论，其主要结果有：
　　 定理4.3.1如果射影平面PG(r)存在，那么PG(r)具有(2r-2，r-1)性质。
　　 并由此提出问题：当t=r-1时，求r阶射影平面具有(p,t)性质的最大值p?作者给出了当r=2，3，4时，p的最大值分别为2，5，9。

目录

文摘

英文文摘

声明

文献综述

1.基本概念

2.确定横贯超图的一种算法

3.几类超图的γ(H)

4.超图的(p,t)性质

参考文献

致谢