导读:本文包含了图的圆边染色论文开题报告文献综述及选题提纲参考文献，主要关键词:图,图的圆染色,图的圆边染色,笛卡尔积图
图的圆边染色论文文献综述
程志[1]（2008）在《一些图的圆边染色》一文中研究指出本文考虑的图若无特殊声明均为简单图。一个简单图的k可边染色是一个从含k种颜色的色集到图G的边集合的映射，并且使得相邻两边染不同的颜色。对于一个七可边染色的图G来说，最小的七就是图G的边色数。Vince提出了图的圆染色的概念，图的圆边染色就是图的圆染色由点到边的推广。图G是一个图，正整数k，d满足2d≤k，那么图的(k，d)边染色是指从颜色集{0，1，…，k-1}到图G的边的映射c，并且任意相邻的两边e_1，e_2满足d≤|c(e_1)-c(e_2)|≤l-d．图G的圆边染色数χ'_c(G)就是图G含有(k，d)边染色中的k／d比值的下界。即：χ'_c(G)=inf{k／d：G含有一个(k，d)边染色)．图的圆边染色的许多基本性质被Hackmmnn证明：定理0．1 [3]如果G是一个含有q条边的图，那么χ'_c(G)=min{k／d：G含有一个(k，d)边染色且k≤q}．定理0．2 [3]如果G是第一类图，那么χ'_c(G)=△(G)．如果G是第二类图，那么△(G)<χ'_c(G)≤△(G)+1．定理0．3 [3]如果图G是第二类图，那么要么χ'_c(G)=△(G)+1要么△(G)+1/α'(G)≤χ'_c(G)≤△(G)+α'(G)-1/α'(G)(其中α'(C)是图G的边独立数)第一类图的圆边染色问题已经解决，而许多第二类图的圆边染色问题没有得以解决。所以本文研究的主要是一些第二类图的圆边染色性质。由于这个问题是一个NP问题，所以本文的思想就是确定某第二类图的范围。而确定χ'_c(G)，就要从定义出发，找寻(k，d)染色。找出上述范围的k_1，k_2，k_3，…，k_n，d_1，…，d_n，u_G=k_1/d_1>k_2/d_2>…>k_n/d_n=l_G，检验图G是否含有(k_2，d_2)染色，如果没有，χ'_c(G)=k_1/d_1；如果含有(k_2，d_2)染色，继续检验(k_3，d_3)染色，依次类推。本文根据以上算法来确定一些图的圆边染色。全文共分四章，第一章介绍图论的一些基本概念，并给出图的染色理论的已有定理证明及圆边染色的理论。第二章介绍解决圆边染色的算法。第叁章我们给出了顶点数小于7的所有第二类图的圆边染色数。主要结论有：定理0．4在顶点小于7的所有第二类图中，其圆边染色数：χ'_c(G_1)=3，χ'_c(G-2)=5/2，χ'_c(G_3)=4，χ'_c(G_4)=9/2，χ'_c(G_5)=5，χ'_c(G_6)=4，χ'_c(G_7)=5，χ'_c(G_8)=5．定理0．5如果G是一个C_3×C_3的笛卡尔积图，那么其圆边色数为：χ'_c(G)=χ(G)=5．第四章给出了一类链图H_n的圆边染色数及其证明。定理0．6定义H_n是如图4，具体定义如下：V(H_n)={a_i，b_i，c_i，d_i，m_i，n_i：i=1，…，n}∪{v}．E(H_n)={a_ib_i，b_ic_i，c_id_i，d_im_i，m_in_i，n_ia_i，b_im_i，c_in_i，d_ia_(i+1)：i=1，…，n}∪{va_1}其中a_(n+1)=v．那么，χ'_c(H_n)=3+1/n．(本文来源于《山东大学》期刊2008-04-10）
王光辉[2]（2007）在《边染色图中的匹配、圈及图的圆染色》一文中研究指出图论的研究始于200多年前。关于图论的第一篇论文是1736年Euler发表的，他用图的方法解决了哥尼斯堡(K(?)nigsberg)七桥问题。二十世纪六十年代以来，图论在科学界异军突起，活跃非凡。图论中有很多着名的问题，如哈密尔顿问题，四色问题，中国邮递员问题等。并且，应用图论来解决化学，生物学，信息和计算机科学等学科问题已显示出极大的优越性。同时，图论在工程技术领域及社会科学中也有着广泛的应用。它作为离散数学的一个重要分支，受到了各方面的普遍重视。我们用G表示一个图，若G的每条边都染上颜色，则称G为边染色图。给定一个边染色图G，关联于顶点v的不同颜色的边的数目，称为顶点v的色度，记为d~c(v)。如果把一般的未染色图看作是每条边都染不同颜色的边染色图，则顶点的色度就等于它的度。除了在图论和算法上的重要应用外，边染色中的许多问题还出现在分子生物科学，心理学和网络通信等其它的领域中。因此，近年来，这方面的研究变得活跃起来，主要集中在边染色图中某些特殊子图的存在性上。边染色图中的子图，如果任意相邻的两条边的颜色都不相同，我们称之为交错子图，或者称为边正常染色子图。进一步，如果该子图中所有边的颜色都不相同，我们称之为彩色子图。这两类子图的研究尤其受到关注。图的匹配，路和圈是图论中的基础研究领域，因此边染色图中的彩色的(交错的)匹配，路和圈就成了一个重要的研究方向。图中过每个顶点的圈，称为图的哈密尔顿圈。图的哈密尔顿圈问题，是图论中的一个经典问题。其中一个着名的猜想是Chvátal[20]提出的如下猜想：韧度充分大的图有一个哈密尔顿圈。对于许多特殊的图类，例如弦图和平面图，上述猜想被证明是成立的[11，12，23]。图G的一条k-途径是指G的一条经过每个顶点至多k次的闭支撑途径。图的一个哈密尔顿圈就是图的1-途径。作为哈密尔顿圈的一个非常有趣的变形，图的k-途径引起了很多人的兴趣。Jackson和wormald[54]研究了k-途径，并猜想任意1-坚韧图都有一条2-途径。这个猜想仍然没有得到证明，最好的结果是任意4-坚韧图都有一条2-途径[37]。自然地，我们会考虑如下问题：确定最小的整数k=k(Δ)使得对最大度为Δ的任意图都有一条k-途径。对于一般图，这个问题是平凡的，因为最大度为Δ的任意树都有Δ-途径[54]，但对于k＜Δ，不含任何k-途径。但如果我们考虑无桥图(2-边连通图)，情况就不一样了。我们在第五章中，讨论了这个问题。另一方面，图的染色理论在图论中占有很重要的地位。近年来，图的圆染色的研究变的异常活跃，得到了一系列漂亮的结果，也产生了许多新颖的研究方法，逐渐成为图的染色理论中的一个重要分支。图的选择数(列表色数)是图的一个很重要的参数，其中一个着名的定理是Thomassen[81]的关于平面图的5-可选择性的证明。最近，Zhu[89]和Mohar[69]给出了圆选择数的概念，因此，对平面图的圆选择数的研究也就成了一个非常有意义的研究方向。另外，Bokal等[69]考虑了有向图的圆染色，把色数和圆色数的概念推广到有向图。因此，许多关于无向图中的染色和圆染色方面的问题，我们都可以在有向图中考虑。本文研究了图论中的几个问题，具体地，我们研究了边染色图中的匹配和圈，图的k-途径和图的圆染色。全文共分为七章。第一章，我们给出了一个简短但相对完整的综述。首先，我们给出了一些基本的定义和术语，并且对上述叁个方向的研究进展分别做了介绍。最后，我们列出了本文的主要结果。在第二章，我们考虑了边染色图中的彩色匹配问题。边染色图中的一个彩色匹配是指任意两条边的颜色都不相同的一个匹配。在一般的未染色图中，最大匹配问题(找一个边数最多的匹配)是多项式可解的([61])。而在边染色图中，即使是在边染色二部图中，最大彩色匹配问题(找一个边数最多的彩色匹配)是NP-完全的([45])。因此，彩色匹配的研究主要集中在边染色完全图和边染色完全二部图中。Erd(?)s和Pósa[30]研究了极值图论中的一个很基本的问题，他们证明了任意一个顶点个数至少为2k，最小度至少为k的图，都有一个k条边的匹配。我们在边染色图中研究了类似的问题。我们证明了若G是一个边染色图，并且对任意点v都有d~c(v)≥k≥4，则G含有一个有[(5k-3)／12]条边的彩色匹配。我们还证明了若G是一个边染色二部图，并且对任意顶点v，都有d~c(v)≥k≥3，则G有一个[2k／3]条边的彩色匹配。并且，我们给出了色邻域的概念，研究了边染色二部图中，满足某种色邻域条件的彩色匹配问题。在第叁章，我们研究了边染色图中的彩色圈。首先，我们给出了边染色图存在彩色圈的色度条件。并且，我们运用关于Caccetta-H(?)ggkvist猜想(有向图中有向叁角形存在性)的一个结果，得到了边染色图存在彩色叁角形或者彩色四边形的色度条件。同时，我们还研究了边染色图中的长彩色圈。在第四章，我们讨论了边染色图中色度和交错圈的关系，得到了边染色图中几类特殊交错圈存在的色度条件。同时，我们还对Bollobás-Erd(?)s猜想(边染色完全图中的交错哈密尔顿圈的存在性)做了研究，给出了满足Bollobás-Erd(?)s条件的边染色完全图中，最长交错圈的圈长的一个下界。在第五章，我们研究了图的k-途径，证明了最大度为Δ的任意无桥图(2-边连通图)都有一条[(Δ+1)／2]-途径，并且证明了这个界是最好可能的。在第六章，我们考虑Mohar[69]提出的关于平面图的圆选择数的一个问题，研究了具有大围长的平面图的圆选择数。我们证明了围长至少为(10n+8)／3的平面图的圆选择数至多为2+2／n，从而改进了[53]中的结果。另外，我们还讨论了几类特殊平面图(系列平行图，外平面图，奇轮)的圆选择数。在第七章，我们沿用[71]中的定义，对有向图的染色和圆染色做了进一步的研究。我们证明了如果一个有向图D的补图不含有向的哈密尔顿圈，则D的圆色数x_c(D)等于它的色数x(D)。我们还得出，给定一个正常k-染色的有向图D，k=x(D)，则D中存在有向路过这k种颜色。这些结果分别对无向图中的相应的结果做了推广。另外，在每一章里面，我们都提出了几个可以进一步考虑的问题和未解决的猜想。(本文来源于《山东大学》期刊2007-04-10）
图的圆边染色论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
图论的研究始于200多年前。关于图论的第一篇论文是1736年Euler发表的，他用图的方法解决了哥尼斯堡(K(?)nigsberg)七桥问题。二十世纪六十年代以来，图论在科学界异军突起，活跃非凡。图论中有很多着名的问题，如哈密尔顿问题，四色问题，中国邮递员问题等。并且，应用图论来解决化学，生物学，信息和计算机科学等学科问题已显示出极大的优越性。同时，图论在工程技术领域及社会科学中也有着广泛的应用。它作为离散数学的一个重要分支，受到了各方面的普遍重视。我们用G表示一个图，若G的每条边都染上颜色，则称G为边染色图。给定一个边染色图G，关联于顶点v的不同颜色的边的数目，称为顶点v的色度，记为d~c(v)。如果把一般的未染色图看作是每条边都染不同颜色的边染色图，则顶点的色度就等于它的度。除了在图论和算法上的重要应用外，边染色中的许多问题还出现在分子生物科学，心理学和网络通信等其它的领域中。因此，近年来，这方面的研究变得活跃起来，主要集中在边染色图中某些特殊子图的存在性上。边染色图中的子图，如果任意相邻的两条边的颜色都不相同，我们称之为交错子图，或者称为边正常染色子图。进一步，如果该子图中所有边的颜色都不相同，我们称之为彩色子图。这两类子图的研究尤其受到关注。图的匹配，路和圈是图论中的基础研究领域，因此边染色图中的彩色的(交错的)匹配，路和圈就成了一个重要的研究方向。图中过每个顶点的圈，称为图的哈密尔顿圈。图的哈密尔顿圈问题，是图论中的一个经典问题。其中一个着名的猜想是Chvátal[20]提出的如下猜想：韧度充分大的图有一个哈密尔顿圈。对于许多特殊的图类，例如弦图和平面图，上述猜想被证明是成立的[11，12，23]。图G的一条k-途径是指G的一条经过每个顶点至多k次的闭支撑途径。图的一个哈密尔顿圈就是图的1-途径。作为哈密尔顿圈的一个非常有趣的变形，图的k-途径引起了很多人的兴趣。Jackson和wormald[54]研究了k-途径，并猜想任意1-坚韧图都有一条2-途径。这个猜想仍然没有得到证明，最好的结果是任意4-坚韧图都有一条2-途径[37]。自然地，我们会考虑如下问题：确定最小的整数k=k(Δ)使得对最大度为Δ的任意图都有一条k-途径。对于一般图，这个问题是平凡的，因为最大度为Δ的任意树都有Δ-途径[54]，但对于k＜Δ，不含任何k-途径。但如果我们考虑无桥图(2-边连通图)，情况就不一样了。我们在第五章中，讨论了这个问题。另一方面，图的染色理论在图论中占有很重要的地位。近年来，图的圆染色的研究变的异常活跃，得到了一系列漂亮的结果，也产生了许多新颖的研究方法，逐渐成为图的染色理论中的一个重要分支。图的选择数(列表色数)是图的一个很重要的参数，其中一个着名的定理是Thomassen[81]的关于平面图的5-可选择性的证明。最近，Zhu[89]和Mohar[69]给出了圆选择数的概念，因此，对平面图的圆选择数的研究也就成了一个非常有意义的研究方向。另外，Bokal等[69]考虑了有向图的圆染色，把色数和圆色数的概念推广到有向图。因此，许多关于无向图中的染色和圆染色方面的问题，我们都可以在有向图中考虑。本文研究了图论中的几个问题，具体地，我们研究了边染色图中的匹配和圈，图的k-途径和图的圆染色。全文共分为七章。第一章，我们给出了一个简短但相对完整的综述。首先，我们给出了一些基本的定义和术语，并且对上述叁个方向的研究进展分别做了介绍。最后，我们列出了本文的主要结果。在第二章，我们考虑了边染色图中的彩色匹配问题。边染色图中的一个彩色匹配是指任意两条边的颜色都不相同的一个匹配。在一般的未染色图中，最大匹配问题(找一个边数最多的匹配)是多项式可解的([61])。而在边染色图中，即使是在边染色二部图中，最大彩色匹配问题(找一个边数最多的彩色匹配)是NP-完全的([45])。因此，彩色匹配的研究主要集中在边染色完全图和边染色完全二部图中。Erd(?)s和Pósa[30]研究了极值图论中的一个很基本的问题，他们证明了任意一个顶点个数至少为2k，最小度至少为k的图，都有一个k条边的匹配。我们在边染色图中研究了类似的问题。我们证明了若G是一个边染色图，并且对任意点v都有d~c(v)≥k≥4，则G含有一个有[(5k-3)／12]条边的彩色匹配。我们还证明了若G是一个边染色二部图，并且对任意顶点v，都有d~c(v)≥k≥3，则G有一个[2k／3]条边的彩色匹配。并且，我们给出了色邻域的概念，研究了边染色二部图中，满足某种色邻域条件的彩色匹配问题。在第叁章，我们研究了边染色图中的彩色圈。首先，我们给出了边染色图存在彩色圈的色度条件。并且，我们运用关于Caccetta-H(?)ggkvist猜想(有向图中有向叁角形存在性)的一个结果，得到了边染色图存在彩色叁角形或者彩色四边形的色度条件。同时，我们还研究了边染色图中的长彩色圈。在第四章，我们讨论了边染色图中色度和交错圈的关系，得到了边染色图中几类特殊交错圈存在的色度条件。同时，我们还对Bollobás-Erd(?)s猜想(边染色完全图中的交错哈密尔顿圈的存在性)做了研究，给出了满足Bollobás-Erd(?)s条件的边染色完全图中，最长交错圈的圈长的一个下界。在第五章，我们研究了图的k-途径，证明了最大度为Δ的任意无桥图(2-边连通图)都有一条[(Δ+1)／2]-途径，并且证明了这个界是最好可能的。在第六章，我们考虑Mohar[69]提出的关于平面图的圆选择数的一个问题，研究了具有大围长的平面图的圆选择数。我们证明了围长至少为(10n+8)／3的平面图的圆选择数至多为2+2／n，从而改进了[53]中的结果。另外，我们还讨论了几类特殊平面图(系列平行图，外平面图，奇轮)的圆选择数。在第七章，我们沿用[71]中的定义，对有向图的染色和圆染色做了进一步的研究。我们证明了如果一个有向图D的补图不含有向的哈密尔顿圈，则D的圆色数x_c(D)等于它的色数x(D)。我们还得出，给定一个正常k-染色的有向图D，k=x(D)，则D中存在有向路过这k种颜色。这些结果分别对无向图中的相应的结果做了推广。另外，在每一章里面，我们都提出了几个可以进一步考虑的问题和未解决的猜想。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
图的圆边染色论文参考文献
[1].程志.一些图的圆边染色[D].山东大学.2008
[2].王光辉.边染色图中的匹配、圈及图的圆染色[D].山东大学.2007