两类特殊图的消圈数和最大不可分独立集的研究
发布时间：2021-08-11 03:16
本文主要研究了莫比乌斯网格图Pm×Cn′（m=2,3,4,6,7）的消圈数问题以及循环图C（n,2,3）的消圈数,最大不可分独立集问题.第一章首先介绍了图论的起源与发展,图的消圈数以及最大不可分独立集问题的研究现状和部分重要成果.接着介绍了文中需要用到的一些基本定义定理以及本文的研究成果.第二章考虑了影响莫比乌斯网格图Pm×Cn′（m=2,3,4,6,7）消圈数的三个因素:度数,独立性,余图的连通分支数,得到消圈数的下界.之后根据图的结构特征采用分析法,列举法提高下界值并在图中找到对应的消圈点从而证明了取等条件成立.第三章第一节考虑了影响循环图C（n,2,3）消圈数的两个因素:独立性,余图的连通分支数,得到消圈数下界.之后根据消圈点的独立性和圈的存在性,采用反证法提高下界值并在图中找到对应的消圈点从而证明了取等条件成立.第二节在前一节已证明循环图C（n,2,3）消圈数的情况下,结合四正则图独立集的上界,用列举法证明了当n=6k+1,6k+3,6k+4,6k...
【文章来源】：华东师范大学上海市 211工程院校 985工程院校 教育部直属院校
【文章页数】：58 页
【学位级别】：硕士
【部分图文】：
P4×C′nS,n为奇数
华东师范大学硕士学位论文当n为奇数时,取S={v1,1,v2,1,v2,3,v2,5,v2,7...v2,n,v3,2,v3,4,v3,6...v3,n1}.此时|S|=n+1且GS无圈,如下图2.26所示.当n为偶数时,取S={v4,1,v2,1,v2,3,v2,5,v2,7...v2,n1,v3,2,v3,4,v3,6...v3,n}.此时|S|=n+1且GS无圈,如下图2.27所示.图2.26P4×C′nS,n为奇数图2.27P4×C′nS,n为偶数从而,(P4×C′n)=n+1.□2.4P6×C′n的消圈数定理2.9(P6×C′n)=5n+23,n=3k,3k+1,3k+2(k为奇数),k≥1;5n+23+1,n=3k+2(k为偶数),k≥2.证明由推论2.6知：(P6×C′n)≥6nn+23=5n+23.当n=3k(k≥1),5n+23=5×3k+23=5k+1.当n=3k+1(k≥1),5n+23=5×(3k+1)+23=5k+3.当n=3k+2(k≥1),5n+23=5×(3k+2)+23=5k+4.情形1:当n=3k(k≥1),(P6×C′3k)≥5k+1.1.当k为奇数时,取S={v6,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...v2,3k2,v3,3k1,v5,3k1,v2,3k,v4,3k},其中0≤m<k321.此时|S|=5k+1且余图P6×C′3kS无圈,如下图2.28所示.2.当k为偶数时,取S={v6,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...},17
华东师范大学硕士学位论文其中0≤m<k22.此时|S|=5k+1且余图P6×C′3kS无圈,如下图2.29所示.图2.28P6×C′3kS,k为奇数图2.29P6×C′3kS,k为偶数从而,(P6×C′3k)=5k+1.下面举例说明.例2.1(P6×C′9)=16.(P6×C′6)=11.在图P6×C′9中取消圈集：S={v6,1,v2,1,v3,2,v5,2,v2,3,v4,3,v5,4,v2,5,v4,5,v3,6,v5,6,v2,7,v3,8,v5,8,v2,9,v4,9}.则|S|=16且余图P6×C′9S无圈,如下图2.30所示.在图P6×C′6中取消圈集：S={v6,1,v2,1,v3,2,v5,2,v2,3,v4,3,v5,4,v2,5,v4,5,v3,6,v5,6}.则|S|=11且余图P6×C′6S无圈,如下图2.31所示.图2.30P6×C′9S图2.31P6×C′6S情形2.当n=3k+1(k≥0),(P6×C′3k+1)≥5k+3.1.当k为奇数时,取S={v5,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...v1,3k+1,v4,3k+1},其中0≤m<k321.此时|S|=5k+3且余图P6×C′3k+1S无圈,如下图2.32所示.18
【参考文献】：
期刊论文
[1]路与圈的笛卡尔乘积图的消圈数[J]. 沈传锦. 山西师范大学学报(自然科学版). 2010(04)
[2]完全图与树、圈、完全图、完全二部图的笛卡尔乘积图的消圈数[J]. 沈传锦. 海南大学学报(自然科学版). 2009(04)
[3]蛇形图的消圈公式[J]. 侯剑萍. 福州大学学报(自然科学版). 2009(05)
硕士论文
[1]Halin图消圈数及点染色问题的研究[D]. 王永强.华东师范大学 2015
[2]几类图的消圈数问题[D]. 庄翠花.华东师范大学 2014
本文编号：3335336
【文章来源】：华东师范大学上海市 211工程院校 985工程院校 教育部直属院校
【文章页数】：58 页
【学位级别】：硕士
【部分图文】：
P4×C′nS,n为奇数
华东师范大学硕士学位论文当n为奇数时,取S={v1,1,v2,1,v2,3,v2,5,v2,7...v2,n,v3,2,v3,4,v3,6...v3,n1}.此时|S|=n+1且GS无圈,如下图2.26所示.当n为偶数时,取S={v4,1,v2,1,v2,3,v2,5,v2,7...v2,n1,v3,2,v3,4,v3,6...v3,n}.此时|S|=n+1且GS无圈,如下图2.27所示.图2.26P4×C′nS,n为奇数图2.27P4×C′nS,n为偶数从而,(P4×C′n)=n+1.□2.4P6×C′n的消圈数定理2.9(P6×C′n)=5n+23,n=3k,3k+1,3k+2(k为奇数),k≥1;5n+23+1,n=3k+2(k为偶数),k≥2.证明由推论2.6知：(P6×C′n)≥6nn+23=5n+23.当n=3k(k≥1),5n+23=5×3k+23=5k+1.当n=3k+1(k≥1),5n+23=5×(3k+1)+23=5k+3.当n=3k+2(k≥1),5n+23=5×(3k+2)+23=5k+4.情形1:当n=3k(k≥1),(P6×C′3k)≥5k+1.1.当k为奇数时,取S={v6,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...v2,3k2,v3,3k1,v5,3k1,v2,3k,v4,3k},其中0≤m<k321.此时|S|=5k+1且余图P6×C′3kS无圈,如下图2.28所示.2.当k为偶数时,取S={v6,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...},17
华东师范大学硕士学位论文其中0≤m<k22.此时|S|=5k+1且余图P6×C′3kS无圈,如下图2.29所示.图2.28P6×C′3kS,k为奇数图2.29P6×C′3kS,k为偶数从而,(P6×C′3k)=5k+1.下面举例说明.例2.1(P6×C′9)=16.(P6×C′6)=11.在图P6×C′9中取消圈集：S={v6,1,v2,1,v3,2,v5,2,v2,3,v4,3,v5,4,v2,5,v4,5,v3,6,v5,6,v2,7,v3,8,v5,8,v2,9,v4,9}.则|S|=16且余图P6×C′9S无圈,如下图2.30所示.在图P6×C′6中取消圈集：S={v6,1,v2,1,v3,2,v5,2,v2,3,v4,3,v5,4,v2,5,v4,5,v3,6,v5,6}.则|S|=11且余图P6×C′6S无圈,如下图2.31所示.图2.30P6×C′9S图2.31P6×C′6S情形2.当n=3k+1(k≥0),(P6×C′3k+1)≥5k+3.1.当k为奇数时,取S={v5,1,v2,6m+1,v3,6m+2,v5,6m+2,v2,6m+3,v4,6m+3,v5,6m+4,v2,6m+5,v4,6m+5,v3,6m+6,v5,6m+6...v1,3k+1,v4,3k+1},其中0≤m<k321.此时|S|=5k+3且余图P6×C′3k+1S无圈,如下图2.32所示.18
【参考文献】：
期刊论文
[1]路与圈的笛卡尔乘积图的消圈数[J]. 沈传锦. 山西师范大学学报(自然科学版). 2010(04)
[2]完全图与树、圈、完全图、完全二部图的笛卡尔乘积图的消圈数[J]. 沈传锦. 海南大学学报(自然科学版). 2009(04)
[3]蛇形图的消圈公式[J]. 侯剑萍. 福州大学学报(自然科学版). 2009(05)
硕士论文
[1]Halin图消圈数及点染色问题的研究[D]. 王永强.华东师范大学 2015
[2]几类图的消圈数问题[D]. 庄翠花.华东师范大学 2014
本文编号：3335336
本文链接：https://www.wllwen.com/kejilunwen/yysx/3335336.html
