2,443
个编辑
更改
跳到导航
跳到搜索
第22行：
第22行： − 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 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> 第82行：
第70行： − 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. 第94行：
第81行： − 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. − + 第104行：
第90行： − Deleting the row and column of <math>\Delta</math> corresponding with the sink yields the ''reduced graph Laplacian'' <math>\Delta'</math>. Then, when starting with a configuration <math>z</math> and toppling each vertex <math>v</math> a total of <math>\mathbf{x}(v)\in\mathbb{N}_0</math> times yields the configuration <math>z-\Delta'\boldsymbol{\cdot}~\mathbf{x}</math>, where <math>\boldsymbol{\cdot}</math> is the contraction product. Furthermore, if <math>\mathbf{x}</math> corresponds to the number of times each vertex is toppled during the stabilization of a given configuration <math>z</math>, then − :<math>z^\circ=z-\Delta'\boldsymbol{\cdot}~\mathbf{x}</math> − − +
无编辑摘要
|author-link=Per Bak |author2-link=Chao Tang }}</ref>中提出的。
|author-link=Per Bak |author2-link=Chao Tang }}</ref>中提出的。
这个模型是一种'''<font color="#ff8000"> [[元胞自动机]]模型 Cellular automaton</font>'''。在最初的公式中，有限网格上的每个位置都有一个与沙堆的坡度相对应的关联值。当“沙粒”(或“碎片”)被随机放置在沙堆上时，放置位置的斜坡就会堆积起来，直到倾斜程度超过一个特定的阈值，这个位置倒塌，沙子会转移到邻近的位置，增加它们的斜坡。Bak，Tang和 Wiesenfeld考虑了在网格上连续随机放置沙粒的过程; 每次这样在特定位置放置沙粒有可能不会产生影响，也有可能会引起[[级联反应]]，影响到周围的其他位置。
这个模型是一种'''<font color="#ff8000"> [[元胞自动机]]模型 Cellular automaton</font>'''。在最初的公式中，有限网格上的每个位置都有一个与沙堆的坡度相对应的关联值。当“沙粒”(或“碎片”)被随机放置在沙堆上时，放置位置的斜坡就会堆积起来，直到倾斜程度超过一个特定的阈值，这个位置倒塌，沙子会转移到邻近的位置，增加它们的斜坡。Bak，Tang和 Wiesenfeld考虑了在网格上连续随机放置沙粒的过程; 每次这样在特定位置放置沙粒有可能不会产生影响，也有可能会引起级联反应，影响到周围的其他位置。
该模型已经在无限栅格、其他(非方形)栅格和任意图(包括有向多重图)上进行了研究。<ref name=Hol2008>{{cite book
该模型已经在无限栅格、其他(非方形)栅格和任意图(包括有向多重图)上进行了研究。<ref name=Hol2008>{{cite book
[[元胞自动机]]像之前一样进行，即在每次迭代中，向随机选择的非沉没顶点添加一个沙粒，不断进行崩塌过程，直到所有顶点都稳定。
[[元胞自动机]]像之前一样进行，即在每次迭代中，向随机选择的非沉没顶点添加一个沙粒，不断进行崩塌过程，直到所有顶点都稳定。
上面给出的沙堆模型的定义，是在标准正方形网格<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>之外的一个单独剩余顶点构成了最终沙堆图的沉没顶点。
==沙堆群==
==沙堆群==
给定一个构型<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>
给定一个构型<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翻译存疑 ==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）
删除与沉没顶点相对应的 <math>\Delta</math>的行和列，得到简化图拉普拉斯矩阵 <math>\Delta'</math>。然后，当以一个构型<math>z</math> 开始，并将每个顶点<math>v</math>进行总共<math>\mathbf{x}(v)\in\mathbb{N}_0</math>次的崩塌操作时，产生<math>z-\Delta'\boldsymbol{\cdot}~\mathbf{x}</math>构型，其中<math>\boldsymbol{\cdot}</math>是收缩积。此外，如果 <math>\mathbf{x}</math> 对应于在给定构型<math>z</math>的稳定过程中每个顶点产生崩塌的次数，则
删除与沉没顶点相对应的 <math>\Delta</math>的行和列，得到简化图拉普拉斯矩阵 <math>\Delta'</math>。然后，当以一个构型<math>z</math> 开始，并将每个顶点<math>v</math>进行总共<math>\mathbf{x}(v)\in\mathbb{N}_0</math>次的崩塌操作时，产生<math>z-\Delta'\boldsymbol{\cdot}~\mathbf{x}</math>构型，其中<math>\boldsymbol{\cdot}</math>是收缩积。此外，如果 <math>\mathbf{x}</math> 对应于在给定构型<math>z</math>的稳定过程中每个顶点产生崩塌的次数，则
:<math>z^\circ=z-\Delta'\boldsymbol{\cdot}~\mathbf{x}</math>
:<math>z^\circ=z-\Delta'\boldsymbol{\cdot}~\mathbf{x}</math>
在这种情况下，<math>\mathbf{x}</math>被称为崩塌或<math>z</math>的稳定过程的里程计函数 <font color="#ff8000">odometer function</font>。
在这种情况下，<math>\mathbf{x}</math>被称为崩塌或<math>z</math>的稳定过程的里程计函数 <font color="#ff8000">odometer function</font>。
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）odometer function翻译存疑
==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）odometer function翻译存疑 ==[[用户:Zcy|Zcy]]（[[用户讨论:Zcy|讨论]]）