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

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

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

3、環(huán)態(tài)的集合，則結(jié)論可表示為: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處沙粒數(shù)為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)構(gòu)成的集合.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處