圖的極小循環(huán)態(tài)

孟二霞,侯耀平,方愛香

(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 中國 長沙 410081)

早在1987年,美國的3位科學(xué)家Bak,Tang以及Wiesenfeld 在文獻(xiàn)[1]中就提出了自組織臨界性理論并介紹了一種BTW的自動機(jī)模型-沙堆模型.隨后,在文獻(xiàn)[2]中Dhar推廣了這種自動機(jī)模型,提出了Abelian沙堆模型并給出了用來判斷循環(huán)態(tài)的燃燒算法. Abelian沙堆模型被提出后, 許多物理學(xué)家和數(shù)學(xué)家從不同方面對這個(gè)模型進(jìn)行了研究,侯耀平等在文獻(xiàn)[3～4]中用矩陣和數(shù)論的方法確定了一些圖的沙堆群結(jié)構(gòu),作為沙堆群的主要構(gòu)成元素—循環(huán)態(tài)以及極小循環(huán)態(tài)有很好的性質(zhì)[5].文獻(xiàn)[6]給出了圖的任一極小循環(huán)態(tài)與圖G的有唯一源點(diǎn)q的無圈定向之間的一一對應(yīng)關(guān)系. 與圖上沙堆模型的循環(huán)態(tài)相關(guān)的一個(gè)問題是G-parking函數(shù), 文獻(xiàn)[7]給出了極大G-parking函數(shù)集的性質(zhì). 本文運(yùn)用無圈定向與圖的極小循環(huán)態(tài)的對應(yīng)關(guān)系得到了循環(huán)態(tài)與極小循環(huán)態(tài)之間的關(guān)系以及某些圖運(yùn)算的極小循環(huán)態(tài)的性質(zhì).

設(shè)G=(V,q,E)是一個(gè)簡單連通圖,其中V=(q,v1,v2,…,vn),q是G的源點(diǎn),E(G)是G的邊集. 對有向圖,用d+(vi)表示以點(diǎn)vi為起點(diǎn)的有向邊的數(shù)目,稱作點(diǎn)vi的出度; 用d-(vi)表示以點(diǎn)vi為終點(diǎn)的有向邊的數(shù)目,稱作點(diǎn)vi的入度,d(vi)表示點(diǎn)vi在圖G中的度(有時(shí)候?yàn)楸苊饣煜胐G(vi)表示點(diǎn)vi在圖G中的度). 對于有向圖中的任一點(diǎn)vi, 都有d+(vi)+d-(vi)=d(vi)成立. 非負(fù)整數(shù)向量u=(u(v1),u(v2),…,u(vn))稱為圖G的一個(gè)態(tài),其中u(vi)表示在點(diǎn)vi處的沙粒數(shù),若點(diǎn)vi滿足u(vi)

在穩(wěn)定態(tài)中,只有一部分u在某些頂點(diǎn)上增加一些沙粒數(shù)后經(jīng)過一系列的倒塌又回到穩(wěn)定態(tài)u,這部分的特殊穩(wěn)定態(tài)稱為循環(huán)態(tài). 循環(huán)態(tài)在沙堆模型中具有重要的作用和很好的代數(shù)性質(zhì), 他們構(gòu)成了一個(gè)有限交換群,也稱為圖的沙堆群. 對圖G的所有循環(huán)態(tài)組成的集合記為R(G). Dhar在文獻(xiàn)[2]中給出了判定一個(gè)穩(wěn)定態(tài)u是否為循環(huán)態(tài)的有效方法, 稱為燃燒算法.

燃燒算法[3]任取圖G的一個(gè)穩(wěn)定態(tài)u,在頂點(diǎn)q的每個(gè)鄰點(diǎn)上都加1個(gè)沙粒,按照上面的倒塌規(guī)則,除點(diǎn)q外,若每個(gè)頂點(diǎn)都恰好倒塌一次最后又回到態(tài)u, 則u是圖G的循環(huán)態(tài).

對任一循環(huán)態(tài),我們可以根據(jù)燃燒算法得到的倒塌序列來定義燃燒圖.

定義1設(shè)u是圖G=(V,q,E)的一個(gè)循環(huán)態(tài),f=(v1,v2,…,vn)是圖G關(guān)于循環(huán)態(tài)u的一個(gè)倒塌序列. 定義一個(gè)燃燒圖Gf=(V,q,E′),其中E′={(vi,vj)|{vi,vj} ∈E∧i

另外極小循環(huán)態(tài)是一種特殊的循環(huán)態(tài), 對圖G的任一個(gè)循環(huán)態(tài)u, 稱u是圖G極小循環(huán)態(tài)當(dāng)且僅當(dāng)將循環(huán)態(tài)u的任意非零點(diǎn)處vi的沙粒數(shù)減少1(即u(vi)-1)時(shí),u不是循環(huán)態(tài). 用Rmin(G)表示圖G的所有極小循環(huán)態(tài)集. 作為特殊的循環(huán)態(tài),每個(gè)極小循環(huán)態(tài)的燃燒圖有且只有1個(gè).

下面是極小循環(huán)態(tài)與圖的有唯一源點(diǎn)q的無圈定向間的一一對應(yīng)關(guān)系.

引理1[3]一個(gè)態(tài)u是圖G的一個(gè)極小循環(huán)態(tài)當(dāng)且僅當(dāng)存在圖G的有唯一源點(diǎn)q的無圈定向與之對應(yīng), 使得對?v∈V(G),有u(v)=d+(v).

1 循環(huán)態(tài)是極小循環(huán)態(tài)的并

本節(jié)給出循環(huán)態(tài)與極小循環(huán)態(tài)之間的關(guān)系.

將圖G中的頂點(diǎn)標(biāo)號為(q,1,2,…,n).對于任一循環(huán)態(tài)u, 根據(jù)燃燒算法可知:將與q相鄰的每個(gè)頂點(diǎn)都增加一個(gè)沙粒,則每個(gè)頂點(diǎn)恰好倒塌一次最終回到u.易知循環(huán)態(tài)u的倒塌序列不唯一, 于是其燃燒圖也不唯一. 但若按照下面的規(guī)則進(jìn)行倒塌: 當(dāng)有兩個(gè)頂點(diǎn)同時(shí)倒塌, 則選擇標(biāo)號較小的頂點(diǎn)先倒塌,即可得到唯一的倒塌序列v1,v2,…,vn,從而得到唯一的燃燒圖. 按照倒塌的先后定義偏序關(guān)系：v1

根據(jù)上述偏序關(guān)系確定圖G的有唯一源點(diǎn)q的無圈定向: 與q關(guān)聯(lián)的邊都是背離q的方向,給定一頂點(diǎn)vj, 使得d+(vj)=u(vj),當(dāng)u(vj)

下面證明按照上述方法得到的有向圖O是有唯一源點(diǎn)q的無圈定向圖.

先證明無圈: 對于包含q在內(nèi)的子圖,若含圈,則點(diǎn)q必在某個(gè)圈中,也有一條邊指向點(diǎn)q,與前面所定義的有向圖O矛盾.故點(diǎn)q不在任何圈中.又由u(vj)=d+(vj)且vj是盡可能指向標(biāo)號較大的頂點(diǎn), 若存在vi

再證該圖的源點(diǎn)q是唯一的. 假設(shè)還存在另一源點(diǎn)v0, 與之關(guān)聯(lián)的邊也都是背離v0的，故v0在倒塌時(shí)有:u(v0)+d-(v0)≥d(v0), 而d-(v0)=0, 故u(v0)≥d(v0)，與u是循環(huán)態(tài)矛盾. 假設(shè)不成立. 故圖的無圈定向中源點(diǎn)q是唯一的.

根據(jù)上面的定理, 容易得到如下兩個(gè)推論.

推論1設(shè)G=(V,q,E)是一個(gè)圖,則G上的任意循環(huán)態(tài)至多是|V(G)|-1個(gè)極小循環(huán)態(tài)的并.

證根據(jù)定理1中尋找比循環(huán)態(tài)u小的極小循環(huán)態(tài)可知: 先確定1個(gè)固定的點(diǎn)vj, 使得d+(vj)=c(vj)=u(vj), 當(dāng)vj取遍圖G的所有頂點(diǎn)后, 至多找到|V(G)|-1個(gè)極小循環(huán)態(tài),它們的并即為循環(huán)態(tài)u.

推論2圖G=(V,q,E)中,v(≠q)是圖G的1個(gè)頂點(diǎn). 若整數(shù)k滿足0≤k≤d(v)-1, 則存在極小循環(huán)態(tài)c∈Rmin(G),使得c(v)=k.

證任取圖G的1個(gè)極小循環(huán)態(tài)c1, 在燃燒算法下,c1的倒塌序列為(vi1,vi2,…,vin), 再對圖G的頂點(diǎn)重新標(biāo)號,vij對應(yīng)的標(biāo)號為j, 則頂點(diǎn)的新序列為(1,2,…,n), 不妨設(shè)點(diǎn)v的標(biāo)號為i,對與i關(guān)聯(lián)的邊定向如下: 點(diǎn)i指向標(biāo)號盡可能大的頂點(diǎn)且滿足d+(i)=k, 對其余的與點(diǎn)i關(guān)聯(lián)的邊都指向i. 與q關(guān)聯(lián)的邊都背離q, 其余的邊都按標(biāo)號從小到大的方向. 由定理1的證明可知，得到的有向圖是有唯一源點(diǎn)q的無圈定向圖. 再根據(jù)圖的極小循環(huán)態(tài)與無圈定向之間的關(guān)系可知，存在c∈Rmin(G), 使得c(v)=k=d+(v),對其余的點(diǎn)v′, 有d+(v′)=c(v′).

2 圖運(yùn)算的極小循環(huán)態(tài)

極小循環(huán)態(tài)作為沙堆群中的特殊組成元素, 文獻(xiàn)[6]已經(jīng)給出了一些極小循環(huán)態(tài)的性質(zhì)， 并且得到了一些特殊圖的極小循環(huán)態(tài).對于一般圖的極小循環(huán)態(tài)，可以經(jīng)過特殊圖的運(yùn)算得到,其極小循環(huán)態(tài)也可以由下面的定理得到.

先考慮當(dāng)c(s)=d(s)-1時(shí),圖G的極小循環(huán)態(tài)可以由圖G*e的極小循環(huán)態(tài)c′來得到的.定義圖G上的態(tài)c:

下面考慮將圖G的任意1條邊分割后所得圖與原圖的極小循環(huán)態(tài)之間的聯(lián)系. 設(shè)邊e={s,t}是圖G的任意一條邊, 將邊e分割成2條邊{s,w},{w,t}得到新圖H,c是圖G的任意一個(gè)極小循環(huán)態(tài).則下面的結(jié)論成立.

定理3Rmin(H)=R1∪R2， 其中R1中的元素是圖H的一部分極小循環(huán)態(tài)c′,滿足

R2中的元素是圖H的另一部分極小循環(huán)態(tài)c′,滿足

所以c′是圖H的極小循環(huán)態(tài). 這些循環(huán)態(tài)的集合記為R2.

對圖G的任意一條邊e={s，t}, 分割此條邊后圖G的有唯一源點(diǎn)q的無圈定向至多有3種情況,所以至多存在3個(gè)極小循環(huán)態(tài)與之對應(yīng). 前兩種如上面兩種情形, 另外還可以把邊{s,w}定向?yàn)?w,s), 把邊{w,t}定義為(t,w),當(dāng)c(t)=d(t)-1時(shí), 邊{w,t}的方向必須規(guī)定為(w,t),否則點(diǎn)t為源點(diǎn),極小循環(huán)態(tài)如R1中的形式所示;當(dāng)c(t)

(a)

所得到的極小循環(huán)態(tài)與(a)中的相同. 綜上所述:對圖G中與邊{s,t}方向相反的情形若是含有圈,則沒有極小循環(huán)態(tài)存在; 若得到的是有唯一源點(diǎn)q的無圈定向, 則其對應(yīng)的極小循環(huán)態(tài)可以由前面的情況得到.于是有Rmin(H)=R1∪R2.

參考文獻(xiàn)：

[1] BAK P, TANG C, WIESENFELD K. Self-organised criticality:an explanation of 1/fnoise[J]. Phys Rev Lett, 1987,59(4):381-384.

[2] DHAR D. Self-organised critical state of the sandpile automaton models[J]. Phys Rev Lett,1990,64(14):1613-1616.

[3] SHEN J, HOU Y. On the sandpile group of 3×ntwisted bracelets[J]. Linear Algebra Appl, 2008,429(16):1894-1904.

[5] BORGNE Y L, ROSSIN D. On the identity of the sandpile group[J]. Discrete Math, 2002,256(3):775-790.

[6] SCHULZ M. Minimal recurrent configurations of chip firing games and directed acyclic graphs[J].DMTCS Proc, 2010,5(16):111-124.

[7] CHEBIKIN D, PYLYAVSKYY P. A family of bijections betweenG-parking functions and spanning trees[J].Comb Theory Ser, 2005,110(1):31-41.

[8] CORI R, DARTOIS A, ROSSIN D. Avalanches polynomials of some family of graphs[J]. Math Comb Sci, 2004,1(13): 81-94.

[9] LOPEZ C M. Chip firing and the tutte polynomial[J].Annals of Comb, 1997,35(1):253-259.

[10] BIGGS N L. Chip-Firing and the critical group of a graph[J]. Algebr Comb, 1999,9(1):25-45.

[11] CHEN S, YE S K. Critical groups for homeomorphism classes of graphs[J], Discrete Math, 2009,309(1):255-258.

[12] CORI R, ROSSIN D. On the sandpile group of dual graphs[J]. Eur Comb, 2000,21(5):447-459.

[13] LEVINE L. The sandpile group of a tree[J]. Eur Comb, 2009,30(4):1026-1035.