發(fā)布時間：2017-10-23 23:13

  本文關(guān)鍵詞：圖二部平衡劃分中的極小反例問題

  更多相關(guān)文章： 圖 k-部劃分 k-部平衡劃分 二部平衡劃分

【摘要】：設(shè)圖G為簡單圖,k為正整數(shù).若將圖G的頂點集V(G)劃分成k個互不相交的頂點集V1,V2….,Vk,稱為簡單圖G的一個k-部劃分.若圖G的某個k-部劃分,滿足條件-1≤|Vi|-|Vj|≤1,(i,j∈{1,2,,…,k}),則稱V1,V2….,Vk,是圖G的一個k-部平衡劃分,其中|Vi|(i∈k)表示某個劃分的大小即所含頂點個數(shù).本篇學位論文主要討論k-部劃分中比較特殊的平衡二部劃分問題,即此時k=2.在文獻中,Bollobas和Scott有一個著名的關(guān)于平衡二部劃分的猜想：對于有m條邊和n個頂點的簡單圖G,若每個頂點的度至少為2,則圖G存在一個平衡二部劃分[V1,V2],使得max{e(V1),e(V2)}≤m/3.Xu,Yan和Yu在文獻中初步證明了當時,圖G的最大平衡二部劃分滿足]max{e(V1),e(V2)}≤e(G)/3.之后,Xu和Yu進一步證明猜想的正確性,并指出三角形K3是唯一極圖.Lee,Loh和Sudakov證明了對任意正整數(shù)k≥1,每個有m條邊的圖G,若最小度為2k或2k+1,則圖G有平衡二部劃分[V1,V2]滿足(?)并且他們猜想無窮小的尾數(shù)項可以去掉.本篇學位論文延用Xu和Yu在文獻中的方法,主要證明了如下結(jié)論：設(shè)圖G是一個最小度不小于4且含m條邊和幾個項點的簡單圖.若圖G沒有二部平衡劃分[S,S],使得(?)但任一最小度不小于4且階數(shù)小于n圖H都有二部平衡劃分[T,T]使得(?) u1,u2,u3,u4為四個4一度點且G[{u1,u2,u3,u4}]=K4,則有(?)除非其結(jié)構(gòu)為圖1和圖2
【關(guān)鍵詞】：圖 k-部劃分 k-部平衡劃分 二部平衡劃分
【學位授予單位】：南京師范大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：O157.5
【目錄】：

• 摘要5-7
• Abstract7-9
• 第1章 緒論9-18
• 1.1 相關(guān)定義和概念9-11
• 1.2 圖劃分的歷史進展和現(xiàn)有結(jié)論11-16
• 1.3 本文所用相關(guān)結(jié)論16-18
• 第2章 定理及證明18-37
• 第3章 總結(jié)與展望37-38
• 參考文獻38-41
• 致謝41

【相似文獻】

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

1 蘇本堂,扈文峰;最小度和f-因子[J];山東大學學報(自然科學版);1997年02期

2 劉紅霞;k-對等圖的鄰集和最小度[J];煙臺大學學報(自然科學與工程版);2002年02期

3 陳綱;;蘊含扇圖的可圖序列的最小度和[J];西北師范大學學報(自然科學版);2006年04期

4 張勇飛;柳明珠;;關(guān)于包含2個圈的2-因子的最小度條件的注記[J];科教文匯(下旬刊);2008年11期

5 滕巖;王江魯;;圖的最小度與路可擴性[J];科學技術(shù)與工程;2010年11期

6 蔡小濤;關(guān)于S-閉跡的最小度的充分條件[J];數(shù)學年刊A輯(中文版);1989年03期

7 李明楚,李忠祥;無爪圖中的最長圈[J];數(shù)學研究與評論;1993年01期

8 滕聰;k-消去圖的鄰集和最小度[J];臨沂師專學報;1993年Z1期

9 任世軍,羅聲政;鄰域并與最小度給出的哈米頓圖的充分條件(英文)[J];哈爾濱工業(yè)大學學報;1993年01期

10 蘇本堂,何樂亮,程述漢;獨立數(shù)和最小度與f-因子[J];山東師大學報(自然科學版);1997年01期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 何蓓;吳敏;三間均;周意誠;;基于最小度排序的One to One營銷優(yōu)化算法[A];第二十三屆中國控制會議論文集（上冊）[C];2004年

中國博士學位論文全文數(shù)據(jù)庫 前2條

1 劉建熙;關(guān)于Randic指標三個問題的解決[D];南開大學;2010年

2 鄒青松;圖包含指定長度的圈和泛弧問題的研究[D];山東大學;2011年

中國碩士學位論文全文數(shù)據(jù)庫 前3條

1 肖然;圖二部平衡劃分中的極小反例問題[D];南京師范大學;2016年

2 劉建熙;[D];華南師范大學;2007年

3 滕巖;圖的度與路可擴性[D];山東師范大學;2010年

，

本文編號：1085853