圖的Chip-firing Game問題的研究.pdf

1、本文主要討論這樣一種游戲Chip-firing Games：先給出-個(gè)圖G=(V， E)，G的每個(gè)點(diǎn)上都包含若干個(gè)碎片，當(dāng)-個(gè)點(diǎn)v上的碎片數(shù)c(v)大于等于v的度數(shù)d(v)時(shí)，就可以對(duì)該點(diǎn)進(jìn)行崩塌，在v點(diǎn)-次崩塌之后，頂點(diǎn)v上的碎片數(shù)減少d(v)個(gè)，而v的任-鄰點(diǎn)u與v連有幾條邊，u的碎片數(shù)就增加幾個(gè)，G的其它頂點(diǎn)碎片數(shù)不變.游戲按此規(guī)則進(jìn)行，每-個(gè)狀態(tài)的總碎片數(shù)保持不變.如果某-時(shí)刻，G上的任意-點(diǎn)w都有c(w)

2、都不具備崩塌條件，就稱這個(gè)游戲是有限的；反之，若任何時(shí)刻G中都存在可以崩塌的點(diǎn)，那么游戲就是無(wú)限的.在A.Bjorner，L.Lovasz和P.W.Shor于1991年發(fā)表的文章”Chip-firing Games on Graphs”中，給出了這樣的結(jié)果：在任意有m條邊，n個(gè)頂點(diǎn)的圖形G上，總碎片數(shù)N如果小于m，不管碎片如何分布，G上的Chip-firing Games總為有限；如果總碎片數(shù)N大于2m-n，那么G上的Chip-firi

3、ng Games都為無(wú)限；而如果N取區(qū)間[m，2m-N]上的任-整數(shù)，則結(jié)果不確定。 本篇文章以上面的結(jié)果為基礎(chǔ)做了一些工作，文章分為三章： 在第-章中，我們對(duì)Chip-firing Games的起源，意義，發(fā)展的情況，在這-領(lǐng)域的主要工作做-些介紹，并闡述本文的主要工作； 在第二章中，對(duì)于任意的圖G，我們利用圖的鄰接矩陣和-些已有的結(jié)論，來(lái)給出-個(gè)算法以判斷在G的碎片總數(shù)N的取值范圍為[m，2m-n]的情況下，

4、從哪些初始狀態(tài)出發(fā)的Ghip-firing Games有限，而從哪此初始狀態(tài)出發(fā)的Chip-firing Games無(wú)限； 在第三章中，我們針對(duì)完全圖進(jìn)行研究.首先討論在某些特殊情況下，完全圖上的Chip-firing Games的性頃；其次證明在N的取值范圍為[m，2m-n]的情況下，對(duì)于完全圖上的任意的Chip-firing Games，都可以通過(guò)一系列的崩塌到達(dá)-類特殊的狀態(tài)，并給出-個(gè)充要條件來(lái)最終判斷這個(gè)Chip-fi