论文部分内容阅读
超图的拉格朗日极值是极值图论的一个有力工具,它在优化、模式识别等领域也具有广泛的应用。1965年,Motzkin和Straus建立了图的拉格朗日极值和其团数之间的关系,这个关系及其推广已被广泛应用于优化问题中,如果在超图中能得到类似结果,是极具价值的。在本文中,我们证明了某些匀齐超图和非匀齐超图中的Motzkin-Straus型定理。其中关于3-图和r-图的结果为Peng和Zhao(2013)的一个猜想提供了支撑。在很多应用中,我们需要超图拉格朗日极值的上界。Frankl和Furedi猜测在所有边数为m的r-图中,由cOlex序最小的m个元素组成的r-图具有最大的拉格朗日极值。2002年,Talbot得到了Frankl-Furedi猜想的一些部分结果。在本文中,我们证明了在一定条件下,当m=(t(?))-p(0≤p<t-r)时,在所有边数为m的t阶r-图中,由colex序最小的m个元素组成的r-图具有最大的拉格朗日极值。作为推论,我们得到了m=(t3)-p(0≤p≤4)和r=3时,Frankl-Furedi猜想成立。我们还在其他一些限制条件下,得到了Frankl-Furedi猜想的一些部分结果。鉴于Motzkin-Straus定理不能直接推广到超图中,我们建立了一个和图及其补图的结构相关的齐性多项式函数。这个函数的极值(我们称其为广义拉格朗日极值)推广了图的拉格朗日极值的概念。对3-图,我们建立了图的团数和其广义拉格朗日极值之间的一些关系,这些关系可为3-图的团数提供线索。我们还建立了某些{2,r}-图({1,2,r}-图)的最大完全子图的阶和其广义极值之间的关系。