2,443
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： + 第5行：
第6行： − + + + 第21行：
第24行： − + − + + + + + + + + + + 第35行：
第47行： − + + + − ==Definition (rectangular grids)定义（矩形网格）== − The sandpile model is a [[cellular automaton]] originally defined on a <math>N\times M</math> rectangular grid (''checkerboard'') <math>\Gamma\subset\mathbb{Z}^2</math> of the [[Square lattice|standard square lattice]] <math>\mathbb{Z}^2</math>. − To each vertex (''side'', ''field'') <math>(x,y)\in\Gamma</math> of the grid, we associate a value (''grains of sand'', ''slope'', ''particles'') <math>z_0(x,y)\in\{0,1,2,3\}</math>, with <math>z_0\in\{0,1,2,3\}^\Gamma</math> referred to as the (initial) configuration of the sandpile. − The dynamics of the automaton at iteration <math>i\in\mathbb{N}</math> are then defined as follows: − − # Choose a random vertex <math>(x_i,y_i)\in\Gamma</math> according to some probability distribution (usually uniform). − # Add one grain of sand to this vertex while letting the grain numbers for all other vertices unchanged, i.e. set<br /><math>z_i(x_i,y_i)=z_{i-1}(x_i,y_i)+1</math> and<br /><math>z_i(x,y)=z_{i-1}(x,y)</math> for all <math>(x,y)\neq(x_i,y_i)</math>. − # If all vertices are ''stable'', i.e. <math>z_i(x,y)<4</math> for all <math>(x,y)\in\Gamma</math>, also the configuration <math>z_i</math> is said to be stable. In this case, continue with the next iteration. − # If at least one vertex is ''unstable'', i.e. <math>z_i(x_u,y_u)\geq 4</math> for some <math>(x_u,y_u)\in\Gamma</math>, the whole configuration <math>z_i</math> is said to be unstable. In this case, choose any unstable vertex <math>(x_u,y_u)\in\Gamma</math> at random. ''Topple'' this vertex by reducing its grain number by four and by increasing the grain numbers of each of its (at maximum four) direct neighbors by one, i.e. set<br /><math>z_i(x_u,y_u) \rightarrow z_i(x_u,y_u) - 4,</math>, and<br /><math>z_i( x_u \pm 1, y_u \pm 1) \rightarrow z_i( x_u \pm 1, y_u\pm 1) + 1</math> if <math>( x_u \pm 1, y_u\pm 1)\in\Gamma</math>.<br />If a vertex at the boundary of the domain topples, this results in a net loss of grains (two grains at the corner of the grid, one grain otherwise). − # Due to the redistribution of grains, the toppling of one vertex can render other vertices unstable. Thus, repeat the toppling procedure until all vertices of <math>z_i</math> eventually become stable and continue with the next iteration. 第63行：
第67行： − + − The toppling of several vertices during one iteration is referred to as an ''avalanche''. Every avalanche is guaranteed to eventually stop, i.e. after a finite number of topplings some stable configuration is reached such that the automaton is well defined. Moreover, although there will often be many possible choices for the order in which to topple vertices, the final stable configuration does not depend on the chosen order; this is one sense in which the sandpile is [[Abelian group|''abelian'']]. Similarly, the number of times each vertex topples during each iteration is also independent of the choice of toppling order. − 在一次迭代中多个顶点的崩塌被称为雪崩。每一次雪崩最终都会停止，也就是说，经过有限数量的顶点崩塌，会达到某种稳定的配置，这样自动机就得到了很好的定义。此外，尽管顶点崩塌的顺序常常有许多可能的选择，但最终的稳定状态并不依赖于所选择的顺序; 这是沙堆模型具有的可交换性质。类似地，在每次迭代过程中，每个顶点的崩塌次数也与崩塌顺序的选择是无关的。+ − + − To generalize the sandpile model from the rectangular grid of the standard square lattice to an arbitrary undirected finite multigraph <math>G=(V,E)</math>, a special vertex <math>s\in V</math> called the ''sink'' is specified that is not allowed to topple. A ''configuration'' (state) of the model is then a function <math>z:V\setminus\{s\}\rightarrow\mathbb{N}_0</math> counting the non-negative number of grains on each non-sink vertex. A non-sink vertex <math>v\in V\setminus\{s\}</math> with − :<math>z(v)\geq \deg(v)</math> − is unstable; it can be toppled, which sends one of its grains to each of its (non-sink) neighbors: − :<math>z(v) \to z(v) - \deg(v)</math> − :<math>z(u) \to z(u) + 1</math> for all <math>u\sim v</math>, <math>u\neq s</math>. − + − The cellular automaton then progresses as before, i.e. by adding, in each iteration, one particle to a randomly chosen non-sink vertex and toppling until all vertices are stable. − 元胞自动机像之前一样进行，即在每次迭代中，向随机选择的非沉没顶点添加一个沙粒，不断进行崩塌过程，直到所有顶点都稳定。+ 第89行：
第86行： − + − In the dynamics of the sandpile automaton defined above, some stable configurations (<math>0\leq z(v)<4</math> for all <math>v\in G\setminus\{s\}</math>) appear infinitely often, while others can only appear a finite number of times (if at all). The former are referred to as ''recurrent configurations'', while the latter are referred to as ''transient configurations''. The recurrent configurations thereby consist of all stable non-negative configurations which can be reached from any other stable configuration by repeatedly adding grains of sand to vertices and toppling. It is easy to see that the ''minimally stable configuration'' <math>z_m</math>, where every vertex carries <math>z_m(v)=deg(v)-1</math> grains of sand, is reachable from any other stable configuration (add <math>deg(v)-z(v)-1\geq 0</math> grains to every vertex). Thus, equivalently, the recurrent configurations are exactly those configurations which can be reached from the minimally stable configuration by only adding grains of sand and stabilizing. − + − Not every non-negative stable configuration is recurrent. For example, in every sandpile model on a graph consisting of at least two connected non-sink vertices, every stable configuration where both vertices carry zero grains of sand is non-recurrent. To prove this, first note that the addition of grains of sand can only increase the total number of grains carried by the two vertices together. To reach a configuration where both vertices carry zero particles from a configuration where this is not the case thus necessarily involves steps where at least one of the two vertices is toppled. Consider the last one of these steps. In this step, one of the two vertices has to topple last. Since toppling transfers a grain of sand to every neighboring vertex, this implies that the total number of grains carried by both vertices together cannot be lower than one, which concludes the proof. − + − + − Given an arbitrary but fixed ordering of the non-sink vertices, multiple toppling operations, which can e.g. occur during the stabilization of an unstable configuration, can be efficiently encoded by using the [[Laplacian matrix|graph Laplacian]] <math>\Delta=D-A</math>, where <math>D</math> is the [[degree matrix]] and <math>A</math> is the [[adjacency matrix]] of the graph. − 给定一个任意但固定的非沉没顶点的顺序，进行多个崩塌操作，可以通过使用[[拉普拉斯矩阵|图拉普拉斯]]<math>\Delta=D-A</math>高效地编码多个崩塌操作（例如，在不稳定构型的稳定过程中可能发生），其中<math>D</math>是图的[[度矩阵]]，<math>A</math>是图的[[邻接矩阵]]。+ 第117行：
第111行： − In this case, <math>\mathbf{x}</math> is referred to as the ''toppling'' or ''odometer function'' (of the stabilization of <math>z</math>). − + − Under the operation <math>*</math>, the set of recurrent configurations forms an [[abelian group]] isomorphic to the cokernel of the reduced graph Laplacian <math>\Delta'</math>, i.e. to <math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>, whereby <math>n</math> denotes the number of vertices (including the sink). More generally, the set of stable configurations (transient and recurrent) forms a [[commutative monoid]] under the operation <math>*</math>. The minimal [[Semigroup#Subsemigroups and ideals|ideal]] of this monoid is then isomorphic to the group of recurrent configurations. − + + − The group formed by the recurrent configurations, as well as the group <math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math> to which the former is isomorphic, is most commonly referred to as the ''sandpile group''. Other common names for the same group are ''critical group'', ''Jacobian group'' or (less often) ''Picard group''. Note, however, that some authors only denote the group formed by the recurrent configurations as the sandpile group, while reserving the name Jacobian group or critical group for the (isomorphic) group defined by <math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math> (or for related isomorphic definitions). Finally, some authors use the name Picard group to refer to the direct product of the sandpile group and <math>\mathbb{Z}</math>, which naturally appears in a cellular automaton closely related to the sandpile model, referred to as the chip firing or dollar game. − − 由循环构形形成的群，以及与之同构的群<math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>，通常称为'''<font color="#ff8000"> 沙堆群Sandpile group</font>'''。相同群的其它常用名称是“临界群”、“Jacobian群”或(不常见的)“Picard群”。然而，要注意的是，有些作者只把循环构型形成的组称为沙堆组，而为由<math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>（或相关的同构定义）定义的同构群保留Jacobian群或临界群的称呼。最后，一些作者使用Picard群来指代沙堆群和<math>\mathbb{Z}</math>的直接产物，后者出现在与沙堆模型密切相关的元胞自动机中，被称为'''<font color="#ff8000"> 碎片点火或美元游戏Chip firing or Dollar game</font>'''。 + − Given the isomorphisms stated above, the order of the sandpile group is the determinant of <math>\Delta'</math>, which by the [[Kirchhoff's theorem|matrix tree theorem]] is the number of spanning trees of the graph. 第140行：
第130行： − + − {{main|Self-organized criticality}} − The original interest behind the model stemmed from the fact that in simulations on lattices, it is attracted to its [[critical state]], at which point the correlation length of the system and the correlation time of the system go to infinity, without any fine tuning of a system parameter. This contrasts with earlier examples of critical phenomena, such as the [[phase transition]]s between solid and liquid, or liquid and gas, where the critical point can only be reached by precise tuning (e.g., of temperature). Hence, in the sandpile model we can say that the criticality is [[self-organization|self-organized]]. − 模型最初源于这样一个事实，即在晶格上的模拟中，它被吸引到了它的[[临界状态]]，此时系统的关联长度和关联时间趋于无穷大，不需要对系统参数进行任何微调。这与早期临界现象的例子形成了对比，例如固体和液体之间，或液体和气体之间的[[相变]]，其中临界点只能通过精确调节（例如，温度）来达到。因此，在沙堆模型中，我们可以说临界性是自组织的。 − Once the sandpile model reaches its critical state there is no correlation between the system's response to a [[wiktionary:perturbation|perturbation]] and the details of a perturbation. Generally this means that dropping another grain of sand onto the pile may cause nothing to happen, or it may cause the entire pile to collapse in a massive slide. The model also displays [[1/f noise|1/''ƒ'' noise]], a feature common to many complex systems in nature.+ − 一旦沙堆模型达到其临界状态，系统对扰动的响应和扰动细节之间就没有关联。一般来说，这意味着再往沙堆形成的斜坡上撒一粒沙子可能不会导致任何事情发生，或者可能导致整个沙堆形成的斜坡在大规模滑坡中崩塌。该模型还显示了[[1/f noise|1/''ƒ'' noise]]，这是自然界中许多复杂系统的共同特征。+ − ==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）[[1/f noise|1/''ƒ'' noise]]是什么 − This model only displays critical behaviour in two or more dimensions. The sandpile model can be expressed in 1D; however, instead of evolving to its critical state, the 1D sandpile model instead reaches a minimally stable state where every lattice site goes toward the critical slope. − For two dimensions, it has been hypothesized that the associated [[conformal field theory]] is consists of [[symplectic fermion]]s with a [[central charge]] ''c'' = −2.<ref>{{cite journal |author=S. Moghimi-Araghi |author2=M. A. Rajabpour |author3=S. Rouhani |title=Abelian Sandpile Model: a Conformal Field Theory Point of View |arxiv=cond-mat/0410434 |year=2004 |doi=10.1016/j.nuclphysb.2005.04.002 |volume=718|issue=3|journal=Nuclear Physics B|pages=362–370|bibcode = 2005NuPhB.718..362M |s2cid=16233977 }}</ref> − + − + − + 第174行：
第158行： − 芯片构型的稳定遵循一种“[[最小作用原理|最小作用原理]]”的形式：每个顶点在稳定过程中不超过必要的崩塌量。+ − +
无编辑摘要
此词条暂由水流心不竞初译，未经审校，带来阅读不便，请见谅。此词条由Zcy初步审校。
此词条暂由水流心不竞初译，未经审校，带来阅读不便，请见谅。此词条由Zcy初步审校。
'''<font color="#ff8000"> 阿贝尔沙堆模型Abelian sandpile model</font>'''，也被称为 Bak-Tang-Wiesenfeld 模型，是第一个发现的动力系统展现自组织临界性的例子。它是由 Per Bak，Chao Tang 和 Kurt Wiesenfeld 在1987年的一篇论文<ref name=Bak1987>
'''<font color="#ff8000"> 阿贝尔沙堆模型 Abelian sandpile model</font>'''，也被称为 Bak-Tang-Wiesenfeld 模型，是第一个发现的动力系统展现[[自组织临界性]]的例子。它是由 Per Bak，Chao Tang 和 Kurt Wiesenfeld 在1987年的一篇论文<ref name=Bak1987>
{{cite journal
{{cite journal
| author = Bak, P. |author2=Tang, C. |author3-link=Kurt Wiesenfeld |author3=Wiesenfeld, K.
| author = Bak, P. |author2=Tang, C. |author3-link=Kurt Wiesenfeld |author3=Wiesenfeld, K.
The model is a [[cellular automaton]]. In its original formulation, each site on a finite grid has an associated value that corresponds to the slope of the pile. This slope builds up as "grains of sand" (or "chips") are randomly placed onto the pile, until the slope exceeds a specific threshold value at which time that site collapses transferring sand into the adjacent sites, increasing their slope. Bak, Tang, and Wiesenfeld considered process of successive random placement of sand grains on the grid; each such placement of sand at a particular site may have no effect, or it may cause a cascading reaction that will affect many sites.
The model is a [[cellular automaton]]. In its original formulation, each site on a finite grid has an associated value that corresponds to the slope of the pile. This slope builds up as "grains of sand" (or "chips") are randomly placed onto the pile, until the slope exceeds a specific threshold value at which time that site collapses transferring sand into the adjacent sites, increasing their slope. Bak, Tang, and Wiesenfeld considered process of successive random placement of sand grains on the grid; each such placement of sand at a particular site may have no effect, or it may cause a cascading reaction that will affect many sites.
这个模型是一种'''<font color="#ff8000"> 细胞自动机模型Cellular automaton</font>'''。在最初的公式中，有限网格上的每个位置都有一个与沙堆的坡度相对应的关联值。当“沙粒”(或“碎片”)被随机放置在沙堆上时，放置位置的斜坡就会堆积起来，直到倾斜程度超过一个特定的阈值，这个位置倒塌，沙子会转移到邻近的位置，增加它们的斜坡。Bak, Tang,和Wiesenfeld考虑了在网格上连续随机放置沙粒的过程; 每次这样在特定位置放置沙粒有可能不会产生影响，也有可能会引起级联反应，影响到周围的其他位置。
这个模型是一种'''<font color="#ff8000"> [[元胞自动机]]模型 Cellular automaton</font>'''。在最初的公式中，有限网格上的每个位置都有一个与沙堆的坡度相对应的关联值。当“沙粒”(或“碎片”)被随机放置在沙堆上时，放置位置的斜坡就会堆积起来，直到倾斜程度超过一个特定的阈值，这个位置倒塌，沙子会转移到邻近的位置，增加它们的斜坡。Bak，Tang和 Wiesenfeld考虑了在网格上连续随机放置沙粒的过程; 每次这样在特定位置放置沙粒有可能不会产生影响，也有可能会引起[[级联反应]]，影响到周围的其他位置。
The model has since been studied on the infinite lattice, on other (non-square) lattices, and on arbitrary graphs (including directed multigraphs).<ref name=Hol2008>{{cite book
| author = Holroyd, A. |author2=Levine, L. |author3=Mészáros, K. |author4=Peres, Y. |author5=Propp, J. |author6=Wilson, B.
| year = 2008
| title = Chip-Firing and Rotor-Routing on Directed Graphs
| journal = In and Out of Equilibrium 2
| volume = 60
| pages = 331–364
| doi = 10.1007/978-3-7643-8786-0_17
| bibcode=1987PhRvL..59..381B
|arxiv=0801.3306|isbn=978-3-7643-8785-3 |s2cid=7313023 }}</ref> It is closely related to the [[Chip-firing game#Biggs's Variant|dollar game]], a variant of the [[chip-firing game]] introduced by Biggs.<ref>{{cite journal|last=Biggs|first=Norman L.|date=25 June 1997|title=Chip-Firing and the Critical Group of a Graph|url=ftp://ftp.math.ethz.ch/hg/EMIS/journals/JACO/Volume9_1/m6g7032786582625.fulltext.pdf|journal=Journal of Algebraic Combinatorics|pages=25–45|accessdate=10 May 2014}}</ref>
该模型已经在无限栅格、其他(非方形)栅格和任意图(包括有向多重图)上进行了研究。<ref name=Hol2008>{{cite book
该模型已经在无限栅格、其他(非方形)栅格和任意图(包括有向多重图)上进行了研究。<ref name=Hol2008>{{cite book
| doi = 10.1007/978-3-7643-8786-0_17
| doi = 10.1007/978-3-7643-8786-0_17
| bibcode=1987PhRvL..59..381B
| bibcode=1987PhRvL..59..381B
|arxiv=0801.3306|isbn=978-3-7643-8785-3 |s2cid=7313023 }}</ref>它与美元游戏密切相关，美元游戏是Biggs引入的一种chip-firing游戏的变体。<ref>{{cite journal|last=Biggs|first=Norman L.|date=25 June 1997|title=Chip-Firing and the Critical Group of a Graph|url=ftp://ftp.math.ethz.ch/hg/EMIS/journals/JACO/Volume9_1/m6g7032786582625.fulltext.pdf|journal=Journal of Algebraic Combinatorics|pages=25–45|accessdate=10 May 2014}}</ref>
|arxiv=0801.3306|isbn=978-3-7643-8785-3 |s2cid=7313023 }}</ref>它与美元博弈游戏密切相关，美元游戏是Biggs引入的一种chip-firing游戏的变体。<ref>{{cite journal|last=Biggs|first=Norman L.|date=25 June 1997|title=Chip-Firing and the Critical Group of a Graph|url=ftp://ftp.math.ethz.ch/hg/EMIS/journals/JACO/Volume9_1/m6g7032786582625.fulltext.pdf|journal=Journal of Algebraic Combinatorics|pages=25–45|accessdate=10 May 2014}}</ref>
==定义（矩形网格）==
沙堆模型是一个'''<font color="#ff8000">元胞自动机cellular automaton </font>'''，它最初定义在<math> N\times M </math>矩形网格(棋盘格)上，其顶点在标准的正方形格子<math> \mathbb{Z}^2 </math>上<math> \Gamma\subset\mathbb{Z}^2 </math>。
沙堆模型是一个'''<font color="#ff8000">元胞自动机cellular automaton </font>'''，它最初定义在<math> N\times M </math>矩形网格(棋盘格)上，其顶点在标准的正方形格子<math> \mathbb{Z}^2 </math>上<math> \Gamma\subset\mathbb{Z}^2 </math>。
对于栅格中的每个顶点<math> (x,y)\in\Gamma </math>，我们关联一个值(沙粒、坡度、颗粒) <math> z_0(x,y)\in\{0,1,2,3\} </math>，这样所有顶点的初始状态<math> z_0\in\{0,1,2,3\}^\Gamma </math>被称为沙堆的(初始)构型。
对于栅格中的每个顶点<math> (x,y)\in\Gamma </math>，我们关联一个值(沙粒、坡度、颗粒) <math> z_0(x,y)\in\{0,1,2,3\} </math>，这样所有顶点的初始状态<math> z_0\in\{0,1,2,3\}^\Gamma </math>被称为沙堆的(初始)构型。
自动机的动力学过程在第<math> i\in\mathbb{N} </math>次迭代时的定义如下:
自动机的动力学过程在第<math> i\in\mathbb{N} </math>次迭代时的定义如下:
#根据某种概率分布(通常为均匀分布)随机选择一个顶点。根据一些概率分布(通常是均匀的)选择一个随机顶点<math> (x_i,y_i)\in\Gamma </math>。
#根据某种概率分布(通常为均匀分布)随机选择一个顶点。根据一些概率分布(通常是均匀的)选择一个随机顶点<math> (x_i,y_i)\in\Gamma </math>。
#由于沙粒的重新分布，一个顶点的崩塌会使其他顶点不稳定。这样，重复崩塌的过程，直到<math>z_i</math>状态下的所有顶点最终稳定下来，继续下一轮迭代。
#由于沙粒的重新分布，一个顶点的崩塌会使其他顶点不稳定。这样，重复崩塌的过程，直到<math>z_i</math>状态下的所有顶点最终稳定下来，继续下一轮迭代。
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]） (two grains at the corner of the grid, one grain otherwise)翻译存疑
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]） (two grains at the corner of the grid, one grain otherwise)翻译存疑 ==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）
在一次迭代中多个顶点的崩塌被称为”雪崩“。每一次雪崩最终都会停止，也就是说，经过有限数量的顶点崩塌，会达到某种稳定的构型，这样自动机就得到了很好的定义。此外，尽管顶点崩塌的顺序常常有许多可能的选择，但最终的稳定状态并不依赖于所选择的顺序; 这是沙堆模型具有的可交换性质。类似地，在每次迭代过程中，每个顶点的崩塌次数也与崩塌顺序的选择是无关的。
==Definition (undirected finite multigraphs)定义（无向有限多图）==
==定义（无向有限多重图）==
为了将'''<font color="#ff8000"> 沙堆模型</font>'''从标准方格的矩形网格推广到任意无向有限多重图 <math> G=(V,E)</math> ，在 <math> V</math> 中指定了一个不允许崩塌的特殊沉没顶点<math> s</math>。模型的构型(状态)服从函数<math> z:V\setminus\{s\}\rightarrow\mathbb{N}_0</math>，计算每个非沉没顶点上的非负沙粒数。非沉没顶点<math> v\in V\setminus\{s\} </math>当满足<math> z(v)\geq \deg(v) </math>时是不稳定的，它会产生崩塌，向给它的每个(非沉没)邻居分发一颗沙粒：
为了将'''沙堆模型'''从标准方格的矩形网格推广到任意无向有限多重图 <math> G=(V,E)</math> ，在 <math> V</math> 中指定了一个不允许崩塌的特殊”沉没 sink“ 顶点<math> s</math>。模型的构型(状态)服从函数<math> z:V\setminus\{s\}\rightarrow\mathbb{N}_0</math>，计算每个非沉没顶点上的非负沙粒数。非沉没顶点<math> v\in V\setminus\{s\} </math>当满足<math> z(v)\geq \deg(v) </math>时是不稳定的，它会产生崩塌，向给它的每个(非沉没)邻居分发一颗沙粒：
:<math>z(v) \to z(v) - \deg(v)</math>
:<math>z(v) \to z(v) - \deg(v)</math>
:<math>z(u) \to z(u) + 1</math>对于所有的<math>u\sim v</math>, <math>u\neq s</math>.
:<math>z(u) \to z(u) + 1</math>对于所有的<math>u\sim v</math>, <math>u\neq s</math>.
[[元胞自动机]]像之前一样进行，即在每次迭代中，向随机选择的非沉没顶点添加一个沙粒，不断进行崩塌过程，直到所有顶点都稳定。
The definition of the sandpile model given above for finite rectangular grids <math>\Gamma\subset\mathbb{Z}^2</math> of the standard square lattice <math>\mathbb{Z}^2</math> can then be seen as a special case of this definition: consider the graph <math>G=(V,E)</math> which is obtained from <math>\Gamma</math> by adding an additional vertex, the sink, and by drawing additional edges from the sink to every boundary vertex of <math>\Gamma</math> such that the [[Degree (graph theory)|degree]] of every non-sink vertex of <math>G</math> is four. In this manner, also sandpile models on non-rectangular grids of the standard square lattice (or of any other lattice) can be defined: Intersect some bounded subset <math>S</math> of <math>\mathbb{R}^2</math> with <math>\mathbb{Z}^2</math>. [[Edge contraction|Contract every edge]] of <math>\mathbb{Z}^2</math> whose two endpoints are not in <math>S\cap\mathbb{Z}^2</math>. The single remaining vertex outside of <math>S\cap\mathbb{Z}^2</math> then constitutes the sink of the resulting sandpile graph.
The definition of the sandpile model given above for finite rectangular grids <math>\Gamma\subset\mathbb{Z}^2</math> of the standard square lattice <math>\mathbb{Z}^2</math> can then be seen as a special case of this definition: consider the graph <math>G=(V,E)</math> which is obtained from <math>\Gamma</math> by adding an additional vertex, the sink, and by drawing additional edges from the sink to every boundary vertex of <math>\Gamma</math> such that the [[Degree (graph theory)|degree]] of every non-sink vertex of <math>G</math> is four. In this manner, also sandpile models on non-rectangular grids of the standard square lattice (or of any other lattice) can be defined: Intersect some bounded subset <math>S</math> of <math>\mathbb{R}^2</math> with <math>\mathbb{Z}^2</math>. [[Edge contraction|Contract every edge]] of <math>\mathbb{Z}^2</math> whose two endpoints are not in <math>S\cap\mathbb{Z}^2</math>. The single remaining vertex outside of <math>S\cap\mathbb{Z}^2</math> then constitutes the sink of the resulting sandpile graph.
上面给出的沙堆模型的定义，是在标准正方形网格<math>\mathbb{Z}^2</math>上的有限矩形网格<math>\Gamma\subset\mathbb{Z}^2</math>上，它可以看作是下面定义的一个特例：考虑图<math>G=(V,E)</math>，从<math>\Gamma</math>添加一个沉没顶点，并添加从沉没顶点到每个边界顶点的边，使得<math>G</math>的每个非沉没顶点的度数为4。以这种方式，也可以定义标准正方形网格(或任何其他类型网格)的非矩形格上的沙堆模型: 将<math>\mathbb{R}^2</math>的一些有界子集<math>S</math>与<math>\mathbb{R}^2</math>相交。收缩<math>\mathbb{Z}^2</math>的每条边，其两个端点不在<math>S\cap\mathbb{Z}^2</math>中。<math>S\cap\mathbb{Z}^2</math>之外的一个单独剩余顶点构成了最终沙堆图的沉没顶点。
上面给出的沙堆模型的定义，是在标准正方形网格<math>\mathbb{Z}^2</math>上的有限矩形网格<math>\Gamma\subset\mathbb{Z}^2</math>上，它可以看作是下面定义的一个特例：考虑图<math>G=(V,E)</math>，从<math>\Gamma</math>添加一个沉没顶点，并添加从沉没顶点到每个边界顶点的边，使得<math>G</math>的每个非沉没顶点的度数为4。以这种方式，也可以定义标准正方形网格(或任何其他类型网格)的非矩形格上的沙堆模型: 将<math>\mathbb{R}^2</math>的一些有界子集<math>S</math>与<math>\mathbb{R}^2</math>相交。收缩<math>\mathbb{Z}^2</math>的每条边，其两个端点不在<math>S\cap\mathbb{Z}^2</math>中。<math>S\cap\mathbb{Z}^2</math>之外的一个单独剩余顶点构成了最终沙堆图的沉没顶点。
==Transient and recurrent configurations瞬态和循环构型==
==瞬态和循环构型==
在上面定义的沙堆自动机的动力学过程中，一些稳定状态的构型（对于所有<math>v\in G\setminus\{s\}</math>，<math>0\leq z(v)<4</math>）经常无限次出现，而另一些则只能出现有限次（如果真的发生的话）。前者被称为“循环构型”，而后者被称为“瞬态构型”。因此，周期性构形由所有稳定的非负构形组成，这些构形可以从任何其他稳定构形中，通过反复向顶点添加沙粒，产生崩塌而得到。很容易看出，“最小稳定构型”<math>zum</math>，其中每个顶点放置<math>z_m(v)=deg(v)-1</math>颗沙粒，可从任何其他稳定构型得到（通过向每个顶点添加<math>deg(v)-z(v)-1\geq 0</math>颗沙粒）。因此，也就是说，周期性构型可以从最小稳定构型开始，通过添加沙粒，再稳定化得到。
在上面定义的沙堆自动机的动力学过程中，一些稳定状态的构型（对于所有<math>v\in G\setminus\{s\}</math>，<math>0\leq z(v)<4</math>）经常无限次出现，而另一些则只能出现有限次（如果真的发生的话）。前者被称为“循环构型”，而后者被称为“瞬态构型”。因此，周期性构型由所有稳定的非负构型组成，这些构型可以从任何其他稳定构型中，通过反复向顶点添加沙粒，产生崩塌而得到。很容易看出，“最小稳定构型”<math>zum</math>，其中每个顶点放置<math>z_m(v)=deg(v)-1</math>颗沙粒，可从任何其他稳定构型得到（通过向每个顶点添加<math>deg(v)-z(v)-1\geq 0</math>颗沙粒）。因此，也就是说，周期性构型可以从最小稳定构型开始，通过添加沙粒，再稳定化得到。
并非所有非负稳定构型都是循环的。例如，在一个至少包含由两个连通的非沉没顶点的图结构的沙堆模型中，如果这两个顶点没有放置沙粒，那么这个稳定结构是非循环的。为了证明这一点，首先要注意的是，沙粒的增加只能增加两个顶点放置的沙粒的总数。为了达到两个顶点都不放置沙粒的构型，从一个不是这种情况的构型出发，必然涉及到两个顶点中至少有一个崩塌的步骤。考虑这些步骤中的最后一个，在这个步骤中，两个顶点中的一个必须最后崩塌。由于崩塌会将对每个相邻的顶点转移一颗沙粒，这意味着两个顶点共同放置的沙粒总数不能低于一颗，因而得证。
并非所有非负稳定构型都是循环的。例如，在一个至少包含由两个连通的非沉没顶点的图结构的沙堆模型中，如果这两个顶点没有放置沙粒，那么这个稳定结构是非循环的。为了证明这一点，首先要注意的是，沙粒的增加只能增加两个顶点放置的沙粒的总数。为了达到两个顶点都不放置沙粒的构型，从一个不是这种情况的构型出发，必然涉及到两个顶点中至少有一个崩塌的步骤。考虑这些步骤中的最后一个，在这个步骤中，两个顶点中的一个必须最后崩塌。由于崩塌会将对每个相邻的顶点转移一颗沙粒，这意味着两个顶点共同放置的沙粒总数不能低于一颗，因而得证。
==Sandpile group沙堆群==
==沙堆群==
Given a configuration <math>z</math>, <math>z(v)\in\mathbb{N}_0</math> for all <math>v\in G\setminus\{s\}</math>, toppling unstable non-sink vertices on a finite connected graph until no unstable non-sink vertex remains leads to a unique ''stable'' configuration <math>z^\circ</math>, which is called the ''stabilization'' of <math>z</math>. Given two stable configurations <math>z</math> and <math>w</math>, we can define the operation <math>z*w \to (z+w)^\circ</math>, corresponding to the vertex-wise addition of grains followed by the stabilization of the resulting sandpile.
Given a configuration <math>z</math>, <math>z(v)\in\mathbb{N}_0</math> for all <math>v\in G\setminus\{s\}</math>, toppling unstable non-sink vertices on a finite connected graph until no unstable non-sink vertex remains leads to a unique ''stable'' configuration <math>z^\circ</math>, which is called the ''stabilization'' of <math>z</math>. Given two stable configurations <math>z</math> and <math>w</math>, we can define the operation <math>z*w \to (z+w)^\circ</math>, corresponding to the vertex-wise addition of grains followed by the stabilization of the resulting sandpile.
给定一个构型<math>z</math>，<math>z(v)\in\mathbb{N}_0</math>对于所有<math>v\in G\setminus\{s\}</math>，在有限连通图上使不稳定的非沉没顶点崩塌，直到没有不稳定的非汇顶点保留，这将导致唯一的“稳定”配置math>z^\circ</math>，这就是<math>z</math>的“稳定化”。给定两个稳定构型<math>z</math>和<math>w</math>，我们可以定义运算<math>z*w \to (z+w)^\circ</math>，对应于沙粒的顶点方向相加，然后稳定得到的沙堆。
给定一个构型<math>z</math>，<math>z(v)\in\mathbb{N}_0</math>对于所有<math>v\in G\setminus\{s\}</math>，在有限连通图上使不稳定的非沉没顶点崩塌，直到没有不稳定的非汇顶点保留，这将导致唯一的“稳定”构型math>z^\circ</math>，这就是<math>z</math>的“稳定化”。给定两个稳定构型<math>z</math>和<math>w</math>，我们可以定义运算<math>z*w \to (z+w)^\circ</math>，对应于沙粒的顶点方向相加，然后稳定得到的沙堆。<font color="#ff8000">corresponding to the vertex-wise addition of grains followed by the stabilization of the resulting sandpile.</font>
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）corresponding to the vertex-wise addition of grains翻译存疑
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）corresponding to the vertex-wise addition of grains翻译存疑
给定一个任意但固定的非沉没顶点的顺序，进行多个崩塌操作，可以通过使用拉普拉斯矩阵<math>\Delta=D-A</math>高效地编码多个崩塌操作（例如，在不稳定构型的稳定过程中可能发生），其中<math>D</math>是图的度矩阵，<math>A</math>是图的[[邻接矩阵]]。
在这种情况下，<math>\mathbf{x}</math>被称为崩塌或<math>z</math>的稳定过程的里程计函数。
在这种情况下，<math>\mathbf{x}</math>被称为崩塌或<math>z</math>的稳定过程的里程计函数 <font color="#ff8000">odometer function</font>。
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）odometer function翻译存疑
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）odometer function翻译存疑
在<math>*</math>运算下，递归构形的集合构成一个与约化图拉普拉斯矩阵<math>\Delta'</math>的核同构的阿贝尔群。对于 <math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>，其中<math>n</math> 表示顶点数（包括沉没顶点）。更一般地说，稳定构型集（瞬态和循环）在<math>*</math>.运算下形成'''<font color="#ff8000"> 交换幺半群Commutative monoid</font>'''。这个幺半群的最小理想同构于循环构型群。
在<math>*</math>运算下，递归构型的集合构成一个与约化图拉普拉斯矩阵<math>\Delta'</math>的核同构的阿贝尔群。对于 <math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>，其中<math>n</math> 表示顶点数（包括沉没顶点）。更一般地说，稳定构型集（瞬态和循环）在<math>*</math>.运算下形成'''<font color="#ff8000"> 交换幺半群Commutative monoid</font>'''。这个幺半群的最小理想同构于循环构型群。The minimal [[Semigroup#Subsemigroups and ideals|ideal]] of this monoid is then isomorphic to the group of recurrent configurations.
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）ideal翻译存疑
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）ideal翻译存疑
由循环构型形成的群，以及与之同构的群<math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>，通常称为'''<font color="#ff8000"> 沙堆群Sandpile group</font>'''。相同群的其它常用名称是“临界群”、“Jacobian群”或(不常见的)“Picard群”。然而，要注意的是，有些作者只把循环构型形成的组称为沙堆组，而为由<math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>（或相关的同构定义）定义的同构群保留Jacobian群或临界群的称呼。最后，一些作者使用Picard群来指代沙堆群和<math>\mathbb{Z}</math>的直接产物，后者出现在与沙堆模型密切相关的[[元胞自动机]]中，被称为'''<font color="#ff8000"> 碎片点火或美元博弈游戏Chip firing or Dollar game</font>'''。
给定上述同构，沙堆群的顺序是<math>\Delta'</math>的行列式，根据矩阵树定理，它是图的生成树数目。
给定上述同构，沙堆群的顺序是<math>\Delta'</math>的行列式，根据矩阵树定理，它是图的生成树数目。
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）the order of the sandpile group is the determinant of <math>\Delta'</math>的翻译存疑，order是否翻译成顺序
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）the order of the sandpile group is the determinant of <math>\Delta'</math>的翻译存疑，order是否翻译成顺序
==Self-organized criticality自组织临界性==
==[[自组织临界性]]==
模型最初源于这样一个事实，即在晶格上的模拟中，它被吸引到了它的[[临界状态]]，此时系统的关联长度和关联时间趋于无穷大，不需要对系统参数进行任何微调。这与早期临界现象的例子形成了对比，例如固体和液体之间，或液体和气体之间的'''[[相变]] phase transition'''，其中临界点只能通过精确调节（例如，温度）来达到。因此，在沙堆模型中，我们可以说临界性是[[自组织]]的。
一旦沙堆模型达到其临界状态，系统对扰动的响应和扰动细节之间就没有关联。一般来说，这意味着再往沙堆形成的斜坡上撒一粒沙子可能不会导致任何事情发生，或者可能导致整个沙堆形成的斜坡在大规模滑坡中崩塌。该模型还显示了1/f噪声 <math>1/f noise</math>，这是自然界中许多[[复杂系统]]的共同特征。
此模型仅在两个或多个维度中显示临界现象。沙堆模型可以用一维来表示; 然而，一维沙堆模型不是演化到临界状态，而是达到最小稳定状态，其中每个格点都趋向临界坡度。
此模型仅在两个或多个维度中显示临界现象。沙堆模型可以用一维来表示; 然而，一维沙堆模型不是演化到临界状态，而是达到最小稳定状态，其中每个格点都趋向临界坡度。
对于二维，相关共形场理论被认为是中心电荷为''c'' = −2的symplectic fermion辛费米子组成的；<ref>{{cite journal |author=S. Moghimi-Araghi |author2=M. A. Rajabpour |author3=S. Rouhani |title=Abelian Sandpile Model: a Conformal Field Theory Point of View |arxiv=cond-mat/0410434 |year=2004 |doi=10.1016/j.nuclphysb.2005.04.002 |volume=718|issue=3|journal=Nuclear Physics B|pages=362–370|bibcode = 2005NuPhB.718..362M |s2cid=16233977 }}</ref>
对于二维，相关共形场理论被认为是中心电荷为''c'' = −2的'''辛费米子 symplectic fermion'''组成的；<ref>{{cite journal |author=S. Moghimi-Araghi |author2=M. A. Rajabpour |author3=S. Rouhani |title=Abelian Sandpile Model: a Conformal Field Theory Point of View |arxiv=cond-mat/0410434 |year=2004 |doi=10.1016/j.nuclphysb.2005.04.002 |volume=718|issue=3|journal=Nuclear Physics B|pages=362–370|bibcode = 2005NuPhB.718..362M |s2cid=16233977 }}</ref>
==Properties属性==
==属性/性质==
===Least action principle最小作用原理===
===最小作用原理===
The stabilization of chip configurations obeys a form of ''[[principle of least action|least action principle]]'': each vertex topples no more than necessary in the course of the stabilization.<ref name=Fey2010>
The stabilization of chip configurations obeys a form of ''[[principle of least action|least action principle]]'': each vertex topples no more than necessary in the course of the stabilization.<ref name=Fey2010>
{{cite journal
{{cite journal
| pages=143–159|arxiv = 0901.3805 |bibcode = 2010JSP...138..143F |s2cid=7180488}}</ref>
| pages=143–159|arxiv = 0901.3805 |bibcode = 2010JSP...138..143F |s2cid=7180488}}</ref>
芯片构型的稳定遵循一种“最小作用原理”的形式：每个顶点在稳定过程中不超过必要的崩塌量。
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）chip configurations的翻译存疑
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）chip configurations的翻译存疑==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）
This can be formalized as follows. Call a sequence of topples ''legal'' if it only topples unstable vertices, and ''stabilizing'' if it results in a stable configuration. The standard way of stabilizing the sandpile is to find a maximal legal sequence; i.e., by toppling so long as it is possible. Such a sequence is obviously stabilizing, and the Abelian property of the sandpile is that all such sequences are equivalent up to permutation of the toppling order; that is, for any vertex <math>v</math>, the number of times <math>v</math> topples is the same in all legal stabilizing sequences. According to the least action principle, a '''minimal stabilizing''' sequence is also equivalent up to permutation of the toppling order to a legal (and still stabilizing) sequence. In particular, the configuration resulting from a minimal stabilizing sequence is the same as results from a maximal legal sequence.
This can be formalized as follows. Call a sequence of topples ''legal'' if it only topples unstable vertices, and ''stabilizing'' if it results in a stable configuration. The standard way of stabilizing the sandpile is to find a maximal legal sequence; i.e., by toppling so long as it is possible. Such a sequence is obviously stabilizing, and the Abelian property of the sandpile is that all such sequences are equivalent up to permutation of the toppling order; that is, for any vertex <math>v</math>, the number of times <math>v</math> topples is the same in all legal stabilizing sequences. According to the least action principle, a '''minimal stabilizing''' sequence is also equivalent up to permutation of the toppling order to a legal (and still stabilizing) sequence. In particular, the configuration resulting from a minimal stabilizing sequence is the same as results from a maximal legal sequence.