关于图的Judicious划分问题的研究

发布时间：2017-06-24 09:17

  本文关键词：关于图的Judicious划分问题的研究，，由笔耕文化传播整理发布。

【摘要】：本论文主要研究了图的judicious划分问题及平衡judicious划分问题.研究主要基于Bollobas和Scott提出的一个问题：是否任何有m条边的图G都存在顶点集V(G)的一个k-划分V1,...,Vk,使得e(Vi)≤m/k2+k-1/2k2h(m1),i=1,...,k和点集V(G)的一个平衡二部划分V1,V2,使得表示两顶点都在Vi(i=1,2)中的边的条数.研究了图的judicious3-划分问题以及最大度和最小度之差不超过2的图的平衡judicious划分问题.并且在郁星星,许宝刚,颜娟等人的研究基础上,将结果进一步改进,使其更加接近问题和猜想. 第一章：对图的划分问题的相关概念及研究背景进行简要介绍；详细描述了图的judicious划分和平衡judicious划分问题;对文章的结构及内容进行简介. 第二章：总结了图的judicious k-划分问题和正则图,(k,k-1)-双正则图的平衡judicious划分问题的已有研究结果. 第三章：主要研究了图的judicious3-划分问题,也就是judiciousk-划分问题的一种情形.当k=3时改进了郁星星和许宝刚关于该问题的结果. 第四章：给出了满足△(G)-δ(G)≤2的图的平衡judicious划分问题的结果,此结果覆盖了颜娟,许宝刚关于(k,k-1)-双正则图的平衡judicious划分问题的结论. 第五章：列出了一些与judicious划分相关的公开问题以及对这些问题的一些思考.
【关键词】：图 划分 平衡划分 度
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-9
• 第一章 绪论9-12
• 1.1 研究背景9-10
• 1.2 基本概念10-11
• 1.3 本文的主要研究工作11-12
• 第二章 judicious划分问题的已有研究成果12-14
• 2.1 关于judicious k-划分问题的已有工作介绍12
• 2.2 关于平衡judicious划分问题的已有工作介绍12-14
• 第三章 关于judicious 3-划分问题的研究成果14-25
• 3.1 概念介绍14
• 3.2 引理14-17
• 3.3 主要结论17-25
• 第四章 满足△(G)-δ(G)≤2的图的平衡judicious划分25-32
• 4.1 概念介绍25
• 4.2 主要结论25-32
• 第五章 可进一步研究的问题32-33
• 参考文献33-36
• 学位论文数据集36

【参考文献】

中国期刊全文数据库 前1条

1 颜娟;许宝刚;;(k,k-1)-双正则图的平衡Judicious Partitions(英文)[J];南京师大学报(自然科学版);2008年03期

  本文关键词：关于图的Judicious划分问题的研究，由笔耕文化传播整理发布。

本文编号：477726