资源描述:
《若干图类的关联着色与关联对策着色的分析》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、论文题目:若干图类的尖联着色与尖联对策着色的研究作者姓名:刘大琨专业名称:应用数学指导教师:王淑栋入学时间:2006年9月研究方向:系统模型与算法职称:副教授论文提交日期:2009年5月论文答辩日期:2009年6月授予学位日期:THERESEARCHONINCIDENCECOLORINGANDINCIDENCEGAMECOLORINGOFSAVERALTYPESOFGRAPHSADissertationsubmittedinfulfillmentoftherequirementsofthedegr
2、eeofMASTEROFSCIENCEfromShanDongUniversityofScienceandTechnologyLiuDakunSupervisor:AssociateProfessorWangShudongCollegeofInformationScienceandEngineeringMay2009本人呈交给山东科技大学的这篇硕士学位论文,除了所列参考文献和世所公认的文献外,全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名:日期:AFFI
3、RMATIONdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofScienceinShandongUniversityofScienceandTechnology,iswhollymyownworkunlessreferencedofacknowledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheraca
4、demicinstitute.Signature:Date:本文从图的结构性质岀发,利用归纳法和反证法研究了Johnson图以及若干广义Petersen图的关联着色,得到:Johnson图的关联色数x(丿伽))=m(r-加+1);当n=0(mod4),R为奇数时,广义Petersen图P(“0的关联色数询)=4;当k=2,4时,广义Petersen图畑的关联色数%(P(询)=5。设G是一个有限图,两个人Alice和Bob轮流对图G的关联进行着色,使得相邻的关联着色不同。Alice首先开始着色,若无
5、法再进行下去时着色结束。若着色结束后图G的每个关联都正常着色,则Alice获胜,否则Bob获胜。Alice获胜所用的最少颜色数称为图G的关联对策色数,记为/JG)。本文将圈的关联对策着色转化为关联图的对策着色,得到了斤阶圈的关联对策色数HC)=5。关键词:关联色数;关联对^色数;Johnson图;广义Petersen图ABSTRACTInthisdissertation,fromtheconstructionpointofview,usingthemethodsofinductionandcont
6、radiction,weobtaintheseconclusions:theincideneechromaticnumberofJohnsongraphsX(J(捕)=m{t-m+1);Whenn=0(mod4)zkisanoddnumber,incideneechromaticnumberofgeneralizedPetersengraphsis4;Whenn=0(mod4),k-2,4;incidencechromaticnumberofgeneralizedPetersengraphsis5
7、.Letgbeafinitegraph・Twoplayers,AliceandBob,coloralternatelytheincidencesofgraphinsuchawaythattheneighborlyincidencesreceivedistinctcolors.Thegameendswhenthisisnotpossibleanymore.Alicewinsifeveryincideneeiscoloredattheendofthegame,otherwiseBobwins.Thei
8、ncideneegamechromaticnumberofGistheleastorderofcolorsetwithwhichAlicecolorsG.Inthisdissertation,Weconverttheincideneegamecoloringoncyclestothegamecoloringontheincideneegraphsofcycles,andobtaintheincideneegamechromaticnumberofcycleswithorderni&