如果一個(gè)劃分將圖G的頂點(diǎn)集分成k個(gè)不相交的子集,則稱這個(gè)劃分是圖G的一個(gè)k部劃分.圖的一個(gè)k部劃分如果滿足‖Vi|-|Vj‖≤1對(duì)任意的j,j ∈ {1,2,...,k}都成立,則稱這個(gè)劃分為k部平衡劃分.本文主要研究圖的五部平衡劃分問(wèn)題.本文的主要結(jié)果如下:1.G是一個(gè)有n個(gè)頂點(diǎn)和m條邊的圖,其中δ(G)≥≥4[n/5],且r是實(shí)數(shù),則圖G存在一個(gè)最大五部平衡劃分V1,V2,V3,V4,V5,使得(?),如果G滿足:(1)(?)(2)(?)2.若圖G有n個(gè)頂點(diǎn)和m條邊,p是Gc中頂點(diǎn)不交的K5的最大數(shù)目,則圖G存在一個(gè)最小五部平衡劃分V1,V2,V3,V4,V5,滿足e(V1,V2,V3,V4,V5)≤4/5m+2[[n/5]-p)+6/5.
【學(xué)位單位】：華東師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2020
【中圖分類】：O157.5
【文章目錄】：
摘要
Abstract
第一章 引言
    1.1 基本概念
    1.2 研究背景
    1.3 本文主要結(jié)果
第二章 最大平衡5-劃分
    2.1 一些引理
    2.2 主要結(jié)論
第三章 最小平衡5-劃分
    3.1 一些引理
    3.2 主要結(jié)論
第四章 結(jié)論與展望
參考文獻(xiàn)
致謝

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 ;關(guān)于批零劃分問(wèn)題(討論稿)[J];稅務(wù)研究;1987年B3期

2 呂向一;王美妮;;政府間稅收劃分問(wèn)題與改革對(duì)策[J];大眾投資指南;2017年06期

3 張同全;李偉東;李建平;;限制的星劃分問(wèn)題[J];云南大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年02期

4 ;關(guān)于期刊級(jí)別的劃分問(wèn)題[J];中國(guó)腫瘤;1997年04期

5 楊秀君;;關(guān)于書(shū)刊劃分問(wèn)題的討論[J];圖書(shū)館學(xué)刊;1985年03期

6 劉詩(shī)雄;;解題中的劃分問(wèn)題[J];中學(xué)數(shù)學(xué);1985年04期

7 徐大川,韓繼業(yè),杜東雷;關(guān)于圖劃分問(wèn)題的改進(jìn)的近似算法[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2005年04期

8 鐘和;關(guān)于我國(guó)新的社會(huì)階層劃分問(wèn)題的幾個(gè)觀點(diǎn)[J];黨政干部學(xué)刊;2002年06期

9 鄧霞萍;對(duì)跑的周期各動(dòng)作階段劃分問(wèn)題的初步探討[J];廣州體育學(xué)院學(xué)報(bào);1994年03期

10 陳進(jìn);鞠曼麗;;再論聲樂(lè)教學(xué)中的聲部劃分問(wèn)題[J];北方音樂(lè);2015年20期

相關(guān)博士學(xué)位論文 前4條

1 楊愛(ài)峰;圖的廣義著色[D];鄭州大學(xué);2004年

2 李海燕;圖的平衡劃分問(wèn)題[D];南京師范大學(xué);2014年

3 丁紅林;限制性路由與網(wǎng)絡(luò)構(gòu)建問(wèn)題[D];云南大學(xué);2014年

4 王霖青;交通小區(qū)劃分問(wèn)題的整數(shù)規(guī)劃建模與優(yōu)化算法研究[D];東北大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 陳全中;圖的平衡5—?jiǎng)澐謫?wèn)題[D];華東師范大學(xué);2020年

2 王婉;平衡劃分問(wèn)題極小反例的性質(zhì)[D];南京師范大學(xué);2019年

3 羅玉嬌;圖的平衡劃分問(wèn)題[D];華東師范大學(xué);2018年

4 陶辛鍇;有限圖的內(nèi)劃分問(wèn)題[D];中國(guó)科學(xué)技術(shù)大學(xué);2017年

5 朱培培;邊染色圖的頂點(diǎn)劃分問(wèn)題[D];浙江師范大學(xué);2012年

6 孫海晶;關(guān)于圖平衡劃分問(wèn)題的一些結(jié)果[D];南京師范大學(xué);2017年

7 胡曉臣;關(guān)于圖的Judicious劃分問(wèn)題的研究[D];北京交通大學(xué);2015年

8 張慶波;無(wú)線傳感器網(wǎng)絡(luò)中的控制劃分問(wèn)題研究[D];曲阜師范大學(xué);2012年

9 趙筱萌;仲裁初始階段的管轄權(quán)劃分問(wèn)題研究[D];山東大學(xué);2014年

10 閆悅;歌唱聲部劃分問(wèn)題研究[D];天津音樂(lè)學(xué)院;2014年

本文編號(hào)：2869256