一类超图拉格朗日极值的上界估计

发布时间：2018-01-04 05:05

  本文关键词：一类超图拉格朗日极值的上界估计　出处：《吉林大学》2015年硕士论文　论文类型：学位论文

  更多相关文章： 拉格朗日极值 超图 最优解 团

【摘要】：超图的Lagrange极值在图论中占据者重要位置,同时它在现实生活中也有着众多应用.例如,最优化控制,数学模型建立,生物化学的研究都起到重要的作用.所以,对于超图的Lagrange极值的研究有着重要意义. 1941年,Turan [30]发现给定的正整数p和n,对于n个顶点的图G上不含有p阶团的最大边数这就是有名的Turan定理,他将图的Lagrange极值与团相联系.Turan定理已经是图论中的重要结果,有着深远的影响.1965年,Motzkiz和Straus [21]发现了求解2维图的简易有效的方法,并在许多优化的问题中得以应用.他们证明了一个2维图的Lagrange极值与它所包含的最大数阶团的Lagrange极值相同.这个结果不仅提供了一个新的证明Turan定理的方法,同时也唤起众多学者对超图的Lagrange极值的研究的兴趣.随之而来的想法自然是想要将结果推广到超图当中来.但是,不幸的是,对于超图来讲,Motzkiz和Straus的结论并不是完全正确的.有很多超图的Lagrange极值不等于其包含的最大数阶团的Lagrange极值的例子.Motzkiz和Straus的结论在超图中也不是完全错误的,在某些特定的条件下该结论依然成立.例如[25],对于正整数m,t,如果G是含有t-1阶团为最大数阶团的3维超图,且边数m满足条件则Motzkiz和Straus的结论在3维超图成立,即λ(G)=λ([t-1](3)). 虽然Motzkiz和Straus找到了求解图的Lagrange极值的方法,并且进一步有效地证明了Turan定理,但是结果对于超图的局限性还是阻碍了研究的进一步发展.然而我们有时候并不需要知道超图的Lagrange极值,只需要了解它的上界,本文的工作是基于超图顶点集合研究具有某一类结构的超图的Lagrange极值上界. 我们下面定义一种类型的r维超图.对于给定的点集V,我们将这个点集分成r个不相交的点集{Vi1}1≤i1≤r,我们再将每个Vi1(1≤i1≤r)分成r个不相交的集合,定义为{Vi1i2}1≤i2≤r.然后再将每个Vi1i2(1≤i1,i2≤r)分成r个不相交的集合,定义为{Vi1i2i3}1≤i3≤r.重复上面的操作,直到我们获得了rp个互不相交的集合{Vi1i2…ip}1≤i1,i2,…,ip≤r.该r维超图的边所包含的点在每个Vi中取且只取一个点,或在每个Vi1i2中取且只取一个点,直到在每个Vi1i2…ip中取且只取一个点,并取尽所有可能的边,我们定义这样的r为超图为Sp(r)[V].我们猜测这一类超图顶点集合在尽可能平分的情况下,即结构达到最对称的时候所得极值为此类超图极值的上界.在3维超图中,当p=2时我们得到这类超图极值为
[Abstract]:The Lagrange extreme value of hypergraph plays an important role in graph theory , and it has many applications in real life . For example , optimization control , mathematical model establishment and biochemistry research play an important role . So , it is very important to study the Lagrange extreme value of hypergraph . In 1965 , Turan Theorem 30 discovered that a given positive integer , p and n , does not contain the maximum number of edges of a p - order group on the graph G of n vertices , which is a famous Turan theorem . Although Motzkiz and Straus have found a method to solve the Lagrange extrema of graphs , and further prove the Turan theorem , we do not need to know the limits of the supergraph or hinder the further development of the research . However , we don ' t need to know the upper bound of the hypergraph , and the work of this paper is based on the hypergraph vertex set to study the upper bound of the supergraph with a certain kind of structure . For a given point set V , we divide this point set into r disjoint sets { Vi1 } 1 鈮，

本文编号：1377150