平面图3着色及线性着色

《平面图3着色及线性着色》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆大学硕士学位论文中文摘要摘要图的着色问题来源于图论中最著名的四色猜想，它是图论中的一个重要分支。图的着色理论不仅在离散数学与组合分析等数学理论中有应用，它在最优化、交通运输、通讯网络和计算机理论等方面也有着广泛的应用。生活中安排会议或考试的日程以避免冲突，以及安排化学药品的存储以避免相互反应等具体问题也都可以用图的着色理论来解决。基于图的着色理论有着重要的理论意义和实用意义，图的着色问题一直是图论研究中的热点问题。本文主要研究了平面图的3着色与线性着色。它们都是针对图中的顶点进行着色的，其中线性着色以正常顶点着色为基础，3着色即只

2、用了3种颜色的正常顶点着色。主要内容可分为四部分：第一部分(第一章)主要介绍了图论中着色问题的历史背景，以及本文的研究目的与主要内容。第二部分(第二章)介绍了图的着色中的一些基本概念，重点介绍了正常顶点着色和线性着色的概念，并对两种着色的研究现状进行了综述。第三部分(文章的三、四章)是本论文的核心部分。在这～部分中，探讨了平面图的3着色和线性着色问题。第三章首先通过分析全由3度顶点构成的偶圈的结构，发现运用着色技巧可以实现着色延拓，给出了一个引理来说明最小反例图的结构；然后通过对欧拉公式作适当变形，巧妙设计权值分配规则，给出了平面图3

3、可着色的3个充分条件。第四章中通过分析平面图的结构，结合线性着色的特点，运用已知引理在一定程度上缩小了平面图线性着色色数的上界。第四部分(第五章)总结了本文研究所得到的结论，指出了本文的创新之处，并对本文后续研究工作作了展望。关键词：平面图，3着色，3可着色，线性着色，线性色数ABSTRACTThegraphcoloringproblemisderivedfromthefamous“FourColorConjecture”．Itisanimportantbranchofgraphtheory．Thegraphcoloringtheor

4、yisappliedtonotonlymathematicaltheory,suchaSdiscretemathematicsandcombinatorialanalysis，butalsomanyotherfields，suchasoptimization，trafficandtransportation，communicationnetwork，computertheoryandSOOil．ItcallhelpUStosolvetheproblemofarrangingmeetingorexalTlschedule．Itcanal

5、sobeusedtosolvetheproblemofchemicalsstorage．Becauseofthegraphcoloringtheoryistheoreticallyandpracticallyimportantinmanyfields，itisalwaysoneofthehottopicsofgraphtheory．Inthispaper,wemainlystudythe3-coloringandlinearcoloringofplanargraphs．Theyareallvertexcoloring．Thelinea

6、rcoloringisbasedonthepropervertexcoloring．Andthe3-coloringmeansapropervertexcoloringwitllthreecolors．Themaincontentsofthispapercallbedividedintofourparts．Thefirstpart(Chapter1)mainlyintroducesthehistoricalbackgroundofthegraphcoloringproblem，thestudypurposeandthemaincont

7、entsofthispaper．Thesecondpart(Chapter2)introducestherelatedbasicconcepts，especiallythepropervertexcoloringandthelinearcoloring．Besides，thispartsummarizesthecurrentresearchonthe3-coloringandthelinearcoloringofgraphs．Thethirdpart(Chapter3andChapter4)isthecoreofthispaper．T

8、hemainresearchfindingsareincludedinthispart．Wemainlyexplorethe3-coloringandthelinearcoloringofplanargraphsinth