更改

[[File:Sandpile identity 300x205.png|upright=1.25|thumb|The identity element of the sandpile group of a rectangular grid. Yellow pixels correspond to vertices carrying three particles, lilac to two particles, green to one, and black to zero.]]

[[File:Sandpile identity 300x205.png|upright=1.25|thumb|The identity element of the sandpile group of a rectangular grid. Yellow pixels correspond to vertices carrying three particles, lilac to two particles, green to one, and black to zero.]]

 

The identity element of the sandpile group of a rectangular grid. Yellow pixels correspond to vertices carrying three particles, lilac to two particles, green to one, and black to zero.

The identity element of the sandpile group of a rectangular grid. Yellow pixels correspond to vertices carrying three particles, lilac to two particles, green to one, and black to zero.

The Abelian sandpile model, also known as the Bak–Tang–Wiesenfeld model, was the first discovered example of a dynamical system displaying self-organized criticality.  It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.

The Abelian sandpile model, also known as the Bak–Tang–Wiesenfeld model, was the first discovered example of a dynamical system displaying self-organized criticality.  It was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper.

阿贝尔沙堆模型，也被称为 Bak-Tang-Wiesenfeld 模型，是第一个发现的动力系统展示自组织临界性的例子。它是由 Per Bak，Chao Tang 和 Kurt Wiesenfeld 在1987年的一篇论文中介绍的。

'''<font color="#ff8000"> 阿贝尔沙堆模型Abelian sandpile model</font>'''，也被称为 Bak-Tang-Wiesenfeld 模型，是第一个发现的动力系统展示自组织临界性的例子。它是由 Per Bak，Chao Tang 和 Kurt Wiesenfeld 在1987年的一篇论文中介绍的。

{{cite journal

{{cite journal

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>'''。在最初的公式中，有限网格上的每个位置都有一个与桩的坡度相对应的关联值。这个斜坡以“沙粒”(或“碎片”)随机放置在桩上的方式逐渐形成，直到斜坡超过一个特定的阈值，在这个阈值的时候，这个位置倒塌，将沙子转移到邻近的位置，增加了它们的斜坡。贝克、唐和维森菲尔德考虑了在网格上连续随机放置沙粒的过程; 每次这样放置沙粒在特定地点可能没有效果，或者可能会引起级联反应，影响许多地点。

  | year = 1987

  | year = 1987

The sandpile model is a cellular automaton originally defined on a N\times M rectangular grid (checkerboard) \Gamma\subset\mathbb{Z}^2 of the standard square lattice \mathbb{Z}^2.

The sandpile model is a cellular automaton originally defined on a N\times M rectangular grid (checkerboard) \Gamma\subset\mathbb{Z}^2 of the standard square lattice \mathbb{Z}^2.

沙堆模型是一个最初定义在 n 乘 m 矩形网格(棋盘格) Gamma 子集 mathbb { z } ^ 2的标准正方形格子数学{ z } ^ 2上的细胞自动机模型。

沙堆模型是一个最初定义在 n 乘 m 矩形网格(棋盘格) Gamma 子集 mathbb { z } ^ 2的标准正方形格子数学{ z } ^ 2上的l细胞自动机模型。

  | pages = 381&ndash;384

  | pages = 381&ndash;384

  Add one grain of sand to this vertex while letting the grain numbers for all other vertices unchanged, i.e. set<br />z_i(x_i,y_i)=z_{i-1}(x_i,y_i)+1 and<br />z_i(x,y)=z_{i-1}(x,y) for all (x,y)\neq(x_i,y_i).

  Add one grain of sand to this vertex while letting the grain numbers for all other vertices unchanged, i.e. set<br />z_i(x_i,y_i)=z_{i-1}(x_i,y_i)+1 and<br />z_i(x,y)=z_{i-1}(x,y) for all (x,y)\neq(x_i,y_i).

向这个顶点添加一粒沙子，同时让其他顶点的粒子数保持不变，即。设置 < br/> z _ i (x _ i，y _ i) = z _ { i-1}(x _ i，y _ i) + 1和 < br/> z _ i (x，y) = z _ { i-1}(x，y)为所有(x，y) neq (x _ i，y _ i) 。

向这个顶点添加一粒沙子，同时让其他顶点的粒子数保持不变，即。对所有(x,y)\neq(x_i,y_i)设置 <br />z_i(x_i,y_i)=z_{i-1}(x_i,y_i)+1 和<br />z_i(x,y)=z_{i-1}(x,y)。

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.

  If all vertices are stable, i.e. z_i(x,y)<4 for all (x,y)\in\Gamma, also the configuration z_i is said to be stable. In this case, continue with the next iteration.

  If all vertices are stable, i.e. z_i(x,y)<4 for all (x,y)\in\Gamma, also the configuration z_i is said to be stable. In this case, continue with the next iteration.

如果所有的顶点都是稳定的，即。Z _ i (x，y) < 4对于 Gamma 中的所有(x，y) ，配置 z _ i 也被认为是稳定的。在这种情况下，继续下一个迭代。

如果所有的顶点都是稳定的，即 z_i(x,y)<4对于 Gamma 中的所有(x,y)\in\Gamma，配置 z_i 也被认为是稳定的。在这种情况下，继续下一个迭代。

  If at least one vertex is unstable, i.e. z_i(x_u,y_u)\geq 4 for some (x_u,y_u)\in\Gamma, the whole configuration z_i is said to be unstable. In this case, choose any unstable vertex (x_u,y_u)\in\Gamma 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 />z_i(x_u,y_u) \rightarrow z_i(x_u,y_u) - 4,, and<br />z_i( x_u \pm 1, y_u \pm 1) \rightarrow z_i( x_u \pm 1, y_u\pm 1) + 1 if ( x_u \pm 1, y_u\pm 1)\in\Gamma.<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).

  If at least one vertex is unstable, i.e. z_i(x_u,y_u)\geq 4 for some (x_u,y_u)\in\Gamma, the whole configuration z_i is said to be unstable. In this case, choose any unstable vertex (x_u,y_u)\in\Gamma 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 />z_i(x_u,y_u) \rightarrow z_i(x_u,y_u) - 4,, and<br />z_i( x_u \pm 1, y_u \pm 1) \rightarrow z_i( x_u \pm 1, y_u\pm 1) + 1 if ( x_u \pm 1, y_u\pm 1)\in\Gamma.<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).

如果至少有一个顶点是不稳定的，即。Z _ i (x _ u，y _ u) geq 4对于 γ 中的某些(x _ u，y _ u) ，整个构型 z _ i 被认为是不稳定的。在这种情况下，随机选择 Gamma 中的任意不稳定顶点(x_u，y _ u) 。通过减少四颗粒数和增加一颗粒数(最多四颗)来推翻这个顶点。设置 < br/> z _ i (x _ u，y _ u) right tarrow z _ i (x _ u，y _ u)-4，以及 < br/> z _ i (x _ u pm 1，y _ u pm 1) right tarrow z _ i (x _ u pm 1，y _ u pm 1) + 1 if (x _ u pm 1，y _ u pm 1) in Gamma。< br/> 如果一个顶点在畴的边界倾斜，这将导致晶粒的净损失(两个晶粒在网格的角落，否则一个晶粒)。

如果至少有一个顶点是不稳定的，即 z_i(x_u,y_u)\geq 4对于 γ 中的某些(x_u,y_u)\in\Gamma，整个构型 z_i  被认为是不稳定的。在这种情况下，随机选择 Gamma 中的任意不稳定顶点(x_u,y_u)\in\Gamma 。通过减少四颗粒数和增加一颗粒数(最多四颗)来推翻这个顶点。设置 <br />z_i(x_u,y_u) \rightarrow z_i(x_u,y_u) - 4，以及 <br />z_i( x_u \pm 1, y_u \pm 1) \rightarrow z_i( x_u \pm 1, y_u\pm 1) + 1 if ( x_u \pm 1, y_u\pm 1)\in\Gamma.<br /> 如果一个顶点在畴的边界倾斜，这将导致晶粒的净损失(两个晶粒在网格的角落，否则一个晶粒)。

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

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

  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 z_i eventually become stable and continue with the next iteration.

  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 z_i eventually become stable and continue with the next iteration.

To generalize the sandpile model from the rectangular grid of the standard square lattice to an arbitrary undirected finite multigraph G=(V,E) without loops, a special vertex s\in V called the sink is specified that is not allowed to topple. A configuration (state) of the model is then a function z:V\setminus\{s\}\rightarrow\mathbb{N}_0 counting the non-negative number of grains on each non-sink vertex. A non-sink vertex v\in V\setminus\{s\} with  

To generalize the sandpile model from the rectangular grid of the standard square lattice to an arbitrary undirected finite multigraph G=(V,E) without loops, a special vertex s\in V called the sink is specified that is not allowed to topple. A configuration (state) of the model is then a function z:V\setminus\{s\}\rightarrow\mathbb{N}_0 counting the non-negative number of grains on each non-sink vertex. A non-sink vertex v\in V\setminus\{s\} with  

为了将沙堆模型从标准正方格的矩形网格推广到任意无向有限重图 g = (v，e) ，在 v 中指定了一个不允许倒塌的特殊顶点 s。模型的配置(状态)是一个函数 z: v set- { s }-right tarrow mathbb { n } _ 0，计算每个非汇顶点上的非负粒子数。V set- { s }中的非接收点 v

为了将'''<font color="#ff8000"> 沙堆模型</font>'''从标准正方格的矩形网格推广到任意无向有限重图 g = (v，e) ，在 v 中指定了一个不允许倒塌的特殊顶点 s。模型的配置(状态)是一个函数 z: v set- { s }-right tarrow mathbb { n } _ 0，计算每个非汇顶点上的非负粒子数。V set- { s }中的非接收点 v

  | pages = 331&ndash;364

  | pages = 331&ndash;364

Z (u) to z (u) + 1 for all u sim v，u neq s.

Z (u) to z (u) + 1 for all u sim v，u neq s.

==Definition (rectangular grids)==

==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>.

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>.

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.

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.

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.

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 definition of the sandpile model given above for finite rectangular grids \Gamma\subset\mathbb{Z}^2 of the standard square lattice \mathbb{Z}^2 can then be seen as a special case of this definition: consider the graph G=(V,E) which is obtained from \Gamma by adding an additional vertex, the sink, and by drawing additional edges from the sink to every boundary vertex of \Gamma such that the degree of every non-sink vertex of G 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 S of \mathbb{R}^2 with \mathbb{Z}^2. Contract every edge of \mathbb{Z}^2 whose two endpoints are not in S\cap\mathbb{Z}^2. The single remaining vertex outside of S\cap\mathbb{Z}^2 then constitutes the sink of the resulting sandpile graph.

The definition of the sandpile model given above for finite rectangular grids \Gamma\subset\mathbb{Z}^2 of the standard square lattice \mathbb{Z}^2 can then be seen as a special case of this definition: consider the graph G=(V,E) which is obtained from \Gamma by adding an additional vertex, the sink, and by drawing additional edges from the sink to every boundary vertex of \Gamma such that the degree of every non-sink vertex of G 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 S of \mathbb{R}^2 with \mathbb{Z}^2. Contract every edge of \mathbb{Z}^2 whose two endpoints are not in S\cap\mathbb{Z}^2. The single remaining vertex outside of S\cap\mathbb{Z}^2 then constitutes the sink of the resulting sandpile graph.

The dynamics of the automaton at iteration <math>i\in\mathbb{N}</math> are then defined as follows:

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).  

# Choose a random vertex <math>(x_i,y_i)\in\Gamma</math> according to some probability distribution (usually uniform).  

In the dynamics of the sandpile automaton defined above, some stable configurations (0\leq z(v)<4 for all v\in G\setminus\{s\}) 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 z_m, where every vertex carries z_m(v)=deg(v)-1 grains of sand, is reachable from any other stable configuration (add deg(v)-z(v)-1\geq 0 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.

In the dynamics of the sandpile automaton defined above, some stable configurations (0\leq z(v)<4 for all v\in G\setminus\{s\}) 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 z_m, where every vertex carries z_m(v)=deg(v)-1 grains of sand, is reachable from any other stable configuration (add deg(v)-z(v)-1\geq 0 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.

在以上定义的沙堆自动机的动力学中，一些稳定的构型(0 leq z (v) < 4)经常出现，而另一些构型只能出现有限次数(如果有的话)。前者称为循环配置，而后者称为瞬态配置。因此，轮回结构由所有稳定的非负结构组成，这些结构可以通过反复向顶点添加砂粒和倾斜而从任何其他稳定结构中得到。显而易见，最小稳定结构 zm，其中每个顶点携带 z _ m (v) = deg (v)-1沙粒，可以从任何其他稳定结构(向每个顶点添加 deg (v)-z (v)-1 geq 0沙粒)到达。因此，等价的回归构型正是那些只需加入砂粒并进行稳定化即可从最小稳定构型得到的构型。

在上面定义的沙堆自动机的动力学中，一些稳定的组态（0\leq z（v）<4，对于所有v\In G\setminus\{s}）经常出现，而另一些则只能出现有限次（如果有的话）。前者被称为重复配置，而后者被称为瞬态配置。因此，周期性构形由所有稳定的非负构形组成，这些构形可以通过反复向顶点添加砂粒和倾倒而达到。很容易看出，最小稳定配置z峎m，其中每个顶点携带z峎m（v）=deg（v）-1颗粒，可从任何其他稳定配置（每个顶点添加deg（v）-z（v）-1\geq 0颗粒）。因此，等效地说，周期性构型正是通过添加沙粒和稳定化就可以从最小稳定构型得到的构型。

 

# 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>.

# 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 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.

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.

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.

# 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).

# 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.

# 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.