论文部分内容阅读
对图论的研究已经有二百多年的历史，最早关于图论的文章是在1736年由欧拉完成的，该文章解决了著名的哥尼斯堡七桥问题，自20世纪60年代以来，图论得到了迅猛发展，图论方面的结果大量涌现，其中图的染色理论在图论研究中占有重要的地位，图的染色理论在最优化，计算机理论，网络设计等方面都有着重要的应用，例如在网络中的数据传输，Hessians矩阵的计算等方面.本文旨在讨论图上有限制条件的几类染色问题，包括无圈染色，全染色，列表染色和f-染色.
本文所考虑的图都是有限简单图，我们用V（G）和E（G）分别表示图G的顶点集和边集，图G正常的k-全染色是指用k种颜色对V（G）∪ E（G）中的元素进行着色，使得相邻的或者相关联的两个元素染不同的颜色；使图G存在正常的k-全染色的最小正整数k称为G的全色数，记为x"（G）同样的，如果我们只对图G的顶点或者边的进行着色，分别可以得到图G的点色数x（G）和边色数x（G）图G的一个正常的点（或者边）染色称为无圈的，如果图G中不含2-色圈，换句话说，图G中任何染两种颜色的点（或者边）导出的子图是一棵森林，图G的无圈色数，用a（G）表示，是使图G存在无圈点染色所需的最少颜色数。同样地，图G的无圈边色数，用a（G）表示，是使图G存在无圈边染色所需的最少颜色数。设L是图G的一个颜色列表：对每个点ν∈V（G），给其一个颜色集合L（ν），如果图G存在一个无圈点染色φ使得对ν∈V（G），都有φ（ν）∈L（ν），则称图G是无圈L-可染的，如果对任意的颜色列表L满足：对ν∈V（G），有|L（ν）|≥k，图G都是无圈L-可染的，则称图G是无圈k-可选择的。
无圈染色问题作为一般染色问题的推广可用来有效的计算Hessians矩阵：如果已知Hessians矩阵是稀疏的和对称的，用有限差分方法来计算Hessians矩阵时可以转化为图的无圈染色问题.在2001，Alon，Sudakov和Zaks提出了如下猜想：
猜想1.对任意图G，都有α（G）≤△（G）+2.
本文将给出关于该猜想的一些结果.
对于全染色， Behzad和Vizing分别提出如下猜想，该猜想称为全染色猜想：
猜想2.对任意图G，都有△（G）+1≤x"（G）≤△（G）+2.
该猜想迄今还远没有解决，对平面图G，如果最大度△（G）≠6，则该猜想已经被验证，但是对一些曲面图来说，有时候全色数X"（G）可以唯一确定.确定曲面图的全色数将是本文讨论的问题之一.
本文讨论的另外一个问题是列表染色，如果对图G的每个元素x∈V（G）∪E（G），我们都其给一个染色集合L（x），则L称为G的全列表，如果图G存在全染色φ使得对任意的元素x∈V（G）∪ E（G），都有φ（x）∈L（x），则称图G是L-全可染的，令f：V（G）∪ E（G）→N是正整数函数，如果对任意的全列表L满足；对z∈V（G）∪ E（G），有|L（x）|=f（x），图G都是L-全可染的，则称G是f-全可选择的，使图G存在k-全可选择的最小正整数k称为图G的列表全色数，记为xl"（G）同样地，图G的列表色数xl（G）或列表边色数xl（G）分别是对G的顶点或边进行着色.
列表染色是由Vizing，Erdos，Rubin和Taylor分别提出的，下面猜想的（a）部分是由Vizing，Gupta，Albertson和Collins，Bollobas和Harris分别提出的，该猜想被称为列表染色猜想，（b）部分是由Borodin，Kostochka和Woodall等人提出的。
猜想3.如果图G是多重图，则有：
（a）xl（G）=x（G），（b）x"l（G）=x"（G）
对于猜想3，目前只有有限的几个结果.边染色中著名的Vizing定理表明：对最大度为△（G）的图G，有△（G）≤x（G）≤△（G）+1.结合猜想3以及Vizing定理和全染色猜想，显然有下面的猜想：
猜想4.对任意图G，都有
（a）xl（G）≤△（G）+1，（b）x"l（G）≤△（G）+2.
对简单图G，由Vizing定理可知，x（G）=△（G）或者x（G）=△（G）+1.有了这个结果，自然地可根据边色数把所有的图划分成两类：如果x（G）=△（G），我们称图G是第一类的；否则称其为第二类的。在1986年，Hakimi和Kariv将正常边染色推广到f-染色，并得到许多漂亮的结果，设f是给每个顶点ν∈V（G）分配一个正整数f（ν）的函数。图G的一个f-染色是G的一个边染色使得任何一种颜色在顶点ν处至多出现f（ν）次，使G存在一个f-染色所用的最少颜色数称为G的f-色数，记作xf（G）如果对任意的ν∈V（G），都有f（ν）=1，则f-染色问题就变成经典的边染色问题.
令△f（G）=max{[d（ν）/f（ν）]：ν∈V（G）}.Hakimi和Kariv得到如下结论：对任意图G，都有△f（G）≤xf（G）≤△f（G）+1.自然地，所有的简单图都可根据它们的f-色数将其划分成两类.更确切地，如果xf（G）=△f（G），则称G是f-第一类的；否则称G是f-第二类的。如果连通图G是f-第二类，并且满足对任意的e∈E（G）均有xf（G-e）
其他文献
本文对样条函数在数控加工中的应用和B样条对偶基的构造,这两方面分别进行了算法改进和重新构造。在实际应用中,本文一方面对已有的圆弧样条光顺方法作了改进,使之更适合实际
所谓的竞争性货币贬值,其本质就是各国政府通过压低本币汇率的方式,使国内出口部门获得竞争优势,从而保护或者扩大相关产业的市场份额,刺激经济复苏。历史表明,在全球经济大
针对稳定性理论在细胞神经网络中的巨大影响,本文主要探讨了多时滞细胞神经网络的全局指数稳定性,具有分布时滞联想记忆神经网络的全局渐近稳定性以及对Hopfield神经网络的全
作为一种生态经济发展形态,循环经济的“资源-生产-消费-再生资源”的物质能量循环过程与自然生态系统的物质能量从“生产者-消费者-分解者-再循环”的循环模式相比,缺乏真正
支持向量机(Support Vector Machine,SVM)是Vapnik等人根据统计学理论提出的一种机器学习方法。它是建立在VC维和结构风险最小化原则基础上的,利用核函数把非线性可分数据映
用边界元法来求解定义于无界区域上的Helmholtz方程外边值问题有效而且相对简单。但是通过边界积分方程求解任意波数的二维Helmholtz方程Dirichlet和Neumann外边值问题时，当波
非凸半定规划在控制论、扰动分析、系统工程以及电子工程等领域具有广泛的应用.近年来,求解非凸半定规划问题中有许多算法,如罚函数法、光滑化算法等,其中Lagrange乘子罚函数
本论文研究在缺失数据条件下，AR(p)模型参数的估计方法. 在文献中，使用EM算法或MCMC方法给出了一个数据和连续两个数据缺失时参数的估计方法.但是由于计算复杂，很难推广到连