稀疏图的顶点划分问题

发布时间：2023-04-27 22:06

　　图论是数学的一个分支,它以图为研究对象,图的顶点划分问题一直都是图论研究的热点之一,在图论研究中具有重要的理论意义,并且在计算机科学和信息科学等多个领域具有广泛的应用.关于图的顶点划分问题已经有了很多成果,最早的如著名的四色定理,即每个平面图都会有一个(I,I,I,I)-划分,这里的I代表的是独立集.稀疏图的(k,j)-划分指的是将图划分成两个部分,使得一个部分中的点的最大度小于等于k,另一个部分中的点的最大度小于等于j.一个图当围长大于等于5时会有一个(I,F)-划分,这里F代表的是森林.一个图G满足最大平均度小于12/5时会有一个(I,F₁)-划分,其中F₁指的是这个森林的每一个点的度数不超过1,等等.因此,找到合适的图类并研究它的顶点划分是非常有意义的.本论文主要研究稀疏图的顶点划分问题,总共分为四个章节.第一章主要介绍了有关本论文的一些定义和术语,还有国内外的有关顶点划分的一些研究,以及本论文用到的主要方法.第二章证明了在满足一定条件的图类中,若一个图的最大平均度至多是8/3,那么该图有一个(I,O₃)-划分,其...

【文章页数】：44 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 基本符号和定义
    1.2 关于稀疏图的顶点划分问题的已有结果
        1.2.1 关于图可以划分成I和F的研究结果
        1.2.2 关于图可以划分成F和Δ_k的研究结果
        1.2.3 关于图可以划分成P_k和P_k的研究结果
        1.2.4 关于图可以划分成I和O_k的研究结果
        1.2.5 关于图可以划分成Δ_k和Δ_j的研究结果
    1.3 本文主要方法
第二章 稀疏图的(I,O₃)-划分
    2.1 图类g₁的(I,O₃)-划分
    2.2 极小反例的结构特征
    2.3 权转移过程
第三章 稀疏图的(I,O₄)-划分
    3.1 图类g₂的(I,O₄)-划分
    3.2 极小反例的结构特征
    3.3 权转移过程
第四章 总结与展望
参考文献
致谢



本文编号：3803156