图的平衡5—划分问题

发布时间：2020-11-03 23:28

　　 如果一个划分将图G的顶点集分成k个不相交的子集,则称这个划分是图G的一个k部划分.图的一个k部划分如果满足‖Vi|-|Vj‖≤1对任意的j,j ∈ {1,2,...,k}都成立,则称这个划分为k部平衡划分.本文主要研究图的五部平衡划分问题.本文的主要结果如下:1.G是一个有n个顶点和m条边的图,其中δ(G)≥≥4[n/5],且r是实数,则图G存在一个最大五部平衡划分V1,V2,V3,V4,V5,使得(?),如果G满足:(1)(?)(2)(?)2.若图G有n个顶点和m条边,p是Gc中顶点不交的K5的最大数目,则图G存在一个最小五部平衡划分V1,V2,V3,V4,V5,满足e(V1,V2,V3,V4,V5)≤4/5m+2[[n/5]-p)+6/5.
【学位单位】：华东师范大学
【学位级别】：硕士
【学位年份】：2020
【中图分类】：O157.5
【文章目录】：
摘要
Abstract
第一章 引言
    1.1 基本概念
    1.2 研究背景
    1.3 本文主要结果
第二章 最大平衡5-划分
    2.1 一些引理
    2.2 主要结论
第三章 最小平衡5-划分
    3.1 一些引理
    3.2 主要结论
第四章 结论与展望
参考文献
致谢

【相似文献】

相关期刊论文 前10条

1 ;关于批零划分问题(讨论稿)[J];税务研究;1987年B3期

2 吕向一;王美妮;;政府间税收划分问题与改革对策[J];大众投资指南;2017年06期

3 张同全;李伟东;李建平;;限制的星划分问题[J];云南大学学报(自然科学版);2008年02期

4 ;关于期刊级别的划分问题[J];中国肿瘤;1997年04期

5 杨秀君;;关于书刊划分问题的讨论[J];图书馆学刊;1985年03期

6 刘诗雄;;解题中的划分问题[J];中学数学;1985年04期

7 徐大川,韩继业,杜东雷;关于图划分问题的改进的近似算法[J];应用数学学报;2005年04期

8 钟和;关于我国新的社会阶层划分问题的几个观点[J];党政干部学刊;2002年06期

9 邓霞萍;对跑的周期各动作阶段划分问题的初步探讨[J];广州体育学院学报;1994年03期

10 陈进;鞠曼丽;;再论声乐教学中的声部划分问题[J];北方音乐;2015年20期

相关博士学位论文 前4条

1 杨爱峰;图的广义着色[D];郑州大学;2004年

2 李海燕;图的平衡划分问题[D];南京师范大学;2014年

3 丁红林;限制性路由与网络构建问题[D];云南大学;2014年

4 王霖青;交通小区划分问题的整数规划建模与优化算法研究[D];东北大学;2014年

相关硕士学位论文 前10条

1 陈全中;图的平衡5—划分问题[D];华东师范大学;2020年

2 王婉;平衡划分问题极小反例的性质[D];南京师范大学;2019年

3 罗玉娇;图的平衡划分问题[D];华东师范大学;2018年

4 陶辛锴;有限图的内划分问题[D];中国科学技术大学;2017年

5 朱培培;边染色图的顶点划分问题[D];浙江师范大学;2012年

6 孙海晶;关于图平衡划分问题的一些结果[D];南京师范大学;2017年

7 胡晓臣;关于图的Judicious划分问题的研究[D];北京交通大学;2015年

8 张庆波;无线传感器网络中的控制划分问题研究[D];曲阜师范大学;2012年

9 赵筱萌;仲裁初始阶段的管辖权划分问题研究[D];山东大学;2014年

10 闫悦;歌唱声部划分问题研究[D];天津音乐学院;2014年

本文编号：2869256