本文關(guān)鍵詞：超圖的拉格朗日研究

  更多相關(guān)文章： Frankl-F(u|)redi猜想 Motzkin-Staus定理 超圖 拉格朗日

【摘要】：超圖的拉格朗日函數(shù)是極值組合學(xué)的一個(gè)重要工具.1965年Motzkin-Straus證明了圖的拉格朗日等于其最大團(tuán)的拉格朗日,從而建立了圖的拉格朗日及其最大團(tuán)之間的關(guān)系,這種聯(lián)系在最大團(tuán)問題(NP完全問題)中及極值圖論中均有重要的應(yīng)用.然而Motzkin-Straus定理在超圖中沒有直接的推廣,即超圖的拉格朗日不一定等于其最大團(tuán)的拉格朗日.設(shè)Cm.T是有m條邊的T-圖,它的邊是由N(T)={e|e(?)N,|e|∈T｝中的元素按余字典序排列的最小的m個(gè)元素所構(gòu)成的.當(dāng)T={r｝時(shí),Cm,{r}簡記為Cm,r.我們在多數(shù)的應(yīng)用中需要對(duì)超圖的拉格朗日的上界有一個(gè)好的估計(jì),所以在上個(gè)世紀(jì)八十年代Frankl和Fiiredi猜想：若G是有m條邊的r-圖,則L(G)≤L(Cm,r),其中L(G)為超圖G的拉格朗日.Talbot在2002年首次給出了關(guān)于這個(gè)猜想的一些部分結(jié)果,后來Tang等也證明了在一些限制條件下這個(gè)猜想是成立的.在第三章中證明了如下結(jié)論：1.設(shè)G=([t],E)是有m條邊的左壓3-圖且[t-1](3)(?)G,其中(3/t-1)+(2/t-2)+1≤m≤(3/t).設(shè)(t-p-i)(t-p)t為Gc(G的補(bǔ)圖)的邊按余字典序排列最小的三元組且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.設(shè)G=([l],E)是有m條邊的左壓3-圖且[t-1](3)(?)G,其中(t31)+(2/t-2)+1≤m≤(3/t).設(shè)(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的一般拉格朗日函數(shù)L(H)的優(yōu)化,也即給不同的邊賦予不同的權(quán)重.本文探討的問題是對(duì)任意含m條邊的T型超圖H,是否也會(huì)有L(H)≤L(Cm,T)?在2.1節(jié)中對(duì){1,2｝-圖給出了這個(gè)問題的肯定回答,以及2.3節(jié)也給出了{(lán)1,r1,r2,…,rl｝-圖與{r1,r2,…,rl｝-圖的一般拉格朗日問題的聯(lián)系.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前1條

1 姚宇萍;彭岳建;;極值問題——超圖的拉格朗日（英文）[J];湖南師范大學(xué)自然科學(xué)學(xué)報(bào);2016年01期

，

本文編號(hào)：1258950