图上二人对策着色和对策着色数.pdf

园南京师勉夫掌硕士学位论文图上二人对策着色和对策着色数����������索取号:密级�����作者:戚志如院系:数学与计算机科学学院指导教师:学科专业:孙志人副教授运筹学与控制论
作者签名:应垒作者签名:趣鸯:查学位论文独创性声明学位论文使用授权声明町。��堕:点�本人郑重声明:�⒓岢忠詔�笫怠⒋葱隆钡目蒲Ь�翊邮卵芯抗ぷ鳎��⒈韭畚氖俏腋鋈嗽诘际χ傅枷陆�械难芯抗ぷ骱腿〉玫难芯�成果.�⒈韭畚闹谐��耐猓��惺笛椤⑹�莺陀泄夭牧暇�钦媸档模��⒈韭畚闹谐��暮椭滦坏哪谌萃猓�话��渌�嘶蚱渌��挂�经发表或撰写过的研究成果.�⑵渌��径员狙芯克�龅墓毕拙�言诼畚闹凶髁松�鞑⒈硎�:本人完全了解南京师范大学有关保留、使用学位论文的规定,学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版;有权将学位论文用于非赢利目的的少量复制并允许论文进人学校图书馆被查阅;有权将学位论文的内容编人有关数据库进行检索;
卜�:��;磁阪卜�:��:摘要�路图,圈图及其补图的对策色数Ⅱ,我们得到了:对�茁稲和�兹�分别有自从��年日.�瓸�����诠赜诩扑慊�蒲е械耐悸圩ㄌ馓致刍嵘献隽恕肮赜�某些色策略的计算复杂性”的专题报告,基于图的正常着色概念,首先引入图的对策着色的概念,所谓图的对策着色,如同两人���和��对弈,选手���酝几�鐾嫉�正常顶点着色,而选手��蛏璺ㄈプ柚垢檬录�姆⑸��柰糋���是扎阶简单图,�且桓稣�某J���莟种颜色的集合,两个人在图�隙赞模�∈諥��和��惶嬉资郑�詈笸瓿啥赞闹炼嘁贫�癫剑�恳徊桨�ㄒ幻�∈痔粞∫桓錾形醋派ǖ�顶点��掖友丈ḿ痻中给它分配一种颜色△,使得。不同于已分配到�牧诘愕难�色,若�胶笸糋被正常着色,则选手���袷ぃ蝗粼诟猛嫉娜ú慷サ惚蛔派��按�成僵局,即对每一个尚未着色的顶点�蚗中的每一种颜色�,口都与一个着�ǖ�顶点相连,则��袷ぃ�糋的对策色数,记为����鞘寡∈諥�,.�谢袷げ呗缘�最小的����,���和���在此基础上介绍了一种新的对策染色�投圆呱��颍��是由色对策�⒄苟�矗�绻�匝∈諦�再附加条件,就提出了一种新的对策着色,邵图�亩圆呷旧á颍�飧鎏跫�窍拗蒲∈諦�,只能利用选手���岩�氲难丈��唬�除非他为保证图着色是正常的而不得不利用�械囊恢中卵丈ǎ�糋的对策色数Ⅱ是选手���谏ǘ圆呷旧á蛑杏幸桓龌袷げ呗缘淖钚〉膖,记为赡���ǘ圆呷旧玭简称为色对策Ⅱ.本文比较了两种色对策之间的差异,讨论了图�纳ǘ圆撷虻男灾剩��图的这种新的参数,利用顶点标号的方法,给出了���袷さ南嘤Σ呗裕�⒍约钢痔�Ⅱ,给出了轮图,扇匿和它的剂分图及其�还�图的对策色致Ⅱ,我们得到�鑞≥��蚨匀魏卫��咨韧糝和扎�阶轮图�シ��畁�.�畁:��
琢耻�腧圻腞乏’���籧‘�撸���海簄其��;或��襯为偶数’粥���既苛跷晕E际��跏㈥�援篡对��茁滞迹サ膔�谕肌���蚽�阶扇图�‘��直鹩�������������们给出了�淄耆�嫉亩圆呱��蛭猲�;完全二部图的对镱色数Ⅱ为�欢詎阶路�最后给出了�兹�的�甮����嫉亩圆呱���牟孪耄�杂趎≥�保�Α5�对扇图剖分图�:吐滞计史滞糋。分别有第五章讨论了�����忌系亩�硕圆咦派ā2⑶腋�隽薃�������迹�颐怯�关键诲:顶点着色;色对策;对策色数�宦滞迹还谕迹籑����图�
粥,�篡球小�撸������Ⅱ.��臿���������������������蜘������瑃���������甒��.��酵����.���『����,�����.����瑆�賤����,���,������.�������琽������甅�������Ⅱ����;���,���,�甃.��������.���琣�����琣������篜�������������瓻�����.�����,�畉.���甌���瑆�
琢咖叠嚣礤阱���嫁删�洞�硝帆胪��魉�������。��顁��一培帆玛�。�击�В����ィ瑆����鋓������籊���:���;��������,观����:����,�������������痵�������������;�����痵��,����琲,����Ⅱ��.������疭���篤�������;�����Ⅱ;������.��������,���.����珏����.��瑃��籄����,����;���.
绪论图论是离散数学的最活跃的分支之一,它是描述和处理离散系统的一个有力