论文部分内容阅读
Local Cut Lemma(简写成LCL)是近来由Bernshteyn在Lovasz Local Lemma(简写成 LLL)的相关算法-熵压缩方法对组合问题应用的基础上，对其进行了推广，它主要是用概率方法来解决图论中的一些组合优化问题。随着对树的研究，1970年，Harary[29]提出了图的线性荫度这一概念.线性有向森林是指每个部分都是路的有向图，而有向线性荫度是指能够将有向图D的所有弧覆盖的最少线性有向森林个数，用la(D)表示.对于每一个本正则有向图D, Nakayama和 Péroche猜测la(D)= d+1,随后He, Li, B ai和 Sun[31]研究了完全对称有向图和大围长正则有向图的线性荫度，并得出对任何d-正则有向图D,当围长g≥8.0786d时，la(D)= d+1。通过研究得到，对任何d-正则有向图，当 d=1时，la(D)= d+1;当 d≥2,且围长g＞8d时，la(D)= d+1.图 G的无圈着色是指正常点染色，并且每个圈上至少包含三种颜色.无圈着色指数Xa(G)是指满足无圈着色所用的最少颜色数。无圈着色最早由Grünbaum[24]提出. Alon, McDiarmid和 Reed在[6]中研究了Kr图（不包含K2,r+1子图）的无圈着色指数，目前最好的结果是Xa(G)＜1+△(1+√2r+4)。 本研究分为五个部分：第一章对图论起源及其发展历程的介绍，重点介绍了图论各个发展阶段的一些代表性问题。第二章对用到的定义概念进行介绍。总结了一些目前国内外在线性荫度以及无圈着色方面的研究现状。第三章探究了LLL以及熵压缩方法的发展，并介绍了熵压缩方法在着色领域的应用，对Local Cut Lemma以及其应用进行介绍，主要包括一般图的非重复线性着色问题，最大度为△的无圈边着色问题等。第四章探究了LCL在d-正则有向图线性荫度求解中的应用和LCL在Kr，图无圈着色指数求解中的应用。第五章则是对本文的总结。