资源描述：
《若干图类的关联着色与关联对策着色的分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
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&
