超图的横贯

论文摘要

超图是普通图的推广,普通图的覆盖在图的理论中占有重要地位。而超图的横贯作为普通图的覆盖的推广,其研究意义自然更加深刻,适用范围自然更为广泛。第一部分介绍了与本论文有关的基本概念。超图的横贯超图在许多领域有着广泛的应用,而如何确定横贯超图则是研究工作的重点。第二部分着重介绍了确定任一超图的横贯超图的一种算法（我们称之为Boole算法）和与此算法相关的结果。第2.1节、第2.2节结合Boole运算定律和相关的概念,给出并证明了Boole算法。其具体步骤为:步骤l:对超图H的每一条边Ej{vj1,vj2,…,v(j|Ej|},定义它的Boole表达式:（?）步骤2:对超图H=（E1,E2,…,Em）,定义它的Boole表达式:φ（H）=（?）步骤3:对φ（H）实施Boole运算,直至得到最简的表达式:σ（TrH）（?）步骤4:σ（TrH）中每一个σt所对应的顶点集Ti是H的一个极小横贯,并且集簇（T1,T2,…,Tt,…）构成了横贯超图TrH.并在此基础上讨论了Boole算法的复杂性:定理2.2.1令超图H的边数为m,上秩为q,则关于H的Boole算法的复杂性为:o(q2m)又根据超图的横贯与独立集的关系,间接地得到了一种求任一超图最大独立集及独立数的算法。第2.3节通过Boole算法,并结合Boole代数中的对偶原理证明了Berge超图著作中有关横贯超图的两个经典结论:推论2.3.1若H和H’是两个简单超图,那么H’=TrH当且仅当H=TrH’.推论2.3.2若H是一个简单超图,则有Tr（TrH）=H.并由此提出问题:哪类超图满足其横贯超图是其自身的性质?作者给出了具有此性质的三类超图,它们分别是:Lavas（?）s超图,扇形超图和射影平面PG（3）,并给出了Boole算法的证明（详见命题2.3.1,命题2.3.2,命题2.3.3）.研究超图的横贯数有其实际的应用背景,尤其是在优化论方面。第三部分给出了三类超图的横贯数（或它们的界）.第3.1节、第3.2节分别给出了p-划分完全超图的横贯数与阶数与边数固定了的一致超图的横贯数的界。其主要结果为:定理3.1.1τ(Kn1,n2,…,npr1,r2,…,rpmin（ni-ri+1） （i∈{1,2,…,p}）定理3.2.1设H是在V上的一个r-一致超图,若|V|=n,|H|=m,则有:τ（H）≤n-（n-（?））（（?））?.第3.3节主要结合分数横贯理论,得出了圈区间超图的横贯数与分数横贯数的关系:定理3.3.2设H是圈区间超图,则有:τ（H）-[τ*（H）].并借助分数横贯数的概念,得出了给定条件下的几个特殊的圈区间超图的横贯数:推论3.3.2设H是一个n阶圈区间超图.若下秩s（H）>（?）,则有:τ（H）≤2.推论3.3.4设H是一个r-一致的n阶圈区间超图,则有:τ（H）=（?）.第四部分更深入地研究了著名学者Erd（o|¨）s等提出的有关超图（p,t）性质的问题。第4.1节、第4.2节结合相关的概念、定义,主要得到了一个超图具有（p,t）性质的充分条件:定理4.2.2设正整数t≥2,H’是超图H的任意p条边构成的部分超图。对任意的H’,如果在V（H’）中找不到这样的t+1个顶点和与之相对应的t+1条边,使得这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（详见命题4.3.1,命题4.3.2,命题4.3.3）.

论文目录

• 中文摘要
• Abstract
• 文献综述
• 1.基本概念
• 2.确定横贯超图的一种算法
• 2.1 Boole运算的介绍
• 2.2 确定任一超图的横贯超图TrH的Boole算法
• 2.3 与Boole算法相关的一些结论
• 3.几类超图的τ（H）
• 3.1 p-划分完全超图的τ（H）
• 3.2 r-一致超图的τ（H）的界
• 3.3 圈区间超图的τ（H）
• 4.超图的（p,t）性质
• 4.1 相关定义
• 4.2 超图（p,t）性质的一个充分条件
• 4.3 射影平面的（p,t）性质
• 参考文献
• 致谢