圖上二人對策著色和對策著色數(shù).pdf

1、自從1991年H.L.Bodlaender在關(guān)于計算機(jī)科學(xué)中的圖論專題討論會上做了“關(guān)于某些色策略的計算復(fù)雜性”的專題報告，基于圖的正常著色概念，首先引入圖的對策著色的概念.所謂圖的對策著色，如同兩人(Alice和Bob)對弈，選手Alice試圖給出圖的正常頂點著色，而選手Bob則設(shè)法去阻止該事件的發(fā)生.設(shè)圖G=(V,E)是n階簡單圖，t是一個正的常數(shù)，X是t種顏色的集合，兩個人在圖G上對弈，選手Alice和Bob交替易手，最后完成對弈

2、至多移動n步，每一步包括一名選手挑選一個尚未著色的頂點v，且從顏色集X中給它分配一種顏色α，使得α不同于已分配到v的鄰點的顏色，若n步后圖G被正常著色，則選手Alice獲勝；若在該圖的全部頂點被著色之前達(dá)成僵局，即對每一個尚未著色的頂點v和X中的每一種顏色α，v都與一個著α色的頂點相連，則Bob獲勝.圖G的對策色數(shù)，記為Xg(G)，是使選手Alice有獲勝策略的最小的t. Chen，Schelp和Shreve在此基礎(chǔ)上介紹了一種

3、新的對策染色Ⅱ和對策色數(shù)Ⅱ，它是由色對策Ⅰ發(fā)展而來.如果對選手Bob再附加條件，就提出了一種新的對策著色，即圖G的對策染色Ⅱ，這個條件是限制選手Bob，只能利用選手Alice已引入的顏色之一，除非他為保證圖著色是正常的而不得不利用X中的一種新顏色.圖G的對策色數(shù)Ⅱ是選手Alice在色對策染色Ⅱ中有一個獲勝策略的最小的t，記為X★a(G).色對策染色Ⅱ簡稱為色對策Ⅱ.本文比較了兩種色對策之間的差異，討論了圖G的色對策Ⅱ的性質(zhì)，對圖的這種新

4、的參數(shù)，利用頂點標(biāo)號的方法，給出了Alice獲勝的相應(yīng)策略，并對幾種特殊的圖進(jìn)行了討論. 本文前兩章介紹了一些基本概念以及后面章節(jié)中要用到的基本引理.第三章給出了路圖，圈圖及其補(bǔ)圖的對策色數(shù)Ⅱ，我們得到了：對n階路Pn和n階圈Cn分別有X★g(P)={2,n≤53,n≥6x★g(Cn)=={2,n=43,n≠4第四章主要討論了與圈有關(guān)圖的對策色數(shù)Ⅱ，給出了輪圖，扇圖和它的剖分圖及其r-冠圖的對策色數(shù)Ⅱ，我們得到：設(shè)n≥3，則對任

5、何n+1階扇圖Fn和n+1階輪圖Wn分別有對扇圖剖分圖Qn和輪圖剖分圖Gn分別有x★g(Qn)=3；x★g(Gn)=3；對n+1階輪圖Wn的r-冠圖Ir(Wn)和n+l階扇圖R的r-冠圖Ir(R)分別有第五章討論了Mycielski圖上的二人對策著色，并且給出了Alice獲勝的相應(yīng)策略.我們給出了n階完全圖的對策色數(shù)Ⅱ為n+1；完全二部圖的對策色數(shù)Ⅱ為3；對n階路Pn的Mycielski圖，我們有 最后給出了n階圈Cn的Myci