更改

沙堆模型 (查看源代码)

2020年11月15日 (日) 22:09的版本

添加51字节、 2020年11月15日 (日) 22:09

无编辑摘要

第22行：第22行： −

这个模型是一种''' [[元胞自动机]]模型 Cellular automaton'''。在最初的公式中，有限网格上的每个位置都有一个与沙堆的坡度相对应的关联值。当“沙粒”(或“碎片”)被随机放置在沙堆上时，放置位置的斜坡就会堆积起来，直到倾斜程度超过一个特定的阈值，这个位置倒塌，沙子会转移到邻近的位置，增加它们的斜坡。Bak，Tang和 Wiesenfeld考虑了在网格上连续随机放置沙粒的过程; 每次这样在特定位置放置沙粒有可能不会产生影响，也有可能会引起级联反应，影响到周围的其他位置。

+

这个模型是一种''' [[元胞自动机]]模型 Cellular automaton'''。在最初的公式中，有限网格上的每个位置都有一个与沙堆的坡度相对应的关联值。当“沙粒”（或“碎片”）被随机放置在沙堆上时，放置位置的斜坡就会堆积起来，直到倾斜程度超过一个特定的阈值，这个位置倒塌，沙子会转移到邻近的位置，增加它们的斜坡。Bak，Tang和 Wiesenfeld考虑了在网格上连续随机放置沙粒的过程; 每次这样在特定位置放置沙粒有可能不会产生影响，也有可能会引起级联反应，影响到周围的其他位置。

−

~~该模型已经在无限栅格、其他(非方形)栅格和任意图(包括有向多重图)上进行了研究。~~<ref name=Hol2008>{{cite book

+

该模型已经在无限栅格、其他（非方形）栅格和任意图（包括有向多重图）上进行了研究。<ref name=Hol2008>{{cite book

| year = 2008

第40行：第40行： −

沙堆模型是一个'''元胞自动机cellular automaton '''，它最初定义在<math> N\times M </math>~~矩形网格(棋盘格)上，其顶点在标准的正方形格子~~<math> \mathbb{Z}^2 </math>上<math> \Gamma\subset\mathbb{Z}^2 </math>。

+

沙堆模型是一个'''元胞自动机cellular automaton '''，它最初定义在<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> (x_i,y_i)\in\Gamma </math>。

+

#根据某种概率分布（通常为均匀分布）随机选择一个顶点。根据一些概率分布（通常是均匀的）选择一个随机顶点<math> (x_i,y_i)\in\Gamma </math>。

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

#如果所有的顶点都是稳定的，即如果对于<math>(x,y)\in\Gamma</math>，<math>z_i(x,y)<4</math>，那么构型<math>z_i</math>被认为是稳定的。在这种情况下，继续下一轮迭代。

−

#如果至少有一个顶点是不稳定的，即对于一些<math>(x_u,y_u)\in\Gamma</math>，<math>z_i(x_u,y_u)\geq 4</math>，<math>z_i</math>被认为是不稳定的。在这种情况下，随机选择任意不稳定顶点<math> (x_u,y_u)\in\Gamma</math>~~。将该顶点的沙粒数减少4个，清空这个顶点，并将其每个(最多4个)直接邻居的沙粒数增加1个。即：~~ <math>z_i(x_u,y_u) \rightarrow z_i(x_u,y_u) - 4,</math>，如果 <math>( x_u \pm 1, y_u\pm 1)\in\Gamma</math>. ， <math>z_i( x_u \pm 1, y_u \pm 1) \rightarrow z_i( x_u \pm 1, y_u\pm 1) + 1</math>。如果一个在边界的顶点产生崩塌，这将导致沙粒的净损失（两粒在网格的角落，一粒在其他地方）。 (two grains at the corner of the grid, one grain otherwise)

+

#如果至少有一个顶点是不稳定的，即对于一些<math>(x_u,y_u)\in\Gamma</math>，<math>z_i(x_u,y_u)\geq 4</math>，<math>z_i</math>被认为是不稳定的。在这种情况下，随机选择任意不稳定顶点<math> (x_u,y_u)\in\Gamma</math>。将该顶点的沙粒数减少4个，清空这个顶点，并将其每个（最多4个）直接邻居的沙粒数增加1个。即： <math>z_i(x_u,y_u) \rightarrow z_i(x_u,y_u) - 4,</math>，如果 <math>( x_u \pm 1, y_u\pm 1)\in\Gamma</math>. ， <math>z_i( x_u \pm 1, y_u \pm 1) \rightarrow z_i( x_u \pm 1, y_u\pm 1) + 1</math>。如果一个在边界的顶点产生崩塌，这将导致沙粒的净损失（两粒在网格的角落，一粒在其他地方）。 (two grains at the corner of the grid, one grain otherwise)

#由于沙粒的重新分布，一个顶点的崩塌会使其他顶点不稳定。这样，重复崩塌的过程，直到<math>z_i</math>状态下的所有顶点最终稳定下来，继续下一轮迭代。

第62行：第62行： −

为了将'''沙堆模型'''从标准方格的矩形网格推广到任意无向有限多重图 <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> 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(u) \to z(u) + 1</math>对于所有的<math>u\sim v</math>, <math>u\neq s</math>.

第70行：第70行： −

上面给出的沙堆模型的定义，是在标准正方形网格<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>之外的一个单独剩余顶点构成了最终沙堆图的沉没顶点。

==瞬态和循环构型==

第105行：第105行： −

由循环构型形成的群，以及与之同构的群<math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>，通常称为''' 沙堆群Sandpile group'''。相同群的其它常用名称是“临界群”、“Jacobian群”或(不常见的)“Picard群”。然而，要注意的是，有些作者只把循环构型形成的组称为沙堆组，而为由<math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>（或相关的同构定义）定义的同构群保留Jacobian群或临界群的称呼。最后，一些作者使用Picard群来指代沙堆群和<math>\mathbb{Z}</math>的直接产物，后者出现在与沙堆模型密切相关的[[元胞自动机]]中，被称为''' 碎片点火或美元博弈游戏Chip firing or Dollar game'''。

+

由循环构型形成的群，以及与之同构的群<math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>，通常称为''' 沙堆群Sandpile group'''。相同群的其它常用名称是“临界群”、“Jacobian群”或（不常见的）“Picard群”。然而，要注意的是，有些作者只把循环构型形成的组称为沙堆组，而为由<math>\mathbf{Z}^{n-1}/\mathbf{Z}^{n-1}\Delta'</math>（或相关的同构定义）定义的同构群保留Jacobian群或临界群的称呼。最后，一些作者使用Picard群来指代沙堆群和<math>\mathbb{Z}</math>的直接产物，后者出现在与沙堆模型密切相关的[[元胞自动机]]中，被称为''' 碎片点火或美元博弈游戏Chip firing or Dollar game'''。

Given the isomorphisms stated above, the order of the sandpile group is the determinant of {\displaystyle \Delta '}\Delta ', which by the matrix tree theorem is the number of spanning trees of the graph.

思无涯咿呀咿呀

管理员

2,443

个编辑