边着色论文_陶艳亮,黄琼湘,陈琳

导读:本文包含了边着色论文开题报告文献综述、选题提纲参考文献及外文文献翻译,主要关键词:广义,下界,图区,系列,松驰,标号,矩阵。

边着色论文文献综述

陶艳亮,黄琼湘,陈琳[1](2019)在《图的区间边着色的收缩图方法》一文中研究指出图G的一个用了颜色1,2,…,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的,且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作■.对图G∈■,使得G有一个区间t-着色的t的最小值和最大值分别记作ω(G)和W(G).现给出了图的区间着色的收缩图方法.利用此方法,我们对双圈图G∈■,证明了ω(G)=△(G)或△(G)+1,并且完全确定了ω(G)=△(G)及ω(G)=△(G)+1的双圈图类.(本文来源于《运筹学学报》期刊2019年02期)

陈勋,黄琼湘,陈琳[2](2019)在《广义θ-链的区间边着色》一文中研究指出如果图G的一个边着色用了1,2,…,t中的所有颜色,并且关联于G的同一个顶点的边上的颜色各不相同,且这些颜色构成了一个连续的整数区间,则称这个边着色是G的区间t-着色。如果对某个正整数t,G有一个区间t-着色,则称G是可区间着色的。所有可区间着色的图构成的集合记作N。图G的亏度def(G)是粘在G的顶点上使它可区间着色的悬挂边的最小数目,显然,G∈N当且仅当def(G)=0。广义θ-链是把路P=[v_0,v_1,…,v_k](k≥1)的每一条边v_(i-1)v_i(i=1,2,…,k),用m_i≥2条两两内部不交的(v_(i-1),v_i)-路替换掉而得到的简单图,记作θ_(m_1,m_2,…,m_k)。把广义θ-图亏度的结论进行推广,确定了θ_(m_1,m_2,…,m_k)的亏度。(本文来源于《山东大学学报(理学版)》期刊2019年06期)

姚敏[3](2019)在《关于某些特殊图类的边着色的1-2-3猜想》一文中研究指出1-2-3猜想断言:对任意一个阶数至少为3的连通图均有用{1,2,3}进行标号的邻点可区别的边标号,此猜想是由Karo′nski,?uczak以及Thomason在2004年提出的。本文主要研究了关于树、格子图以及广义Petersen图的1-2-3猜想,并通过数学归纳法和标号法证明了1-2-3猜想对于树、格子图以及部分广义Petersen图成立。(本文来源于《华东师范大学》期刊2019-05-01)

陈勋[4](2018)在《广义θ-链的区间边着色》一文中研究指出图的着色问题是一个被广泛研究的组合优化问题,是图论的一个重要研究领域.图的着色问题不仅在图论研究中起到重要作用,而且广泛地应用于计算机,通讯网络,地理等.区间边着色是图着色的一个重要研究分支,其概念是由Asratian和Ka-malian在1987年中提出来的,用来解决时间表等问题.对于给定的图,寻找它的一个区间边着色是一个比较难的工作.事实上,一个二部图是否存在一个区间边着色是一个NP-完备的.图G的一个用了颜色1,2,...,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上颜色各不相同且这些颜色构成了一个连续的整数区间.图G称作是可区间边着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间边着色的图构成的集合记作N.图G的亏度def(G)是粘在G的顶点上使它可区间边着色的悬挂边的最小数目.广义θ-链,记作θ_(m1,m2,...,mk),是把路P=[v_0,v_1,...,v_k](k≥1)的每一条边v_(i-1)v_i,这里i=1,2,...,k,用m_i≥2条两两内部不交的(v_(i-1),v_i)-路替换掉而得到的简单图.全文共分为两章.第一章,首先介绍了区间边着色的研究背景及相关应用,以及区间边着色的刻画问题;其次介绍了一些有用的定义和符号;最后列出了区间边着色的一些已有研究结果.第二章分为四个小节,第一节列出了一些与区间边着色相关的有用引理;第二节给出了广义θ-图的若干正常边着色;第叁节刻画了叁种特殊类型的广义θ-链;第四节完整地刻画了广义θ-链的亏度.(本文来源于《新疆大学》期刊2018-06-30)

张卫标,杨瑞[5](2018)在《两类图的无循环边着色》一文中研究指出为了研究Meredith图和系列平行图的无循环边着色问题,本文利用矩阵分析法、数学归纳法及其换色技巧,证明了若G_k是一个Meredith图,则有a'(G_k)=Δ(G_k),同时也证明了Δ(G)≥5的系列平行图的无循环边色数a'(G)≤Δ(G)+1。(本文来源于《河南理工大学学报(自然科学版)》期刊2018年04期)

李昕怡,苏振华[6](2018)在《基于边着色理论的排课问题的应用》一文中研究指出高校排课问题是数学和计算机领域的一个经典问题.本文在教师、班级、时间段叁者的约束限制下,利用图论中边着色理论进行算法设计,从而得到一种简单实用的高校排课系统的可行实施方案.(本文来源于《怀化学院学报》期刊2018年05期)

刘瑶[7](2018)在《图的强边着色问题的研究》一文中研究指出图G的强边着色是G的一个边着色,并且对于任意两条距离小于等于2的边颜色不同。图G的强边着色指数,记作χs'(G),表示图(G有强边着色所需要的最少颜色数。图的强边着色研究的核心问题是Erdos猜想:如果G的最大度为△,那么当△为偶数时,我们有χs'(G)≤5△2/4;当△为奇数时,我们有χs'(G)≤(5△2-2△+1)/4。图G的(s,t)-松弛强边着色是对强边着色的推广。给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ(s,t)'(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。本文证明了以下几个结果:1.在图G中,如果mad(G)<3并且△≤4,那么χ(1,0)'(G)≤3△;2.当△=3和△=4时,对于不同的最大平均度,我们给出χ(1,0)'((G)的上界;3.如果G是平面图,最大度△≥4并且围长最少为7,那么χ(1,0)'(G)≤3△-1。(本文来源于《天津大学》期刊2018-05-10)

张卫标,谢德政[8](2018)在《系列平行图和Meredith图的无循环边着色》一文中研究指出利用数学归纳法,通过构造染色,研究系列平行图和Meredith图的无循环边着色.证明了最大度Δ(G)≥5的系列平行图G的无循环边色数a′(G)≤Δ(G)+1;同时证明了对于Meredith图G_k,有a′(G_k)=Δ(G_k).(本文来源于《天津师范大学学报(自然科学版)》期刊2018年02期)

张卫标[9](2017)在《强边着色猜想问题的最优图》一文中研究指出着名图论专家Erds和Nesetǐil对图的强边色数上界提出了一个猜想:当最大度Δ为偶数时,χ's(G)≤5/4Δ~2;当最大度Δ为奇数时,χ's(G)≤1/4(5Δ~2-2Δ+1);并且给出了当Δ=4时的最优图.此处构造了一族图,并证明了当最大度为奇数时,如果Erd9s和Ne2etǐil提出的强边着色猜想成立,则猜想中的上界是最优的.(本文来源于《重庆工商大学学报(自然科学版)》期刊2017年03期)

陶艳亮[10](2017)在《图的区间边着色的收缩图方法》一文中研究指出图论作为数学的一个分支,近年来得到了较快发展和广泛应用,已广泛应用于运筹学,控制论,信息论和计算机科学等各个领域.一般说来,图的着色问题最早起源于着名的”四色问题”.由于图的着色问题反映了广泛而深刻的实际背景,它的研究带动了整个图论的发展.如今图着色理论被广泛应用于化学品的贮藏,考试日程和安排会议等许多实际问题上.图G的一个用了颜色1,2,...,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作N.对图G∈N,使得G有一个区间t-着色的t的最小值和最大值分别记作w(G)和W(G).本文中,我们给出了图的区间着色的收缩图方法.利用此方法我们对双圈图G∈N,证明了w(G)=?(G)或?(G)+1,并且完全确定了w(G)=?(G)及w(G)=?(G)+1的双圈图类.全文共分为叁章.第一章首先介绍了图着色的研究背景及相关应用,以及图的区间边着色的刻画问题;其次介绍了基本概念及术语;最后列出了图的区间边着色研究的一些已有结果.第二章给出了收缩图方法.第叁章主要利用前面的方法给出了双圈图区间边着色的下界.第叁章分为叁个小节.第一节中给出了双圈图G∈β∞的区间边着色的下界w(G);第二节中给出了双圈图G∈βθ的区间边着色的下界w(G);第叁节中给出了双圈图G∈β的区间着色的下界w(G).(本文来源于《新疆大学》期刊2017-05-29)

边着色论文开题报告

(1)论文研究背景及目的

此处内容要求:

首先简单简介论文所研究问题的基本概念和背景,再而简单明了地指出论文所要研究解决的具体问题,并提出你的论文准备的观点或解决方法。

写法范例:

如果图G的一个边着色用了1,2,…,t中的所有颜色,并且关联于G的同一个顶点的边上的颜色各不相同,且这些颜色构成了一个连续的整数区间,则称这个边着色是G的区间t-着色。如果对某个正整数t,G有一个区间t-着色,则称G是可区间着色的。所有可区间着色的图构成的集合记作N。图G的亏度def(G)是粘在G的顶点上使它可区间着色的悬挂边的最小数目,显然,G∈N当且仅当def(G)=0。广义θ-链是把路P=[v_0,v_1,…,v_k](k≥1)的每一条边v_(i-1)v_i(i=1,2,…,k),用m_i≥2条两两内部不交的(v_(i-1),v_i)-路替换掉而得到的简单图,记作θ_(m_1,m_2,…,m_k)。把广义θ-图亏度的结论进行推广,确定了θ_(m_1,m_2,…,m_k)的亏度。

(2)本文研究方法

调查法:该方法是有目的、有系统的搜集有关研究对象的具体信息。

观察法:用自己的感官和辅助工具直接观察研究对象从而得到有关信息。

实验法:通过主支变革、控制研究对象来发现与确认事物间的因果关系。

文献研究法:通过调查文献来获得资料,从而全面的、正确的了解掌握研究方法。

实证研究法:依据现有的科学理论和实践的需要提出设计。

定性分析法:对研究对象进行“质”的方面的研究,这个方法需要计算的数据较少。

定量分析法:通过具体的数字,使人们对研究对象的认识进一步精确化。

跨学科研究法:运用多学科的理论、方法和成果从整体上对某一课题进行研究。

功能分析法:这是社会科学用来分析社会现象的一种方法,从某一功能出发研究多个方面的影响。

模拟法:通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。

边着色论文参考文献

[1].陶艳亮,黄琼湘,陈琳.图的区间边着色的收缩图方法[J].运筹学学报.2019

[2].陈勋,黄琼湘,陈琳.广义θ-链的区间边着色[J].山东大学学报(理学版).2019

[3].姚敏.关于某些特殊图类的边着色的1-2-3猜想[D].华东师范大学.2019

[4].陈勋.广义θ-链的区间边着色[D].新疆大学.2018

[5].张卫标,杨瑞.两类图的无循环边着色[J].河南理工大学学报(自然科学版).2018

[6].李昕怡,苏振华.基于边着色理论的排课问题的应用[J].怀化学院学报.2018

[7].刘瑶.图的强边着色问题的研究[D].天津大学.2018

[8].张卫标,谢德政.系列平行图和Meredith图的无循环边着色[J].天津师范大学学报(自然科学版).2018

[9].张卫标.强边着色猜想问题的最优图[J].重庆工商大学学报(自然科学版).2017

[10].陶艳亮.图的区间边着色的收缩图方法[D].新疆大学.2017

论文知识图

5Sχ′(Γs4)=5的强边着色合理边着色示意图网络状态图G对应的一个正常5边着3“金刚”级宙斯盾作战系统的有向图模型...利用合理边着色或准强边着色执行点边着色策略后得到的上下...

标签:;  ;  ;  ;  ;  ;  ;  

边着色论文_陶艳亮,黄琼湘,陈琳
下载Doc文档

猜你喜欢