圖上沙堆模型的循環(huán)態(tài).pdf

1、圖上的沙堆模型是研究自組織臨界現象的一個很重要的模型，沙堆模型是在代數與圖論的基礎上進行研究的，具有廣泛的應用.圖上沙堆模型中的循環(huán)態(tài)構成了一個有限交換群，也稱為沙堆群.沙堆群有其豐富的數學結構和代數結構.沙堆群中的重要組成元素-循環(huán)態(tài)與極小循環(huán)態(tài)有一些很完美的性質.根據循環(huán)態(tài)與parking函數的關系，B.Benson和P.Tetali已經給出了任意非極大G-parking函數g是在其控制下的極大Parking函數f的交.本文推廣了此

2、文獻中的結論:得到了非極小循環(huán)態(tài)是若干個不大于它的極小循環(huán)態(tài)的并，且這樣的極小循環(huán)態(tài)個數至多為|V(G)|-1個;另外，根據圖的有唯一源點的無圈定向與極小循環(huán)態(tài)的一一對應關系[4]以及燃燒算法[8]，本文得到了一些圖運算的循環(huán)態(tài)與極小循環(huán)態(tài).具體得到如下結論:
　　 (1)任意圖的非極小循環(huán)態(tài)是若干個不大于它的極小循環(huán)態(tài)的并，且這樣的極小循環(huán)態(tài)個數至多為|V(G)|-1個.設u是圖G的任一個循環(huán)態(tài)用Rumin表示不大于u的極小循

3、環(huán)態(tài)的集合，則結論可表示為:u=(V)c∈RuminC
　　 (2)圖G的極小循環(huán)態(tài)可以用刪除與收縮一條與根點相鄰的邊e={q，s}后圖的極小循環(huán)態(tài)表示:Rmin(G)=Rsumin(G)URmin(G-e)，其中Rsmin(G)表示在點s處沙粒數為d(s)-1的圖G極小循環(huán)態(tài)的集合，Rmin(G-e)表示圖G-e的極小循環(huán)態(tài)集.
　　 (3)分割圖G的任一一條邊e={s，t}后得到新圖記為圖H，則圖H的極小循環(huán)態(tài)可以表

4、示為:Rmin（H）=R1UR2.其中R1是滿足c’(v)={1， v=w;c（v），其他.圖H的所有極小循環(huán)態(tài)構成的集合.R2是滿足{c(t)+1，v=t且c（t)＜d（t)-1;c'(v)=0， v=wc（v），其他.圖H的所有極小循環(huán)態(tài)的集合.c是圖G的任意一個極小循環(huán)態(tài).
　　 (4)圖G的循環(huán)態(tài)可以用刪除與收縮一條與根點相鄰的邊e={q，s}后圖的循環(huán)態(tài)表示為:R(G)=(R）1U R(G-e).其中（R）1是在點s處