超图的拉格朗日研究

发布时间：2017-12-06 14:35

  本文关键词：超图的拉格朗日研究

  更多相关文章： Frankl-F(u|)redi猜想 Motzkin-Staus定理 超图 拉格朗日

【摘要】：超图的拉格朗日函数是极值组合学的一个重要工具.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和Fiiredi猜想：若G是有m条边的r-图,则L(G)≤L(Cm,r),其中L(G)为超图G的拉格朗日.Talbot在2002年首次给出了关于这个猜想的一些部分结果,后来Tang等也证明了在一些限制条件下这个猜想是成立的.在第三章中证明了如下结论：1.设G=([t],E)是有m条边的左压3-图且[t-1](3)(?)G,其中(3/t-1)+(2/t-2)+1≤m≤(3/t).设(t-p-i)(t-p)t为Gc(G的补图)的边按余字典序排列最小的三元组且t-p-i-a=min{E(t-1)/c},其中E(t-1)t/c{b∈V：b∪{t-1,t}∈V(3)\E}.若i≥p-a-1,则L(G)≤L(Cm,3).2.设G=([l],E)是有m条边的左压3-图且[t-1](3)(?)G,其中(t31)+(2/t-2)+1≤m≤(3/t).设(t-p-i)(t-p)t为Gc的边按余字典序排列最小的三元组,若t≥8(p-1)2-40/(p-1)3(p-2)3,则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｝-图的一般拉格朗日问题的联系.
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【参考文献】

中国期刊全文数据库 前1条

1 姚宇萍;彭岳建;;极值问题——超图的拉格朗日（英文）[J];湖南师范大学自然科学学报;2016年01期

，

本文编号：1258950