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

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

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

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

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