论文部分内容阅读
本论文主要研究了图的judicious划分问题及平衡judicious划分问题.研究主要基于Bollobás和Scott提出的一个问题:是否任何有m条边的图G都存在顶点集V(G)的一个k-划分V1,…,Vk,使得e(Vi)≤m/k2+k-1/2k2h(m),i=1,…,k和e(V1,…,Vk)=∑1≤i<j≤ke(Vi,Vj)≥ k-1/km+k-1/2kh(m)-k2-4k+4/8k同时成立,此处h(m)=√2m+1/4-1/2?以及一个猜想:每一个有m条边且最小度不小于2的图G都存在顶点集V(G)的一个平衡二部划分V1,V2,使得max{e(V1),e(V2)}≤m/3成立,此处e(Vi)表示两顶点都在Vi(i=1,2)中的边的条数.研究了图的judicious3-划分问题以及最大度和最小度之差不超过2的图的平衡judicious划分问题.并且在郁星星,许宝刚,颜娟等人的研究基础上,将结果进一步改进,使其更加接近问题和猜想. 第一章:对图的划分问题的相关概念及研究背景进行简要介绍;详细描述了图的judicious划分和平衡judicious划分问题;对文章的结构及内容进行简介. 第二章:总结了图的judicious k-划分问题和正则图,(k,k-1)-双正则图的平衡judicious划分问题的已有研究结果. 第三章:主要研究了图的judicious3-划分问题,也就是judicious k-划分问题的一种情形.当k=3时改进了郁星星和许宝刚关于该问题的结果. 第四章:给出了满足△(G)-δ(G)≤2的图的平衡judicious划分问题的结果,此结果覆盖了颜娟,许宝刚关于(k,k-1)-双正则图的平衡judicious划分问题的结论. 第五章:列出了一些与judicious划分相关的公开问题以及对这些问题的一些思考.