导读:本文包含了消圈数论文开题报告文献综述及选题提纲参考文献，主要关键词:消圈数,点荫度,Brooks定理,3-正则图
消圈数论文文献综述
杨超,任韩[1]（2019）在《关于3-正则图的消圈数和点荫度的一个注记（英文）》一文中研究指出本文从图的嵌入角度考虑,给出了一个计算3-正则图的消圈数(见[J.Graph Theory,1997,25(1):59-77])的新公式.结合所得消圈数公式和Xuong的最大亏格定理(见[J.Combin.Theory Ser.B,1979,26(2):217-225]),进而得到了3-正则图的点荫度为2,此结果证明了Raspaud和王维凡在文献[European J.Combin.,2008,29(4):1064-1075]中给出的下列猜想:任何没有3-圈的平面图都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.(本文来源于《数学进展》期刊2019年04期）
袁利利[2]（2018）在《Sierpi(?)ski图类的消圈数》一文中研究指出图G的消圈数是指使图G变为无圈图而去掉的最少顶点个数.本文说明当Sierpi(?)ski图S_p~n满足p≥2和n≥1时,其消圈数为p~(n-1)(p-2).Sierpi(?)ski图的衍生图Sierpi(?)ski叁角图?S_p~n是由收缩Sierpi(?)ski图S_p~(n+1)的所有非团边得到的.我们将证明当p=3时,Sier-pi′nski叁角图的消圈数为其顶点数的叁分之一.当p≥4时,我们给出Sierpi(?)ski叁角图的消圈数的上界.本文主要研究了Sierpi(?)ski图类的消圈数,基本结构如下:在第一章中,主要介绍了Sierpi(?)ski图的定义、研究背景、以及文中所需的基本概念.在第二章中,我们证明了定理:当Sierpi(?)ski图S_p~n满足p≥2和n≥1时,其消圈数为p~(n-1)(p-2),以及Sierpi(?)ski类似图的消圈数.在第叁章中,我们研究了当p=3时,Sierpi(?)ski叁角图的消圈数为其顶点数的叁分之一,当p≥4时,Sierpi(?)ski叁角图的消圈数的上界。(本文来源于《新疆大学》期刊2018-06-04）
杨超[3]（2017）在《图的消圈数及相关问题研究》一文中研究指出图的消圈数问题是图论的重要问题之一,它源自于计算机科学,具有很强的理论意义和实际意义.随着图的消圈数问题在生产实践中被广泛应用,它逐渐成为众多学者研究的重要领域之一.截至目前,对消圈数问题的研究,已有了较为丰富的结果,并且这些结果仍在进一步完善之中.本文对消圈数及其相关问题进行了研究,全文共分为八章.第一章,介绍图论的一些相关背景和基本概念;列举了本文的主要工作.第二章,给出了消圈数的相关概念,介绍了平面图、立方图、超立方图、笛卡尔乘积图的消圈数的发展现状.第叁章,从图的独立集和覆盖集的角度出发,给出两种计算图的消圈数的新公式:(1)▽(G)= n-T max {α(G-E(T))};(2)▽(G)=T min {/β(G-E(T))},其中,T为G的生成树,α(G-E(T)):β(G-E(T))分别为余树G-E(T)的独立数和覆盖数.截至目前,关于稠密图消圈数的研究工作所知甚少,而上述公式则可以直接用来计算一些稠密图的消圈数.第四章,给出了一种计算k-正则图消圈数的新公式,▽(G)=c(G)+m(S)/k-1其中,c(G)=‖ G ‖-丨G丨+1,m(W)= c + ｜E(S)｜-1,c和｜E(S)｜分别表示G-W的分支数和导出子图G[S]的边数.在此基础上,解决了 3-正则图的消圈数,凭借3-正则图的消圈数,进一步得到了 3-正则图的一个顶点划分、点荫度以及邻点可区别全染色数.第五章,研究了结构较特殊的近4-正则Halin图,并得到了叁类含毛毛虫结构的近4-正则Halin图的消圈数.第六章,研究了一类平面叁角剖分图GnK4,并解决了此类图在n = 1,2,3,4时的消圈数.第七章,弱化了消圈数的条件,提出消除图中最短圈的概念,并得到(?)其中,(?)s(G)表示消去图G中所有最短圈所需要去掉的最少点数.第八章,给出了图的消圈数中几个可研究的课题.(本文来源于《华东师范大学》期刊2017-11-01）
任韩,魏二玲[4]（2016）在《消圈数与图的嵌入（英文）》一文中研究指出设▽(G)表示最少的点数,这些点去掉后图中无圈(即森林).称这个数▽(G)为图G的消圈数.通常,确定图的消圈数是NP完全的.Bau和Beineke曾提出以下问题:哪些阶数为n的3正则图G的消圈数满足▽(G)=[(n+2)/4]?本文回答了这个问题:阶数为n的3正则图G的消圈数满足▽(G)=[(n+2)/4]当且仅当G是上嵌入的(即以最多两个面嵌入在可定向曲面上).其次,对于一般3正则图,得出其消圈数的计算公式为▽(G)=γ_M(G)+ζ(G),这里γ_M(G)表示图的最大亏格,ζ(G)表示图G的Betti亏数.由此可知,3正则图的最大亏格的计算的多项式算法是存在的,所以3正则图的消圈数的计算也是多项式可解的.(本文来源于《数学进展》期刊2016年03期）
王永强[5]（2015）在《Halin图消圈数及点染色问题的研究》一文中研究指出图论知识在电路的设计和计算机操作系统中预防出现死循环等一系列实际问题中的应用引发了对通过去掉图中的一些点(当然也去掉了与这些点相连的边),从而破掉图中所有圈的问题的研究,也就是对消圈数问题的研究.图的最大诱导森林,图的独立数(最大独立集的阶数)等问题都与消圈数有密切关系,所以这一问题的研究在图论中起着十分重要的作用.要想更好的了解图的性质与结构,从研究图的消圈数入手不失为一个好的突破口.着名的四色猜想被提出来后,引发了人们对图的染色问题的研究,被染色的对象逐渐地变得越来越广泛,出现了点染色,边染色,面染色,全染色,强边染色等等.图的染色问题具有很重要的理论和实际应用价值,是图论一个重要的研究方向.图的染色问题,处理的是涉及任务分配之类的问题.编排课表问题,物品存放问题,时间表问题,网络电路的设计等均属于图的染色问题的范畴.虽然以上这两个问题很重要,但在对一般图的研究上举步维艰,人们更多时候是去研究一些特殊的图类并取得了一些进展.根据Tutte关于3-连通图的结构定理：每一个3-连通图都可由某个轮图(也是Halin图)经过顶点分裂逐步得到,由此可以看出Halin图在图的结构研究中的地位和作用.本文首先研究得到了近正则Halin图G的消圈数的上,下界；接下来构造得到了两类特殊的Halin图,用以证明我们得到的消圈数的上,下界是紧的,接着得到了最大度为k或最小度为k的Halin图的消圈数所满足的界；本文还研究了另外两类近4-正则Halin图的消圈数并确定了这两者的各一个最小消圈集；在最后,本文还对Halin图的点染色问题进行了研究,给出了点色数定理[1]的一种新证明.(本文来源于《华东师范大学》期刊2015-04-10）
庄翠花[6]（2014）在《几类图的消圈数问题》一文中研究指出在图中通过去掉一些点破坏圈的问题源于图论在组合电路设计,以及操作系统中预防出现死循环等问题中的应用.消圈数的研究在图论中起到非常重要的作用,它与图中最大森林的阶数、图的连通度、独立数等密切相关.探讨图的消圈数问题,有助于更好的认识图的结构和性质.本文主要讨论几类简单图的消圈数问题.给定有限简单无向图G=(V(G),E(G)),若S(?)V(G),且G-S是不含任何圈的图,则称S为G的一个消圈集.阶数最小的消圈集称为最小消圈集.图G的消圈数就是图G的最小消圈集的阶数,记为φ(G),即φ(G)=min{|S|:S(?)V(G)是G的消圈集}.本文首先根据Bau和Beineke[1]提出的消圈数与连通度的关系,讨论了消圈数是2或3的平面叁角剖分图G的结构.设S是G的一个最小消圈集：当G的消圈数是2时,G-S是一条路；当G的消圈数是3时,G-S的每个连通分支只可能是图6、7或8的结构.随后给出最大度不超过4的图满足特别地,若G不是4-正则图,则当图G(不一定是平面图)的最大度不超过4(除4-正则外)或是偶数个点的4-正则图时,证明了1976年Albertson和Berman[2]提出的关于平面图G的消圈数的猜想.此外,我们还研究了Halin图G(G=T∪C其中T是特征树,C是伴随圈)的消圈数满足并且指出3-正则Halin图可以保证这个界是紧的.这个结果说明1976年Albertson和Berman[2]提出的猜想对任意的Halin图也成立.(本文来源于《华东师范大学》期刊2014-04-10）
魏二玲,李益凡[7]（2013）在《广义Petersen图的消圈数与上可嵌入性》一文中研究指出给定图G=(V,E),S■V,若G-S(图G中去掉S中的点以及与其关联的所有边)是一个无圈图,则称S是图G的一个消圈集,且称min{|S|}S是图G的消圈集}为图的消圈数,记为▽(G).图的消圈数的求解是NP完全的.Bau和Beineke提出了如下问题:什么样的阶为2n的3正则图G,其消圈数为[(n+1)/2]?本文对广义Petersen图的消圈数进行了讨论,从而证明了这类图的消圈数恰好为[(n+1)/2].利用消圈集的性质,进一步可推出,这类图是上可嵌入的.(本文来源于《数学学报》期刊2013年02期）
沈传锦[8]（2011）在《路与路的字典乘积图的消圈数》一文中研究指出探讨了路与路的字典乘积图的消圈问题。对一般的路与路,推导出它们的字典乘积图的消圈数的一个紧的下界;对一些特殊的路与路,推导出它们的字典乘积图的消圈数的准确值。(本文来源于《唐山师范学院学报》期刊2011年05期）
沈传锦[9]（2010）在《路与圈的笛卡尔乘积图的消圈数》一文中研究指出探讨路与圈的笛卡尔乘积图的消圈问题,对一般的路与圈,根据引理1及推论1推导出它们的笛卡尔乘积图的消圈数的一个紧的下界;进而对一些特殊的路与圈,推导出它们的笛卡尔乘积图的消圈数的准确值.(本文来源于《山西师范大学学报(自然科学版)》期刊2010年04期）
沈传锦[10]（2009）在《路与圈的叉积图的消圈数》一文中研究指出研究了路与圈的叉积图的消圈数.对一般的路Pm和圈Cn,得到了Pm×Cn的消圈数的一个紧的下界;对一些特殊的路Pm和圈Cn,得到Pm×Cn的消圈数的准确值.(本文来源于《漳州师范学院学报(自然科学版)》期刊2009年04期）
消圈数论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
图G的消圈数是指使图G变为无圈图而去掉的最少顶点个数.本文说明当Sierpi(?)ski图S_p~n满足p≥2和n≥1时,其消圈数为p~(n-1)(p-2).Sierpi(?)ski图的衍生图Sierpi(?)ski叁角图?S_p~n是由收缩Sierpi(?)ski图S_p~(n+1)的所有非团边得到的.我们将证明当p=3时,Sier-pi′nski叁角图的消圈数为其顶点数的叁分之一.当p≥4时,我们给出Sierpi(?)ski叁角图的消圈数的上界.本文主要研究了Sierpi(?)ski图类的消圈数,基本结构如下:在第一章中,主要介绍了Sierpi(?)ski图的定义、研究背景、以及文中所需的基本概念.在第二章中,我们证明了定理:当Sierpi(?)ski图S_p~n满足p≥2和n≥1时,其消圈数为p~(n-1)(p-2),以及Sierpi(?)ski类似图的消圈数.在第叁章中,我们研究了当p=3时,Sierpi(?)ski叁角图的消圈数为其顶点数的叁分之一,当p≥4时,Sierpi(?)ski叁角图的消圈数的上界。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
消圈数论文参考文献
[1].杨超,任韩.关于3-正则图的消圈数和点荫度的一个注记（英文）[J].数学进展.2019
[2].袁利利.Sierpi(?)ski图类的消圈数[D].新疆大学.2018
[3].杨超.图的消圈数及相关问题研究[D].华东师范大学.2017
[4].任韩,魏二玲.消圈数与图的嵌入（英文）[J].数学进展.2016
[5].王永强.Halin图消圈数及点染色问题的研究[D].华东师范大学.2015
[6].庄翠花.几类图的消圈数问题[D].华东师范大学.2014
[7].魏二玲,李益凡.广义Petersen图的消圈数与上可嵌入性[J].数学学报.2013
[8].沈传锦.路与路的字典乘积图的消圈数[J].唐山师范学院学报.2011
[9].沈传锦.路与圈的笛卡尔乘积图的消圈数[J].山西师范大学学报(自然科学版).2010
[10].沈传锦.路与圈的叉积图的消圈数[J].漳州师范学院学报(自然科学版).2009