论文部分内容阅读
本文分两部分,第一部分(前四章)主要研究-Nim类型的博弈.第二部分(五六章)研究图的在线列表染色.Nim博弈是最经典的组合博弈.有关组合博弈的论文研究了大量的Nim博弈的变形(Nim类型博弈),比如1910年,Moore提出并解决的Nimk博弈,1971年,Schwartz解决的带上界Nim博弈以及2004年Ablert和Nowakowski提出并解决的贪婪的Nim博弈.论文第一章介绍这几种Nim类型博弈的规则和一些必胜策略.在第二章和第三章中我们提出了两种Nim类型博弈:带上界的贪婪的Nim博弈和贪婪的Nimk博弈.带上界的贪婪Nim博弈是带上界的Nim博弈的综合.贪婪的Nimk博弈是贪婪的Nim博弈和Nimk博弈的综合.我们知道,博弈中任何细微的规则变化都可能带来博弈策略上根本的变化.带上界的贪婪Nim博弈和贪婪的Nimk博弈都和原有的博弈有很大的不同.原有的博弈策略不再适用.在第二章和第三章中,我们分别给出了上述两种Nim类型博弈的完整解和必胜方的必胜策略.第四章讨论带虚手的Nim博弈.该博弈由Chan和Low于2014年引入,他们在文献[12]给出了该博弈在一些特殊情形下的解我们推广了[12]中若干引理,给出了该博弈在另外一些特殊情形下的解.求其完整解仍然是一个未解决的问题.第五章主要介绍了列表染色和在线列表染色的一些背景知识以及[5]中的一些结论.第六章研究一些特殊图类的可选性和在线可选性.假设G是一个简单图,f:V(G)→ N是一个映射.给定一个正整数m,假设f(m)是图G(?)Km的f的一个延拓,对于Km的每一个点v,f(m)(v)= |V(G)|.我们分别用mc((G,f)和mp(G,f)表示最小的m使得G(?)Km不是f(m)-可选以及不是f(m)-在线可选的,在这一章中我们还给出了当G是完全图的时候计算mc(G,f)和mp(G,f)的公式.这一结果推广了[5]中一个关于列表染色和在线列表染色的结果,非常令人惊奇的是,mc(G,f)和mp(G,f)的值与一种广义的Dyck路有关系.