论文部分内容阅读
超图的拉格朗日函数是极值组合学的一个重要工具。1965年Motzkin-Straus证明了图的拉格朗日等于其最大团的拉格朗日，从而建立了图的拉格朗日及其最大团之间的关系，这种联系在最大团问题(NP完全问题)中及极值图论中均有重要的应用。然而Motzkin-Straus定理在超图中没有直接的推广，即超图的拉格朗日不一定等于其最大团的拉格朗日。设Cm,T是有m条边的T-图，它的边是由N(T)={e|e?N,|e|∈T}中的元素按余字典序排列的最小的m个元素所构成的。当T={r}时，Cm,{r}简记为Cm,r。我们在多数的应用中需要对超图的拉格朗日的上界有一个好的估计，所以在上个世纪八十年代Frankl和F¨uredi猜想：若G是有m条边的r-图，则L(G)≤L(Cm,r)，其中L(G)为超图G的拉格朗日。Talbot在2002年首次给出了关于这个猜想的一些部分结果，后来Tang等也证明了在一些限制条件下这个猜想是成立的。在第三章中证明了如下结论： 1.设G=([t],E)是有m条边的左压3-图且[t?1](3)?G，其中t?13+t?22+1≤m≤(t3)。设(t?p?i)(t?p)t为Gc(G的补图)的边按余字典序排列最小的三元组且t?p?i?a=min{Ec(t?1)t}，其中Ec(t?1)t={b∈V:b∪{t?1,t}∈V(3)E}。若i≥p?a?1，则L(G)≤L(Cm,3)。 2.设G=([t],E)是有m条边的左压3-图且[t?1](3)?G，其中t?13+ t?22+1≤m≤(t3)。设(t?p?i)(t?p)t为Gc的边按余字典序排列最小的三元组，若t≥(p?1)3(p?2)38(p?1)2?40+2p?1，则L(G)≤L(Cm,3)。 第二章考虑非一致超图H的一般拉格朗日函数L(H)的优化，也即给不同的边赋予不同的权重。本文探讨的问题是对任意含m条边的T型超图H，是否也会有L(H)≤L(Cm,T)？在2.1节中对{1,2}-图给出了这个问题的肯定回答，以及2.3节也给出了{1,r1,r2,···,rl}-图与{r1,r2,···,rl}-图的一般拉格朗日问题的联系。