阿贝尔沙堆模型¶
介绍¶
这些注释介绍了达尔的阿贝尔沙堆模型(ASM)和Sage沙堆(Sage中用于计算沙堆的工具集)。为了更全面地介绍ASM的理论,论文 Chip-Firing and Rotor-Routing on Directed Graphs [H] Holroyd等人,以及 Riemann-Roch and Abel-Jacobi Theory on a Finite Graph 贝克和诺琳 [BN] 是推荐的。另请参见 [PPW2013].
为了描述ASM,我们从 沙堆图 :有向多重图 Gamma 有顶点的 s 从每个顶点都可以访问。通过 多重图 ,我们的意思是 Gamma 分配了一个非负整数权重。说 s 是 可接近的 从某个顶点 v 表示有一个有向边的序列(可能是空的),从 v 结束于 s . 我们打电话 s 这个 sink 沙堆图,即使它可能有外边缘,原因将在一瞬间被阐明。
我们表示 Gamma 通过 V ,并定义 tilde{{V}} = Vsetminus{{s}} . 对于任何顶点 v ,我们让 mbox{{out-degree}}(v) (the out-degree 属于 v )是所有边离开的重量之和 v .
构型和除数¶
A 配置 在 Gamma 是的元素 ZZ_{{geq 0}} tilde{{V}} 也就是说,将一个非负整数赋给每个非墨水顶点。我们把每一个整数看作是放置在相应顶点的沙粒数。A 除数 在 Gamma 是的元素 ZZ V ,即自由交换群中的一个元素 all 顶点的。在除数的上下文中,有时考虑除数是有用的 Gamma 把美元分配给每个顶点,用负整数表示债务。
稳定¶
一种配置 c 是 稳定的 在顶点 vintilde{{V}} 如果 c(v) < mbox{{out-degree}}(v) . 否则, c 是 不稳定的 在 v . 一种配置 c (本身)是 稳定的 如果它在每个非墨水顶点是稳定的。否则, c 是 不稳定的 .如果 c 不稳定于 v ,顶点 v 可以是 解雇 ( 倾覆 )通过移除 mbox{{out-degree}}(v) 沙粒 v 在附近的 v ,由边离开的重量决定 v (每个顶点 w 得到与边缘重量相等的颗粒 (v, w) 是,如果有这样的优势)。请注意,添加到水槽中的颗粒 s 不计算在内(即,它们“消失”)。
尽管我们的意图是最好的,但有时我们会考虑发射一个稳定的顶点,从而在该顶点处产生一个负数量沙子的“配置”。我们也可以 reverse-fire 一个顶点,从顶点的邻域(包括水槽)吸收沙子。
例子。 考虑图表:
所有的边都有重量 1 除了顶点1到顶点3的边具有权重 2 . 如果我们让 c = (5,0,1) 在顶点1、2和3上分别指定了砂粒数时,只有出度为4的顶点1不稳定。发射顶点1提供了一个新的配置 c' = (1,1,3) . 在这里, 4 颗粒离开顶点1。其中一个到了sink顶点(并被遗忘了),一个转到了顶点2,两个转到了顶点3,因为从1到3的边具有权重 2 . 新配置中的顶点3现在不稳定。下面是本例的Sage代码。:
sage: g = {0:{},
....: 1:{0:1, 2:1, 3:2},
....: 2:{1:1, 3:1},
....: 3:{1:1, 2:1}}
sage: S = Sandpile(g, 0) # create the sandpile
sage: S.show(edge_labels=true) # display the graph
创建配置:
sage: c = SandpileConfig(S, {1:5, 2:0, 3:1})
sage: S.out_degree()
{0: 0, 1: 4, 2: 2, 3: 2}
顶点火 1 ::
sage: c.fire_vertex(1)
{1: 1, 2: 1, 3: 3}
配置不变:
sage: c
{1: 5, 2: 0, 3: 1}
反复激发顶点,直到配置变得稳定:
sage: c.stabilize()
{1: 2, 2: 1, 3: 1}
选择::
sage: ~c # shorthand for c.stabilize()
{1: 2, 2: 1, 3: 1}
sage: c.stabilize(with_firing_vector=true)
[{1: 2, 2: 1, 3: 1}, {1: 2, 2: 2, 3: 3}]
由于顶点3在触发顶点1后变得不稳定,它可以被发射,从而导致顶点2变得不稳定,等等。反复发射最终导致稳定的配置。上面Sage代码的最后一行是一个列表,其中的第一个元素是生成的稳定配置, (2,1,1) . 第二个分量记录每个顶点在稳定中发射的次数。
由于水槽可以从每个非墨水顶点访问,并且从不点火,因此在有限数量的顶点点火后,每个配置都将稳定下来。这并不明显,但由此产生的稳定性与不稳定顶点的激发顺序无关。因此,每个配置稳定到唯一的稳定配置。
拉普拉斯¶
固定顶点的总顺序 Gamma ,从而通过数字对顶点进行标记 1, 2, ldots, n 对某些人来说 n (按给定顺序)。这个 拉普拉斯 属于 Gamma 是
在哪里? D 是顶点外度的对角矩阵(即对角线 n times n -谁的矩阵 (i, i) -入口是顶点的出度 i ) A 邻接矩阵 (i,j) -第项是从顶点开始的边的权重 i 到顶点 j ,我们认为是 0 如果没有边缘。这个 约化拉普拉斯算子 , tilde{{L}} ,是拉普拉斯算子的子矩阵,去掉对应于汇点的行和列。触发一个配置的顶点与减去相应的简化拉普拉斯的行是一样的。
例子。 (续):
sage: S.vertices() # the ordering of the vertices
[0, 1, 2, 3]
sage: S.laplacian()
[ 0 0 0 0]
[-1 4 -1 -2]
[ 0 -1 2 -1]
[ 0 -1 -1 2]
sage: S.reduced_laplacian()
[ 4 -1 -2]
[-1 2 -1]
[-1 -1 2]
我们之前考虑过的配置:
sage: c = SandpileConfig(S, [5,0,1])
sage: c
{1: 5, 2: 0, 3: 1}
触发顶点1与从构型中减去相应的简化拉普拉斯方程行(视为向量)相同:
sage: c.fire_vertex(1).values()
[1, 1, 3]
sage: S.reduced_laplacian()[0]
(4, -1, -2)
sage: vector([5,0,1]) - vector([4,-1,-2])
(1, 1, 3)
经常性要素¶
想象一个实验,在这个实验中,一次将一粒沙子扔到一张图表上,停下来让形状在滴间稳定下来。在这个过程中,有些配置只会出现一次。举例来说,一个图的加和序列是空的。其他配置——所谓 重复配置 ---当这个过程被无限重复时,会被无限经常地看到。
准确地说,是一种配置 c 是 经常性 如果(i)它是稳定的,和(ii)给定任何配置 a ,有一个配置 b 这样的话 c = mbox{{stab}}(a+b) ,稳定 a + b .
这个 maximal-stable 配置,表示 c_{{mathrm{{max}}}} 定义为 c_{{mathrm{{max}}}}(v)=mbox{{out-degree}}(v)-1 对于所有非链接顶点 v . 很明显 c_{{mathrm{{max}}}} 是经常性的。此外,不难看出,当且仅当一个配置具有 mbox{{stab}}(a+c_{{mathrm{{max}}}}) 对于某些配置 a .
例子。 (续):
sage: S.recurrents(verbose=false)
[[3, 1, 1], [2, 1, 1], [3, 1, 0]]
sage: c = SandpileConfig(S, [2,1,1])
sage: c
{1: 2, 2: 1, 3: 1}
sage: c.is_recurrent()
True
sage: S.max_stable()
{1: 3, 2: 1, 3: 1}
将任何配置添加到“最大稳定”配置并稳定会产生一个重复配置:
sage: x = SandpileConfig(S, [1,0,0])
sage: x + S.max_stable()
{1: 4, 2: 1, 3: 1}
使用 &
添加和稳定:
sage: c = x & S.max_stable()
sage: c
{1: 3, 2: 1, 3: 0}
sage: c.is_recurrent()
True
注意执行加法和稳定化的各种方法:
sage: m = S.max_stable()
sage: (x + m).stabilize() == ~(x + m)
True
sage: (x + m).stabilize() == x & m
True
燃烧配置¶
A 燃烧配置 是一个 ZZ_{{geq 0}} -线性组合 f 具有非负项的约化拉普拉斯矩阵的行,使得每一个顶点都可以从某个顶点获得 f (换句话说,对于每个顶点 w ,有一条路 v in operatorname{{supp}} f 到 w ). 对应的 烧录脚本 给出了 ZZ_{{geq 0}} -需要线性组合来获得燃烧结构。所以如果 b 是一个燃烧的配置, sigma 是它的剧本,而且 tilde{{L}} 是约化拉普拉斯吗 sigma,tilde{{L}} = b . 这个 最小燃烧配置 是具有最小脚本的那个(它的每个组件都不大于任何其他用于刻录配置的脚本的相应组件)。
给定一个燃烧的配置 b 有剧本的 sigma ,以及任何配置 c 在同一张图上,以下内容是等效的:
c 反复发作;
c + b 稳定到 c ;
稳定的点火矢量 c + b 是 sigma .
烧录配置和脚本是使用Speer的脚本算法的修改版本来计算的。这是对Dhar燃烧算法的有向多重图的推广。
例子。 ::
sage: g = {0:{},1:{0:1,3:1,4:1},2:{0:1,3:1,5:1},
....: 3:{2:1,5:1},4:{1:1,3:1},5:{2:1,3:1}}
sage: G = Sandpile(g,0)
sage: G.burning_config()
{1: 2, 2: 0, 3: 1, 4: 1, 5: 0}
sage: G.burning_config().values()
[2, 0, 1, 1, 0]
sage: G.burning_script()
{1: 1, 2: 3, 3: 5, 4: 1, 5: 4}
sage: G.burning_script().values()
[1, 3, 5, 1, 4]
sage: matrix(G.burning_script().values())*G.reduced_laplacian()
[2 0 1 1 0]
沙堆群¶
稳定组态的集合形成一个交换幺半群,加法定义为普通加法,然后是稳定化。identity元素是全零配置。这个幺半群正是当底层图是DAG(有向无环图)时的群。
循环元素形成了一个亚幺半群,它是一个群。这个组叫做 沙堆群 对于 Gamma ,表示 mathcal{{S}}(Gamma) . 它的identity元素通常不是全零配置(同样,只有在 Gamma 是一只狗)。所以找到身份元素是一个有趣的问题。
让 n=|V|-1 并确定非墨水顶点的顺序。让 mathcal{{tilde{{L}}}}subsetZZ^n 表示 tilde{{L}}^t ,约化拉普拉斯的转置。这是一个定理
因此,沙堆组的元素数量为 det{{tilde{{L}}}} ,根据矩阵树定理,它是指向接收器的加权树的数目。
例子。 (续):
sage: S.group_order()
3
sage: S.invariant_factors()
[1, 1, 3]
sage: S.reduced_laplacian().dense_matrix().smith_form()
(
[1 0 0] [ 0 0 1] [3 1 4]
[0 1 0] [ 1 0 0] [4 1 6]
[0 0 3], [ 0 1 -1], [4 1 5]
)
将标识添加到任何循环配置并使其稳定,将生成相同的重复配置:
sage: S.identity()
{1: 3, 2: 1, 3: 0}
sage: i = S.identity()
sage: m = S.max_stable()
sage: i & m == m
True
自组织临界性¶
本文介绍了Bak,Tang,Wiesenfeld提出的沙堆模型, Self-organized criticality: an explanation of 1/ƒ noise [BTW]. 术语 self-organized criticality 没有精确的定义,但是可以粗略地描述一个系统,它自然地演化到几乎不稳定的状态,并且不稳定性用幂律来描述。在实践中, self-organized criticality 通常被认为是 就像网格图上的沙堆模型 . 网格图只是一个具有额外汇点的网格。每边内部的顶点有一条到水槽的边,角点顶点有一条权重边 2 . 因此,每个非墨水顶点都有出度 4 .
想象一下,在一个空的网格图上反复滴下沙子,让沙堆在中间稳定下来。一开始几乎没有活动,但随着时间的推移,由一粒沙子引起的雪崩的规模和程度变得很难预测。计算机实验——我认为还没有证据——表明雪崩大小的分布服从指数为-1的幂律。在下面的例子中,雪崩的大小是每个顶点发射次数的总和。
示例(雪崩大小的分布)。 ::
sage: S = sandpiles.Grid(10,10)
sage: m = S.max_stable()
sage: a = []
sage: for i in range(10000): # long time (15s on sage.math, 2012)
....: m = m.add_random()
....: m, f = m.stabilize(true)
....: a.append(sum(f.values()))
...
sage: p = list_plot([[log(i+1),log(a.count(i))] for i in [0..max(a)] if a.count(i)]) # long time
sage: p.axes_labels(['log(N)','log(D(N))']) # long time
sage: p # long time
Graphics object consisting of 1 graphics primitive
注:在上述代码中, m.stabilize(true)
返回由稳定配置和触发向量组成的列表。(省略 true
只会提供稳定的配置。)
除数与离散黎曼曲面¶
本节的参考是 Riemann-Roch and Abel-Jacobi theory on a finite graph [BN].
A 除数 在 Gamma 是自由交换群在其顶点上的一个元素,包括sink。如上所述,假设 n+1 的顶点 Gamma 已经被命令了,而且 mathcal{{L}} 是拉普拉斯转置的柱距。然后用元素标识除数 DinZZ^{{n+1}} ,两个除数是 线性等价 如果它们不同于 mathcal{{L}} . 除数 E 是 有效的 ,已写入 Egeq0 如果 E(v)geq0 对于每一个 vin V ,即,如果 Einmathbb{{Z}}_{{geq 0}}^{{n+1}} . 这个 度 除数的 D 是 deg(D) := sum_{{vin V}} D(v) . 零次模线性等价的除数构成 皮卡德集团 或 雅可比 图形的。对于无向图,Picard群与sandpile群同构。
这个 完全线性系统 对于除数 D ,表示 |D| ,是有效除数的集合线性等价于 D .
黎曼-罗赫定理¶
为了在这种情况下描述Riemann-Roch定理,假设 Gamma 是一个无向无权图。这个 维 , r(D) ,线性系统的 |D| 是 -1 如果 |D|=emptyset ,否则为最大整数 s 这样的话 |D-E|neq0 所有有效除数 E 程度的 s . 定义 正则除数 通过 K = sum_{{vin V}} (deg(v)-2) v 和 属 通过 g = #(E) - #(V) + 1 . Riemann-Roch定理说对于任何除数 D ,
例子。 ::
sage: G = sandpiles.Complete(5) # the sandpile on the complete graph with 5 vertices
图上的除数:
sage: D = SandpileDivisor(G, [1,2,2,0,2])
验证Riemann-Roch定理:
sage: K = G.canonical_divisor()
sage: D.rank() - (K - D).rank() == D.deg() + 1 - G.genus()
True
有效除数线性等价于 D ::
sage: D.effective_div(False)
[[0, 1, 1, 4, 1], [1, 2, 2, 0, 2], [4, 0, 0, 3, 0]]
线性等价的非特殊除数(度因子 g-1 对于空线性系统):
sage: N = G.nonspecial_divisors()
sage: [E.values() for E in N[:5]] # the first few
[[-1, 0, 1, 2, 3],
[-1, 0, 1, 3, 2],
[-1, 0, 2, 1, 3],
[-1, 0, 2, 3, 1],
[-1, 0, 3, 1, 2]]
sage: len(N)
24
sage: len(N) == G.h_vector()[-1]
True
描绘线性系统¶
修正除数 D . 至少有两个与线性系统相关联的自然图 D . 首先,考虑具有顶点集的有向图 |D| 从顶点开始有一条边 E 到顶点 F 如果 F 是从 E 发射一个不稳定的顶点。:
sage: S = Sandpile(graphs.CycleGraph(6),0)
sage: D = SandpileDivisor(S, [1,1,1,1,2,0])
sage: D.is_alive()
True
sage: eff = D.effective_div()
sage: firing_graph(S,eff).show3d(edge_size=.005,vertex_size=0.01,iterations=500)
这个 is_alive
方法检查除数是否 D 是活的,即每个除数是否线性等价于 D 不稳定。
第二个图有相同的顶点集,但有一条来自 E 到 F 如果 F 是从 E 通过激发所有不稳定的顶点 E . ::
sage: S = Sandpile(graphs.CycleGraph(6),0)
sage: D = SandpileDivisor(S, [1,1,1,1,2,0])
sage: eff = D.effective_div()
sage: parallel_firing_graph(S,eff).show3d(edge_size=.005,vertex_size=0.01,iterations=500)
注意,在上面的每一个例子中,从线性系统中的任何除数开始,然后沿着边,一个最终被引入一个长度循环 6 (循环除数 (1,1,1,1,2,0) ). 因此, D.alive()
收益率 True
. 在Sage中,人们可以旋转上面的数字来更好地了解结构。
沙堆的代数几何¶
仿射的¶
让 n = |V| - 1 ,并在 Gamma . 让 tilde{{mathcal{{L}}}} subset ZZ^n 表示 tilde{{L}}^t ,约化拉普拉斯的转置。标签顶点 i 不确定的 x_i ,让 CC[Gamma_s] = CC[x_1, dots, x_n] . (这里, s 表示的汇顶点 Gamma ) 沙堆理想 或 颠覆理想 ,首先由Cori、Rossin和Salvy研究 [CRS] 对于无向图,格是理想的吗 tilde{{mathcal{{L}}}} :
在哪里? x^u := prod_{{i=1}}^n x^{{u_i}} 对于 u in ZZ^n .
对于每一个 cinZZ^n 定义 t(c) = x^{{c^+}} - x^{{c^-}} 在哪里? c^+_i = max{{c_i,0}} 和 c^-_i = max{{-c_i,0}} ,这样 c = c^+ - c^- . 然后,每个人 sigma in ZZ^n 定义 T(sigma) = t(tilde{{L}}^tsigma) . 结果证明
在哪里? e_i 是 i -标准基向量和 b 任何配置正在烧录。
仿射坐标环, CC[Gamma_s]/I, 与沙堆群的群代数同构, CC[mathcal{{S}}(Gamma)] .
标准术语排序 CC[Gamma_s] 分级反字典序 x_i > x_j 如果顶点 v_i 离水槽比顶点远 v_j . (对于与水槽等距的顶点,可以进行选择。)如果 sigma_b 是烧录配置的脚本(不一定是最小的),那么
是 I .
投射的¶
现在就让 CC[Gamma] = CC[x_0,x_1,dots,x_n] 在哪里 x_0 对应于水槽顶点。这个 均质沙堆理想 ,表示 I^h ,是通过均质获得的 I 关于 x_0 . 让 L 做(完整的)拉普拉斯人,并且 mathcal{{L}} subset ZZ^{{n+1}} 是其转置的柱距, L^t. 然后 I^h 格子是理想的 mathcal{{L}} :
这个理想可以通过饱和理想来计算
对于指数产品: prod_{{i=0}}^n x_i 延长 T 以明显的方式)。与上面描述的度词典序有关的格布纳基(与 x_0 最小顶点)是通过均匀化非齐次沙堆理想的Gröbner基的每个元素得到的 x_0 .
例子。 ::
sage: g = {0:{},1:{0:1,3:1,4:1},2:{0:1,3:1,5:1},
....: 3:{2:1,5:1},4:{1:1,3:1},5:{2:1,3:1}}
sage: S = Sandpile(g, 0)
sage: S.ring()
Multivariate Polynomial Ring in x5, x4, x3, x2, x1, x0 over Rational Field
均质沙堆理想:
sage: S.ideal()
Ideal (x2 - x0, x3^2 - x5*x0, x5*x3 - x0^2, x4^2 - x3*x1, x5^2 - x3*x0,
x1^3 - x4*x3*x0, x4*x1^2 - x5*x0^2) of Multivariate Polynomial Ring
in x5, x4, x3, x2, x1, x0 over Rational Field
理想的创造者:
sage: S.ideal(true)
[x2 - x0,
x3^2 - x5*x0,
x5*x3 - x0^2,
x4^2 - x3*x1,
x5^2 - x3*x0,
x1^3 - x4*x3*x0,
x4*x1^2 - x5*x0^2]
它的分辨率:
sage: S.resolution() # long time
'R^1 <-- R^7 <-- R^19 <-- R^25 <-- R^16 <-- R^4'
和贝蒂表:
sage: S.betti() # long time
0 1 2 3 4 5
------------------------------------------
0: 1 1 - - - -
1: - 4 6 2 - -
2: - 2 7 7 2 -
3: - - 6 16 14 4
------------------------------------------
total: 1 7 19 25 16 4
希尔伯特函数:
sage: S.hilbert_function()
[1, 5, 11, 15]
以及它的第一个区别(它计算每个阶数中的超级稳定配置的数量):
sage: S.h_vector()
[1, 4, 6, 4]
sage: x = [i.deg() for i in S.superstables()]
sage: sorted(x)
[0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3]
希尔伯特函数开始等于希尔伯特多项式的次数,后者在沙堆理想情况下始终是常数:
sage: S.postulation()
3
零点¶
这个 零点设置 为了沙堆的理想 I 是
多项式的同时零点集 I . 出租 S^1 表示复平面上的单位圆, Z(I) 是的有限子群 S^1 times cdots times S^1 subset CC^n ,与沙堆群同构。零点集实际上是线性同构的沙堆群的忠实表示 CC^n .
例子。 (续):
sage: S = Sandpile({0: {}, 1: {2: 2}, 2: {0: 4, 1: 1}}, 0)
sage: S.ideal().gens()
[x1^2 - x2^2, x1*x2^3 - x0^4, x2^5 - x1*x0^4]
接近零集(设置 x_0 = 1
):
sage: S.solve()
[[-0.707107 + 0.707107*I, 0.707107 - 0.707107*I],
[-0.707107 - 0.707107*I, 0.707107 + 0.707107*I],
[-I, -I],
[I, I],
[0.707107 + 0.707107*I, -0.707107 - 0.707107*I],
[0.707107 - 0.707107*I, -0.707107 + 0.707107*I],
[1, 1],
[-1, -1]]
sage: len(_) == S.group_order()
True
零由一个向量作为一组生成:
sage: S.points()
[[(1/2*I + 1/2)*sqrt(2), -(1/2*I + 1/2)*sqrt(2)]]
决议案¶
均质沙堆理想, I^h ,具有按除数分级的自由分辨率 Gamma 模线性等价。(参见 Discrete Riemann Surfaces 对于除数和线性等价的语言)让 S = CC[Gamma] = CC[x_0,dots,x_n] ,如上所述,让 mathfrak{{S}} 表示模有理等价的除数组。那么 S 评分依据 mathfrak{{S}} 通过让 deg(x^c) = c in mathfrak{{S}} 对于每个单项式 x^c . 最小自由分辨率 I^h 有表格吗
何处 beta_{{i,D}} 是 贝蒂数 对于 I^h .
对于每个除数类 Dinmathfrak{{S}} ,定义一个简单的复合体
贝蒂的号码 beta_{{i,D}} 等于维度 CC 的 i -同调群 Delta_D :
sage: S = Sandpile({0:{},1:{0: 1, 2: 1, 3: 4},2:{3: 5},3:{1: 1, 2: 1}},0)
具有非平凡同调的所有除数类的代表:
sage: p = S.betti_complexes()
sage: p[0]
[{0: -8, 1: 5, 2: 4, 3: 1},
Simplicial complex with vertex set (1, 2, 3) and facets {(3,), (1, 2)}]
与列表中第一个除数相关联的同源性:
sage: D = p[0][0]
sage: D.effective_div()
[{0: 0, 1: 0, 2: 0, 3: 2}, {0: 0, 1: 1, 2: 1, 3: 0}]
sage: [E.support() for E in D.effective_div()]
[[3], [1, 2]]
sage: D.Dcomplex()
Simplicial complex with vertex set (1, 2, 3) and facets {(3,), (1, 2)}
sage: D.Dcomplex().homology()
{0: Z, 1: 0}
最小自由分辨率:
sage: S.resolution()
'R^1 <-- R^5 <-- R^5 <-- R^1'
sage: S.betti()
0 1 2 3
------------------------------
0: 1 - - -
1: - 5 5 -
2: - - - 1
------------------------------
total: 1 5 5 1
sage: len(p)
11
列表中每个元素的同调群的度和秩 p
(与上面的Betti表比较):
sage: [[sum(d[0].values()),d[1].betti()] for d in p]
[[2, {0: 2, 1: 0}],
[3, {0: 1, 1: 1, 2: 0}],
[2, {0: 2, 1: 0}],
[3, {0: 1, 1: 1, 2: 0}],
[2, {0: 2, 1: 0}],
[3, {0: 1, 1: 1, 2: 0}],
[2, {0: 2, 1: 0}],
[3, {0: 1, 1: 1}],
[2, {0: 2, 1: 0}],
[3, {0: 1, 1: 1, 2: 0}],
[5, {0: 1, 1: 0, 2: 1}]]
无向图的Betti数¶
去做。
使用¶
初始化¶
Sage中的沙堆结构主要有三类: Sandpile
, SandpileConfig
和 SandpileDivisor
. 的初始化 Sandpile
形式是:
.. skip
sage:S=沙堆(图形、水槽)
在哪里? graph
表示一个图形和 sink
是水槽顶点的关键点。有四种可能的形式 graph
:
Python字典:
sage: g = {0: {}, 1: {0: 1, 3: 1, 4: 1}, 2: {0: 1, 3: 1, 5: 1}, ....: 3: {2: 1, 5: 1}, 4: {1: 1, 3: 1}, 5: {2: 1, 3: 1}}
图来自字典字典。
每个关键点都是顶点的名称。每个顶点名称旁边 v 字典是由对组成的:
vertex: weight
. 每对代表一条从 v 结束于vertex
(非负整数)权重等于weight
. 允许循环。在上面的例子中,所有的权重都是1。Python列表词典:
sage: g = {0: [], 1: [0, 3, 4], 2: [0, 3, 5], ....: 3: [2, 5], 4: [1, 3], 5: [2, 3]}
当所有边权重都等于1时,这是一个速记。以上示例适用于同一个显示的图形。
一个Sage的图形(字体)
sage.graphs.graph.Graph
):sage: g = graphs.CycleGraph(5) sage: S = Sandpile(g, 0) sage: type(g) <class 'sage.graphs.graph.Graph'>
要查看内置图形的类型,请键入
graphs.
,包括句点和点击标签。有向图:
sage: S = Sandpile(digraphs.RandomDirectedGNC(6), 0) sage: S.show()
见 sage.graphs.graph_generators 有关Sage图形库和图形构造函数的更多信息。
这四种格式中的每一种都由Sandpile类进行预处理,因此,在内部,图由首先呈现的字典格式表示。此内部格式由返回 dict()
::
sage: S = Sandpile({0:[], 1:[0, 3, 4], 2:[0, 3, 5], 3: [2, 5], 4: [1, 3], 5: [2, 3]},0)
sage: S.dict()
{0: {},
1: {0: 1, 3: 1, 4: 1},
2: {0: 1, 3: 1, 5: 1},
3: {2: 1, 5: 1},
4: {1: 1, 3: 1},
5: {2: 1, 3: 1}}
注解
用户负责确保每个顶点都有指向指定接收器的路径。如果水槽有外边缘,则在沙堆计算时将忽略这些边(但不计算除数)。
用于检查给定顶点是否为接收器的代码:
sage: S = Sandpile({0:[], 1:[0, 3, 4], 2:[0, 3, 5], 3: [2, 5], 4: [1, 3], 5: [2, 3]},0)
sage: [S.distance(v,0) for v in S.vertices()] # 0 is a sink
[0, 1, 1, 2, 2, 2]
sage: [S.distance(v,1) for v in S.vertices()] # 1 is not a sink
[+Infinity, 0, +Infinity, +Infinity, 1, +Infinity]
方法¶
以下是 Sandpile
, SandpileConfig
和 SandpileDivisor
方法(函数)。每个摘要后面都有一个方法的完整描述列表。对于沙堆还有很多方法可用,例如,从有向图类继承的方法。要查看所有这些,请输入 dir(Sandpile)
或类型 Sandpile.
,包括句点和点击标签。
沙堆¶
方法概述。
all_k_config ---所有值都设置为k的常量配置。
all_k_div ---所有值都设置为k的除数。
avalanche_polynomial ---雪崩多项式。
betti ---理想的倒台。
betti_complexes ---具有非平凡同调的支撑配合物。
burning_config ---最小的燃烧配置。
burning_script ---最小刻录配置的脚本。
canonical_divisor ---标准除数。
dict ---表示有向图的字典。
genus ---亏格:(#非圈边)-(#顶点)+1。
groebner ---齐次倾倒理想的Groebner基础。
group_gens ---沙堆组生成器的最小列表。
group_order ---沙堆群的大小。
h_vector ---每阶超稳定组态的数目。
help ---沙堆特定方法的列表(不是从Graph继承的)。
hilbert_function ---齐次倾倒理想的Hilbert函数。
ideal ---饱和均匀倾倒理想。
identity ---身份配置。
in_degree ---顶点的度数一个顶点的度数或所有度数的列表。
invariant_factors ---沙堆群的不变因子。
is_undirected ---底层图是无向图吗?
jacobian_representatives ---雅可比群元素的代表。
laplacian ---图的拉普拉斯矩阵。
markov_chain ---配置或除数的沙堆马尔可夫链。
max_stable ---最大稳定构型。
max_stable_div ---最大稳定除数。
max_superstables ---最大超稳定构型。
min_recurrents ---最小递归元素。
nonsink_vertices ---非墨水顶点。
nonspecial_divisors ---非特殊除数。
out_degree ---顶点的出度或所有出度的列表。
picard_representatives ---Picard群中d级除数类的代表。
points ---沙堆理想的乘法零点群的生成元。
postulation ---倾倒理想的假设数。
recurrents ---周期性构型。
reduced_laplacian ---图的约化拉普拉斯矩阵。
reorder_vertices ---顶点名称排列的沙堆副本。
resolution ---齐次倾倒理想的最小自由分解。
ring ---包含齐次倾倒理想的环。
show ---绘制底层图形。
show3d ---绘制底层图形。
sink ---水槽顶点。
smith_form ---拉普拉斯算子的史密斯范式。
solve ---沙堆理想复仿射零点的逼近。
stable_configs ---所有稳定配置的发电机。
stationary_density ---沙堆的静止密度。
superstables ---超级稳定的配置。
symmetric_recurrents ---对称递归构型。
tutte_polynomial ---塔特多项式。
unsaturated_ideal ---不饱和均匀倾倒理想。
version ---Sage沙堆的版本号。
zero_config ---全零配置。
zero_div ---全零除数。
完整描述沙堆方法。
---
all_k_config(k)
所有值都设置为的常量配置 k .
输入:
k
--整数
输出:
SandpileConfig
示例:
sage: s = sandpiles.Diamond()
sage: s.all_k_config(7)
{1: 7, 2: 7, 3: 7}
---
all_k_div(k)
所有值都设置为的除数 k .
输入:
k
--整数
输出:
SandpileDivisor
示例:
sage: S = sandpiles.House()
sage: S.all_k_div(7)
{0: 7, 1: 7, 2: 7, 3: 7, 4: 7}
---
avalanche_polynomial(multivariable=True)
雪崩多项式。详见注释。
输入:
multivariable
--(默认值: True
)布尔型
输出:
多项式的
示例:
sage: s = sandpiles.Complete(4)
sage: s.avalanche_polynomial()
9*x0*x1*x2 + 2*x0*x1 + 2*x0*x2 + 2*x1*x2 + 3*x0 + 3*x1 + 3*x2 + 24
sage: s.avalanche_polynomial(False)
9*x0^3 + 6*x0^2 + 9*x0 + 24
注解
对于每个非墨水顶点 v ,让 x_v 不确定。如果 (r,v) 是一对由 r 和非墨水顶点 v ,然后对于每个非墨水顶点 w ,让 n_w 是顶点的次数 w 在稳定 r + v . 让 M(r,v) 做单项 prod_w x_w^{{n_w}} 也就是说,指数记录了 n_w 作为 w 范围覆盖非墨水顶点。雪崩多项式就是 M(r,v) 作为 r 在范围和重复发生 v 范围覆盖非墨水顶点。如果 multivariable
是 False
,然后将所有的索引设置为彼此相等(因此,只计算稳定化中的顶点触发数,而忽略了哪些特定顶点被触发)。
---
betti(verbose=True)
齐次倾倒理想的Betti表。如果 verbose
是 True
,它将打印标准的Betti表,否则,它将返回一个格式较低的表。
输入:
verbose
--(默认值: True
)布尔型
输出:
沙堆的贝蒂数字
示例:
sage: S = sandpiles.Diamond()
sage: S.betti()
0 1 2 3
------------------------------
0: 1 - - -
1: - 2 - -
2: - 4 9 4
------------------------------
total: 1 6 9 4
sage: S.betti(False)
[1, 6, 9, 4]
---
betti_complexes()
具有非平凡同调的支撑配合物。(见注释。)
输出:
(对)列表 [除数,对应的单复数] )
示例:
sage: S = Sandpile({0:{},1:{0: 1, 2: 1, 3: 4},2:{3: 5},3:{1: 1, 2: 1}},0)
sage: p = S.betti_complexes()
sage: p[0]
[{0: -8, 1: 5, 2: 4, 3: 1}, Simplicial complex with vertex set (1, 2, 3) and facets {(3,), (1, 2)}]
sage: S.resolution()
'R^1 <-- R^5 <-- R^5 <-- R^1'
sage: S.betti()
0 1 2 3
------------------------------
0: 1 - - -
1: - 5 5 -
2: - - - 1
------------------------------
total: 1 5 5 1
sage: len(p)
11
sage: p[0][1].homology()
{0: Z, 1: 0}
sage: p[-1][1].homology()
{0: 0, 1: 0, 2: Z}
注解
A support-complex
是由线性系统中除数的支撑而形成的简单复形。
---
burning_config()
最小的燃烧配置。
输出:
dict(配置)
示例:
sage: g = {0:{},1:{0:1,3:1,4:1},2:{0:1,3:1,5:1}, \
3:{2:1,5:1},4:{1:1,3:1},5:{2:1,3:1}}
sage: S = Sandpile(g,0)
sage: S.burning_config()
{1: 2, 2: 0, 3: 1, 4: 1, 5: 0}
sage: S.burning_config().values()
[2, 0, 1, 1, 0]
sage: S.burning_script()
{1: 1, 2: 3, 3: 5, 4: 1, 5: 4}
sage: script = S.burning_script().values()
sage: script
[1, 3, 5, 1, 4]
sage: matrix(script)*S.reduced_laplacian()
[2 0 1 1 0]
注解
烧录配置和脚本是使用Speer的脚本算法的修改版本来计算的。这是对Dhar燃烧算法的有向多重图的推广。
A 燃烧配置 是一个非负整数线性组合的行约化拉普拉斯矩阵具有非负项,因此每个顶点都有一条从某个顶点支持的路径。对应的 烧录脚本 给出获得燃烧配置所需的整数线性组合。所以如果 b 是燃烧配置, sigma 是它的剧本,而且 tilde{{L}} 是约化拉普拉斯吗 sigmacdot tilde{{L}} = b . 这个 最小燃烧配置 是具有最小脚本的那个(它的组件不大于任何其他用于刻录配置的脚本的组件)。
以下是配置的等效项 c 带燃烧配置 b 有剧本的 sigma :
c 反复发作;
c+b 稳定到 c ;
稳定的点火矢量 c+b 是 sigma .
---
burning_script()
最小刻录配置的脚本。
输出:
双关语
示例:
sage: g = {0:{},1:{0:1,3:1,4:1},2:{0:1,3:1,5:1},\
3:{2:1,5:1},4:{1:1,3:1},5:{2:1,3:1}}
sage: S = Sandpile(g,0)
sage: S.burning_config()
{1: 2, 2: 0, 3: 1, 4: 1, 5: 0}
sage: S.burning_config().values()
[2, 0, 1, 1, 0]
sage: S.burning_script()
{1: 1, 2: 3, 3: 5, 4: 1, 5: 4}
sage: script = S.burning_script().values()
sage: script
[1, 3, 5, 1, 4]
sage: matrix(script)*S.reduced_laplacian()
[2 0 1 1 0]
注解
烧录配置和脚本是使用Speer的脚本算法的修改版本来计算的。这是对Dhar燃烧算法的有向多重图的推广。
A 燃烧配置 是一个非负整数线性组合的行约化拉普拉斯矩阵具有非负项,因此每个顶点都有一条从某个顶点支持的路径。对应的 烧录脚本 给出获得燃烧配置所需的整数线性组合。所以如果 b 是燃烧配置, s 是它的剧本,而且 L_{{mathrm{{red}}}} 是约化拉普拉斯吗 scdot L_{{mathrm{{red}}}}= b . 这个 最小燃烧配置 是具有最小脚本的那个(它的组件不大于任何其他用于刻录配置的脚本的组件)。
以下是配置的等效项 c 带燃烧配置 b 有剧本的 s :
c 反复发作;
c+b 稳定到 c ;
稳定的点火矢量 c+b 是 s .
---
canonical_divisor()
标准除数。这是除数 deg(v)-2 每个顶点上的沙粒(不计算循环)。只适用于无向图。
输出:
SandpileDivisor
示例:
sage: S = sandpiles.Complete(4)
sage: S.canonical_divisor()
{0: 1, 1: 1, 2: 1, 3: 1}
sage: s = Sandpile({0:[1,1],1:[0,0,1,1,1]},0)
sage: s.canonical_divisor() # loops are disregarded
{0: 0, 1: 0}
警告
基础图形必须是无向的。
---
()
表示有向图的字典。
输出:
双关语
示例:
sage: S = sandpiles.Diamond()
sage: S.dict()
{0: {1: 1, 2: 1},
1: {0: 1, 2: 1, 3: 1},
2: {0: 1, 1: 1, 3: 1},
3: {1: 1, 2: 1}}
sage: S.sink()
0
---
属()
亏格:(#非圈边)-(#顶点)+1。只为无向图定义。
输出:
整数
示例:
sage: sandpiles.Complete(4).genus()
3
sage: sandpiles.Cycle(5).genus()
1
---
格罗布纳()
齐次倾倒理想的Groebner基础。根据标准沙堆顺序计算(参见 ring
)
输出:
格鲁布纳基
示例:
sage: S = sandpiles.Diamond()
sage: S.groebner()
[x3*x2^2 - x1^2*x0, x2^3 - x3*x1*x0, x3*x1^2 - x2^2*x0, x1^3 - x3*x2*x0, x3^2 - x0^2, x2*x1 - x0^2]
---
group_gens(verbose=True)
沙堆组生成器的最小列表。如果 verbose
是 False
然后将生成器表示为整数列表。
输入:
verbose
--(默认值: True
)布尔型
输出:
SandpileConfig列表(如果 verbose
是 False
)
示例:
sage: s = sandpiles.Cycle(5)
sage: s.group_gens()
[{1: 1, 2: 1, 3: 1, 4: 0}]
sage: s.group_gens()[0].order()
5
sage: s = sandpiles.Complete(5)
sage: s.group_gens(False)
[[2, 2, 3, 2], [2, 3, 2, 2], [3, 2, 2, 2]]
sage: [i.order() for i in s.group_gens()]
[5, 5, 5]
sage: s.invariant_factors()
[1, 5, 5, 5]
---
group_order()
沙堆群的大小。
输出:
整数
示例:
sage: S = sandpiles.House()
sage: S.group_order()
11
---
h_vector()
每阶超稳定组态的数目。等价地,这是(齐次)倒理想的Hilbert函数的第一个差分列表。
输出:
非负整数列表
示例:
sage: s = sandpiles.Grid(2,2)
sage: s.hilbert_function()
[1, 5, 15, 35, 66, 106, 146, 178, 192]
sage: s.h_vector()
[1, 4, 10, 20, 31, 40, 40, 32, 14]
---
help(verbose=True)
沙堆特定方法的列表(不是从Graph继承的)。如果 verbose
,包括简短描述。
输入:
verbose
--(默认值: True
)布尔型
输出:
打印字符串
示例:
sage: Sandpile.help()
For detailed help with any method FOO listed below,
enter "Sandpile.FOO?" or enter "S.FOO?" for any Sandpile S.
<BLANKLINE>
all_k_config -- The constant configuration with all values set to k.
all_k_div -- The divisor with all values set to k.
avalanche_polynomial -- The avalanche polynomial.
betti -- The Betti table for the homogeneous toppling ideal.
betti_complexes -- The support-complexes with non-trivial homology.
burning_config -- The minimal burning configuration.
burning_script -- A script for the minimal burning configuration.
canonical_divisor -- The canonical divisor.
dict -- A dictionary of dictionaries representing a directed graph.
genus -- The genus: (# non-loop edges) - (# vertices) + 1.
groebner -- A Groebner basis for the homogeneous toppling ideal.
group_gens -- A minimal list of generators for the sandpile group.
group_order -- The size of the sandpile group.
h_vector -- The number of superstable configurations in each degree.
help -- List of Sandpile-specific methods (not inherited from "Graph").
hilbert_function -- The Hilbert function of the homogeneous toppling ideal.
ideal -- The saturated homogeneous toppling ideal.
identity -- The identity configuration.
in_degree -- The in-degree of a vertex or a list of all in-degrees.
invariant_factors -- The invariant factors of the sandpile group.
is_undirected -- Is the underlying graph undirected?
jacobian_representatives -- Representatives for the elements of the Jacobian group.
laplacian -- The Laplacian matrix of the graph.
markov_chain -- The sandpile Markov chain for configurations or divisors.
max_stable -- The maximal stable configuration.
max_stable_div -- The maximal stable divisor.
max_superstables -- The maximal superstable configurations.
min_recurrents -- The minimal recurrent elements.
nonsink_vertices -- The nonsink vertices.
nonspecial_divisors -- The nonspecial divisors.
out_degree -- The out-degree of a vertex or a list of all out-degrees.
picard_representatives -- Representatives of the divisor classes of degree d in the Picard group.
points -- Generators for the multiplicative group of zeros of the sandpile ideal.
postulation -- The postulation number of the toppling ideal.
recurrents -- The recurrent configurations.
reduced_laplacian -- The reduced Laplacian matrix of the graph.
reorder_vertices -- A copy of the sandpile with vertex names permuted.
resolution -- A minimal free resolution of the homogeneous toppling ideal.
ring -- The ring containing the homogeneous toppling ideal.
show -- Draw the underlying graph.
show3d -- Draw the underlying graph.
sink -- The sink vertex.
smith_form -- The Smith normal form for the Laplacian.
solve -- Approximations of the complex affine zeros of the sandpile ideal.
stable_configs -- Generator for all stable configurations.
stationary_density -- The stationary density of the sandpile.
superstables -- The superstable configurations.
symmetric_recurrents -- The symmetric recurrent configurations.
tutte_polynomial -- The Tutte polynomial of the underlying graph.
unsaturated_ideal -- The unsaturated, homogeneous toppling ideal.
version -- The version number of Sage Sandpiles.
zero_config -- The all-zero configuration.
zero_div -- The all-zero divisor.
---
hilbert_function()
齐次倾倒理想的Hilbert函数。
输出:
非负整数列表
示例:
sage: s = sandpiles.Wheel(5)
sage: s.hilbert_function()
[1, 5, 15, 31, 45]
sage: s.h_vector()
[1, 4, 10, 16, 14]
---
ideal(gens=False)
饱和均匀倾倒理想。如果 gens
是 True
,则返回理想的生成器。
输入:
gens
--(默认值: False
)布尔型
输出:
理想的,或者是理想的生成者
示例:
sage: S = sandpiles.Diamond()
sage: S.ideal()
Ideal (x2*x1 - x0^2, x3^2 - x0^2, x1^3 - x3*x2*x0, x3*x1^2 - x2^2*x0, x2^3 - x3*x1*x0, x3*x2^2 - x1^2*x0) of Multivariate Polynomial Ring in x3, x2, x1, x0 over Rational Field
sage: S.ideal(True)
[x2*x1 - x0^2, x3^2 - x0^2, x1^3 - x3*x2*x0, x3*x1^2 - x2^2*x0, x2^3 - x3*x1*x0, x3*x2^2 - x1^2*x0]
sage: S.ideal().gens() # another way to get the generators
[x2*x1 - x0^2, x3^2 - x0^2, x1^3 - x3*x2*x0, x3*x1^2 - x2^2*x0, x2^3 - x3*x1*x0, x3*x2^2 - x1^2*x0]
---
identity(verbose=True)
身份配置。如果 verbose
是 False
,配置将转换为整数列表。
输入:
verbose
--(默认值: True
)布尔型
输出:
如果 verbose
是 False
,配置将转换为整数列表。
示例:
sage: s = sandpiles.Diamond()
sage: s.identity()
{1: 2, 2: 2, 3: 0}
sage: s.identity(False)
[2, 2, 0]
sage: s.identity() & s.max_stable() == s.max_stable()
True
---
in_degree(v=None)
顶点的度数一个顶点的度数或所有度数的列表。
输入:
v
--(可选)顶点名称
输出:
整数或dict
示例:
sage: s = sandpiles.House()
sage: s.in_degree()
{0: 2, 1: 2, 2: 3, 3: 3, 4: 2}
sage: s.in_degree(2)
3
---
invariant_factors()
沙堆群的不变因子。
输出:
整数列表
示例:
sage: s = sandpiles.Grid(2,2)
sage: s.invariant_factors()
[1, 1, 8, 24]
---
is_undirected()
底层图是无向图吗? True
如果 (u,v) 当且仅当且仅当 (v,u) 是一个边,每个边都有相同的权重。
输出:
布尔
示例:
sage: sandpiles.Complete(4).is_undirected()
True
sage: s = Sandpile({0:[1,2], 1:[0,2], 2:[0]}, 0)
sage: s.is_undirected()
False
---
jacobian_representatives(verbose=True)
雅可比群元素的代表。如果 verbose
是 False
,然后返回表示除数的列表。
输入:
verbose
--(默认值: True
)布尔型
输出:
沙盘列表(或表示除数的列表)
示例:
对于无向图,形式的除数 s - deg(s)*sink
作为 s
不同的超级表构成了雅各比群的一组不同的代表:
sage: s = sandpiles.Complete(3)
sage: s.superstables(False)
[[0, 0], [0, 1], [1, 0]]
sage: s.jacobian_representatives(False)
[[0, 0, 0], [-1, 0, 1], [-1, 1, 0]]
如果图是有向图的,则上面描述的代表可以用拉普拉斯矩阵的行跨度的等价模来表示:
sage: s = Sandpile({0: {1: 1, 2: 2}, 1: {0: 2, 2: 4}, 2: {0: 4, 1: 2}},0)
sage: s.group_order()
28
sage: s.jacobian_representatives()
[{0: -5, 1: 3, 2: 2}, {0: -4, 1: 3, 2: 1}]
让 tau 是拉普拉斯转置核的非负生成器,并且让 tau_s 如果是下沉分量,则沙堆群同构于阶循环群的直和 tau_s 雅各比群。在上面的例子中,我们有:
sage: s.laplacian().left_kernel()
Free module of degree 3 and rank 1 over Integer Ring
Echelon basis matrix:
[14 5 8]
注解
雅可比群是拉普拉斯矩阵的整数行跨度的零次模的所有除数的集合。
---
拉普拉斯()
图的拉普拉斯矩阵。它 rows 编码顶点触发规则。
输出:
矩阵
示例:
sage: G = sandpiles.Diamond()
sage: G.laplacian()
[ 2 -1 -1 0]
[-1 3 -1 -1]
[-1 -1 3 -1]
[ 0 -1 -1 2]
警告
函数 laplacian_matrix
应该避免。它返回拉普拉斯算子的独立版本。
---
markov_chain(state, distrib=None)
配置或除数的沙堆马尔可夫链。链条开始于 state
. 详见注释。
输入:
state
--SandpileConfig、SandPileVisor或代表其中一个的列表distrib
--(可选)总和为1的非负数列表(表示一个问题)。距离)
输出:
马尔可夫链生成器(见注释)
示例:
sage: s = sandpiles.Complete(4)
sage: m = s.markov_chain([0,0,0])
sage: next(m) # random
{1: 0, 2: 0, 3: 0}
sage: next(m).values() # random
[0, 0, 0]
sage: next(m).values() # random
[0, 0, 0]
sage: next(m).values() # random
[0, 0, 0]
sage: next(m).values() # random
[0, 1, 0]
sage: next(m).values() # random
[0, 2, 0]
sage: next(m).values() # random
[0, 2, 1]
sage: next(m).values() # random
[1, 2, 1]
sage: next(m).values() # random
[2, 2, 1]
sage: m = s.markov_chain(s.zero_div(), [0.1,0.1,0.1,0.7])
sage: next(m).values() # random
[0, 0, 0, 1]
sage: next(m).values() # random
[0, 0, 1, 1]
sage: next(m).values() # random
[0, 0, 1, 2]
sage: next(m).values() # random
[1, 1, 2, 0]
sage: next(m).values() # random
[1, 1, 2, 1]
sage: next(m).values() # random
[1, 1, 2, 2]
sage: next(m).values() # random
[1, 1, 2, 3]
sage: next(m).values() # random
[1, 1, 2, 4]
sage: next(m).values() # random
[1, 1, 3, 4]
注解
这个 closed sandpile Markov chain
具有由沙堆上的配置组成的状态空间。它通过随机选择一个顶点(根据概率分布)从状态转换 distrib
)在那个顶点撒一粒沙子,然后稳定下来。如果“顶点”处于选定状态,则链将保持在当前状态。
这个 open sandpile Markov chain
具有由循环元素组成的状态空间,即状态空间是沙堆群。它从配置过渡 c 通过选择顶点 v 根据 distrib
. 下一个状态是稳定 c+v . 如果 v 是下沉顶点,然后稳定 c+v 定义为 c .
请注意,无论哪种情况,如果 distrib
则其长度等于顶点总数(包括水槽)。
参考文献:
- Levine2014(1,2)
莱昂内尔·莱文。阈态与波哥扬的一个猜想,波哥扬,普列兹耶夫和鲁埃尔,数理通信。 :arxiv:`1402.3283`
---
max_stable()
最大稳定构型。
输出:
沙堆(最大稳定配置)
示例:
sage: S = sandpiles.House()
sage: S.max_stable()
{1: 1, 2: 2, 3: 2, 4: 1}
---
max_stable_div()
最大稳定除数。
输出:
最大稳定因子
示例:
sage: s = sandpiles.Diamond()
sage: s.max_stable_div()
{0: 1, 1: 2, 2: 2, 3: 1}
sage: s.out_degree()
{0: 2, 1: 3, 2: 3, 3: 2}
---
max_superstables(verbose=True)
最大超稳定构型。如果底层图是无向图,则这些是最高阶的超表。如果 verbose
是 False
,配置将转换为整数列表。
输入:
verbose
--(默认值: True
)布尔型
输出:
沙堆元组
示例:
sage: s = sandpiles.Diamond()
sage: s.superstables(False)
[[0, 0, 0],
[0, 0, 1],
[1, 0, 1],
[0, 2, 0],
[2, 0, 0],
[0, 1, 1],
[1, 0, 0],
[0, 1, 0]]
sage: s.max_superstables(False)
[[1, 0, 1], [0, 2, 0], [2, 0, 0], [0, 1, 1]]
sage: s.h_vector()
[1, 3, 4]
---
min_recurrents(verbose=True)
最小递归元素。如果底层图是无向的,则这些是最小次数的递归元素。如果 verbose
是 False
,配置将转换为整数列表。
输入:
verbose
--(默认值: True
)布尔型
输出:
沙堆一览表
示例:
sage: s = sandpiles.Diamond()
sage: s.recurrents(False)
[[2, 2, 1],
[2, 2, 0],
[1, 2, 0],
[2, 0, 1],
[0, 2, 1],
[2, 1, 0],
[1, 2, 1],
[2, 1, 1]]
sage: s.min_recurrents(False)
[[1, 2, 0], [2, 0, 1], [0, 2, 1], [2, 1, 0]]
sage: [i.deg() for i in s.recurrents()]
[5, 4, 3, 3, 3, 3, 4, 4]
---
nonsink_vertices()
非墨水顶点。
输出:
顶点列表
示例:
sage: s = sandpiles.Grid(2,3)
sage: s.nonsink_vertices()
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)]
---
nonspecial_divisors(verbose=True)
非特殊除数。只适用于无向图。(见注释。)
输入:
verbose
--(默认值: True
)布尔型
输出:
(除数)列表
示例:
sage: S = sandpiles.Complete(4)
sage: ns = S.nonspecial_divisors()
sage: D = ns[0]
sage: D.values()
[-1, 0, 1, 2]
sage: D.deg()
2
sage: [i.effective_div() for i in ns]
[[], [], [], [], [], []]
注解
“非特殊除数”是指程度的除数 g-1 空线性系统。这个术语只为无向图定义。在这里, g = |E| - |V| + 1 是图的属(不计算循环作为 |E| )如果 verbose
是 False
,则将除数转换为整数列表。
警告
基础图形必须是无向的。
---
out_degree(v=None)
顶点的出度或所有出度的列表。
输入:
v
-(可选)顶点名称
输出:
整数或dict
示例:
sage: s = sandpiles.House()
sage: s.out_degree()
{0: 2, 1: 2, 2: 3, 3: 3, 4: 2}
sage: s.out_degree(2)
3
---
picard_representatives(d, verbose=True)
学位除数等级的代表 d 在皮卡德集团。(另请参阅文档 jacobian_representatives
)
输入:
d
--整数verbose
--(默认值:True
)布尔型
输出:
沙堆编辑器列表(或表示除数的列表)
示例:
sage: s = sandpiles.Complete(3)
sage: s.superstables(False)
[[0, 0], [0, 1], [1, 0]]
sage: s.jacobian_representatives(False)
[[0, 0, 0], [-1, 0, 1], [-1, 1, 0]]
sage: s.picard_representatives(3,False)
[[3, 0, 0], [2, 0, 1], [2, 1, 0]]
---
点()
沙堆理想的乘法零点群的生成元。
输出:
复数列表
示例:
本例中的沙堆群是循环的,因此解组只有一个生成器。
sage: S = sandpiles.Complete(4)
sage: S.points()
[[1, I, -I], [I, 1, -I]]
---
假设()
倾倒理想的假设数。这是图的一个超稳定配置的最大权重。
输出:
非负整数
示例:
sage: s = sandpiles.Complete(4)
sage: s.postulation()
3
---
recurrents(verbose=True)
周期性构型。如果 verbose
是 False
,配置将转换为整数列表。
输入:
verbose
--(默认值: True
)布尔型
输出:
重复配置列表
示例:
sage: r = Sandpile(graphs.HouseXGraph(),0).recurrents()
sage: r[:3]
[{1: 2, 2: 3, 3: 3, 4: 1}, {1: 1, 2: 3, 3: 3, 4: 0}, {1: 1, 2: 3, 3: 3, 4: 1}]
sage: sandpiles.Complete(4).recurrents(False)
[[2, 2, 2],
[2, 2, 1],
[2, 1, 2],
[1, 2, 2],
[2, 2, 0],
[2, 0, 2],
[0, 2, 2],
[2, 1, 1],
[1, 2, 1],
[1, 1, 2],
[2, 1, 0],
[2, 0, 1],
[1, 2, 0],
[1, 0, 2],
[0, 2, 1],
[0, 1, 2]]
sage: sandpiles.Cycle(4).recurrents(False)
[[1, 1, 1], [0, 1, 1], [1, 0, 1], [1, 1, 0]]
---
reduced_laplacian()
图的约化拉普拉斯矩阵。
输出:
矩阵
示例:
sage: S = sandpiles.Diamond()
sage: S.laplacian()
[ 2 -1 -1 0]
[-1 3 -1 -1]
[-1 -1 3 -1]
[ 0 -1 -1 2]
sage: S.reduced_laplacian()
[ 3 -1 -1]
[-1 3 -1]
[-1 -1 2]
注解
这是拉普拉斯矩阵,行和列的索引被删除了。
---
reorder_vertices()
顶点名称排列的沙堆副本。重新排序后,顶点 u 在顶点之前 v 在顶点列表中如果 u 离水槽更近。
输出:
沙堆
示例:
sage: S = Sandpile({0:[1], 2:[0,1], 1:[2]})
sage: S.dict()
{0: {1: 1}, 1: {2: 1}, 2: {0: 1, 1: 1}}
sage: T = S.reorder_vertices()
顶点1和2已交换:
sage: T.dict()
{0: {1: 1}, 1: {0: 1, 2: 1}, 2: {0: 1}}
---
resolution(verbose=False)
齐次倾倒理想的最小自由分解。如果 verbose
是 True
,则返回所有映射。否则,总结决议。
输入:
verbose
--(默认值: False
)布尔型
输出:
颠覆理想的自由分解
示例:
sage: S = Sandpile({0: {}, 1: {0: 1, 2: 1, 3: 4}, 2: {3: 5}, 3: {1: 1, 2: 1}},0)
sage: S.resolution() # a Gorenstein sandpile graph
'R^1 <-- R^5 <-- R^5 <-- R^1'
sage: S.resolution(True)
[
[ x1^2 - x3*x0 x3*x1 - x2*x0 x3^2 - x2*x1 x2*x3 - x0^2 x2^2 - x1*x0],
<BLANKLINE>
[ x3 x2 0 x0 0] [ x2^2 - x1*x0]
[-x1 -x3 x2 0 -x0] [-x2*x3 + x0^2]
[ x0 x1 0 x2 0] [-x3^2 + x2*x1]
[ 0 0 -x1 -x3 x2] [x3*x1 - x2*x0]
[ 0 0 x0 x1 -x3], [ x1^2 - x3*x0]
]
sage: r = S.resolution(True)
sage: r[0]*r[1]
[0 0 0 0 0]
sage: r[1]*r[2]
[0]
[0]
[0]
[0]
[0]
---
响铃()
包含齐次倾倒理想的环。
输出:
环
示例:
sage: S = sandpiles.Diamond()
sage: S.ring()
Multivariate Polynomial Ring in x3, x2, x1, x0 over Rational Field
sage: S.ring().gens()
(x3, x2, x1, x0)
注解
不确定的 xi
对应于 i -这个顶点如我所列的方法 vertices
. 术语排序是degrevlex,索引器根据它们与sink的距离排序(较大的索引器离sink越远)。
---
显示( 科威特第纳尔)**
绘制底层图形。
输入:
kwds
--(可选)传递给Graph或有向图的show方法的参数
示例:
sage: S = Sandpile({0:[], 1:[0,3,4], 2:[0,3,5], 3:[2,5], 4:[1,1], 5:[2,4]})
sage: S.show()
sage: S.show(graph_border=True, edge_labels=True)
---
显示3D( 科威特第纳尔)**
绘制底层图形。
输入:
kwds
--(可选)传递给Graph或有向图的show方法的参数
示例:
sage: S = sandpiles.House()
sage: S.show3d()
---
接收器()
水槽顶点。
输出:
下沉顶点
示例:
sage: G = sandpiles.House()
sage: G.sink()
0
sage: H = sandpiles.Grid(2,2)
sage: H.sink()
(0, 0)
sage: type(H.sink())
<... 'tuple'>
---
smith_form()
拉普拉斯算子的史密斯范式。详细说明:整数矩阵列表 D, U, V 这样的话 ULV = D 在哪里? L 拉皮斯转座, D 是对角线,并且 U 和 V 在整数上是可逆的。
输出:
整数矩阵列表
示例:
sage: s = sandpiles.Complete(4)
sage: D,U,V = s.smith_form()
sage: D
[1 0 0 0]
[0 4 0 0]
[0 0 4 0]
[0 0 0 0]
sage: U*s.laplacian()*V == D # laplacian symmetric => transpose not necessary
True
---
求解()
沙堆理想复仿射零点的逼近。
输出:
复数列表
示例:
sage: S = Sandpile({0: {}, 1: {2: 2}, 2: {0: 4, 1: 1}}, 0)
sage: S.solve()
[[-0.707107 + 0.707107*I, 0.707107 - 0.707107*I], [-0.707107 - 0.707107*I, 0.707107 + 0.707107*I], [-I, -I], [I, I], [0.707107 + 0.707107*I, -0.707107 - 0.707107*I], [0.707107 - 0.707107*I, -0.707107 + 0.707107*I], [1, 1], [-1, -1]]
sage: len(_)
8
sage: S.group_order()
8
注解
这些解形成了一个与沙堆群同构的乘法群。此组的生成器由 points()
.
---
stable_configs(smax=None)
所有稳定配置的发电机。如果 smax
则发电机给出所有小于或等于的稳定配置 smax
. 如果 smax
不代表稳定的配置,则 smax
被最大稳定构型的相应分量所代替。
输入:
smax
--(可选)SandpileConfig或表示SandpileConfig的列表
输出:
所有稳定配置的发电机
示例:
sage: s = sandpiles.Complete(3)
sage: a = s.stable_configs()
sage: next(a)
{1: 0, 2: 0}
sage: [i.values() for i in a]
[[0, 1], [1, 0], [1, 1]]
sage: b = s.stable_configs([1,0])
sage: list(b)
[{1: 0, 2: 0}, {1: 1, 2: 0}]
---
stationary_density()
沙堆的静止密度。
输出:
有理数
示例:
sage: s = sandpiles.Complete(3)
sage: s.stationary_density()
10/9
sage: s = Sandpile(digraphs.DeBruijn(2,2),'00')
sage: s.stationary_density()
9/8
注解
沙堆的静止密度是总和 sum_c (deg(c) + deg(s)) 在哪里? deg(s) 是下沉的程度,和是所有循环配置的总和。
参考文献:
---
superstables(verbose=True)
超级稳定的配置。如果 verbose
是 False
,配置将转换为整数列表。超表也被称为无向图 G-parking functions
.
输入:
verbose
--(默认值: True
)布尔型
输出:
沙堆一览表
示例:
sage: sp = Sandpile(graphs.HouseXGraph(),0).superstables()
sage: sp[:3]
[{1: 0, 2: 0, 3: 0, 4: 0}, {1: 1, 2: 0, 3: 0, 4: 1}, {1: 1, 2: 0, 3: 0, 4: 0}]
sage: sandpiles.Complete(4).superstables(False)
[[0, 0, 0],
[0, 0, 1],
[0, 1, 0],
[1, 0, 0],
[0, 0, 2],
[0, 2, 0],
[2, 0, 0],
[0, 1, 1],
[1, 0, 1],
[1, 1, 0],
[0, 1, 2],
[0, 2, 1],
[1, 0, 2],
[1, 2, 0],
[2, 0, 1],
[2, 1, 0]]
sage: sandpiles.Cycle(4).superstables(False)
[[0, 0, 0], [1, 0, 0], [0, 1, 0], [0, 0, 1]]
---
symmetric_recurrents(orbits)
对称递归构型。
输入:
orbits
-划分顶点的列表列表
输出:
重复配置列表
示例:
sage: S = Sandpile({0: {},
....: 1: {0: 1, 2: 1, 3: 1},
....: 2: {1: 1, 3: 1, 4: 1},
....: 3: {1: 1, 2: 1, 4: 1},
....: 4: {2: 1, 3: 1}})
sage: S.symmetric_recurrents([[1],[2,3],[4]])
[{1: 2, 2: 2, 3: 2, 4: 1}, {1: 2, 2: 2, 3: 2, 4: 0}]
sage: S.recurrents()
[{1: 2, 2: 2, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 2, 4: 0},
{1: 2, 2: 1, 3: 2, 4: 0},
{1: 2, 2: 2, 3: 0, 4: 1},
{1: 2, 2: 0, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 1, 4: 0},
{1: 2, 2: 1, 3: 2, 4: 1},
{1: 2, 2: 2, 3: 1, 4: 1}]
注解
用户负责确保轨道列表来自底层图的一组对称性。
---
tutte_polynomial()
底层图的Tutte多项式。只为无向沙堆图定义。
输出:
多项式的
示例:
sage: s = sandpiles.Complete(4)
sage: s.tutte_polynomial()
x^3 + y^3 + 3*x^2 + 4*x*y + 3*y^2 + 2*x + 2*y
sage: s.tutte_polynomial().subs(x=1)
y^3 + 3*y^2 + 6*y + 6
sage: s.tutte_polynomial().subs(x=1).coefficients() == s.h_vector()
True
---
unsaturated_ideal()
不饱和均匀倾倒理想。
输出:
理想的
示例:
sage: S = sandpiles.Diamond()
sage: S.unsaturated_ideal().gens()
[x1^3 - x3*x2*x0, x2^3 - x3*x1*x0, x3^2 - x2*x1]
sage: S.ideal().gens()
[x2*x1 - x0^2, x3^2 - x0^2, x1^3 - x3*x2*x0, x3*x1^2 - x2^2*x0, x2^3 - x3*x1*x0, x3*x2^2 - x1^2*x0]
---
版本()
Sage沙堆的版本号。
输出:
一串
示例:
sage: Sandpile.version()
Sage Sandpiles Version 2.4
sage: S = sandpiles.Complete(3)
sage: S.version()
Sage Sandpiles Version 2.4
---
zero_config()
全零配置。
输出:
SandpileConfig
示例:
sage: s = sandpiles.Diamond()
sage: s.zero_config()
{1: 0, 2: 0, 3: 0}
---
zero_div()
全零除数。
输出:
SandpileDivisor
示例:
sage: S = sandpiles.House()
sage: S.zero_div()
{0: 0, 1: 0, 2: 0, 3: 0, 4: 0}
---
SandpileConfig¶
方法概述。
+ ---添加配置。
& ---总和的稳定。
greater-equal ---
True
如果self
至少是other
.greater ---
True
如果self
至少是other
两种构型是不相等的。~ ---稳定的配置。
less-equal ---
True
如果self
最多是other
.less ---
True
如果self
最多是other
两种构型是不相等的。* ---与和相等的循环元素。
^ ---的指数 * -操作员。
- ---配置的加法逆。
- ---配置减法。
add_random ---向随机顶点添加一粒沙子。
burst_size ---配置相对于给定顶点的突发大小。
deg ---配置的程度。
dualize ---与最大稳定构型的差异。
equivalent_recurrent ---与给定配置等价的循环配置。
equivalent_superstable ---等效的超稳定配置。
fire_script ---启动给定脚本。
fire_unstable ---激发所有不稳定的顶点。
fire_vertex ---激发给定顶点。
help ---SandpileConfig方法列表。
is_recurrent ---配置是否重复?
is_stable ---配置是否稳定?
is_superstable ---配置是否超稳定?
is_symmetric ---配置是否对称?
order ---等价递归元的阶。
sandpile ---沙堆下面的结构。
show ---显示配置。
stabilize ---稳定的配置。
support ---包含沙子的顶点。
unstable ---不稳定的顶点。
values ---以列表形式显示配置的值。
完整描述沙堆方法。
---
+
添加配置。
输入:
other
--沙堆输出:
总和
self
和other
示例:
sage: S = sandpiles.Cycle(3) sage: c = SandpileConfig(S, [1,2]) sage: d = SandpileConfig(S, [3,2]) sage: c + d {1: 4, 2: 4}
---
&
总和的稳定。
输入:
other
--沙堆输出:
SandpileConfig
示例:
sage: S = sandpiles.Cycle(4) sage: c = SandpileConfig(S, [1,0,0]) sage: c + c # ordinary addition {1: 2, 2: 0, 3: 0} sage: c & c # add and stabilize {1: 0, 2: 1, 3: 0} sage: c*c # add and find equivalent recurrent {1: 1, 2: 1, 3: 1} sage: ~(c + c) == c & c True
---
>=
True
如果self
至少是other
.输入:
other
--沙堆输出:
布尔
示例:
sage: S = sandpiles.Cycle(3) sage: c = SandpileConfig(S, [1,2]) sage: d = SandpileConfig(S, [2,3]) sage: e = SandpileConfig(S, [2,0]) sage: c >= c True sage: d >= c True sage: c >= d False sage: e >= c False sage: c >= e False
---
>
True
如果self
至少是other
两种构型是不相等的。输入:
other
--沙堆输出:
布尔
示例:
sage: S = sandpiles.Cycle(3) sage: c = SandpileConfig(S, [1,2]) sage: d = SandpileConfig(S, [1,3]) sage: c > c False sage: d > c True sage: c > d False
---
~
稳定的配置。
输出:
SandpileConfig
示例:
sage: S = sandpiles.House() sage: c = S.max_stable() + S.identity() sage: ~c == c.stabilize() True
---
<=
True
如果self
最多是other
.输入:
other
--沙堆输出:
布尔
示例:
sage: S = sandpiles.Cycle(3) sage: c = SandpileConfig(S, [1,2]) sage: d = SandpileConfig(S, [2,3]) sage: e = SandpileConfig(S, [2,0]) sage: c <= c True sage: c <= d True sage: d <= c False sage: c <= e False sage: e <= c False
---
<
True
如果self
最多是other
两种构型是不相等的。输入:
other
--沙堆输出:
布尔
示例:
sage: S = sandpiles.Cycle(3) sage: c = SandpileConfig(S, [1,2]) sage: d = SandpileConfig(S, [2,3]) sage: c < c False sage: c < d True sage: d < c False sage: S = Sandpile(graphs.CycleGraph(3), 0) sage: c = SandpileConfig(S, [1,2]) sage: d = SandpileConfig(S, [2,3]) sage: c < c False sage: c < d True sage: d < c False
---
**** *
如果
other
是一个配置,递归元素等于和。如果other
是一个整数,配置与自身之和other
时代。输入:
other
--整数和整数输出:
SandpileConfig
示例:
sage: S = sandpiles.Cycle(4) sage: c = SandpileConfig(S, [1,0,0]) sage: c + c # ordinary addition {1: 2, 2: 0, 3: 0} sage: c & c # add and stabilize {1: 0, 2: 1, 3: 0} sage: c*c # add and find equivalent recurrent {1: 1, 2: 1, 3: 1} sage: (c*c).is_recurrent() True sage: c*(-c) == S.identity() True sage: c {1: 1, 2: 0, 3: 0} sage: c*3 {1: 3, 2: 0, 3: 0}
---
^
与自身构型之和等价的递归元素 k 时代。如果 k 否定也一样。如果 k 零是群的返回。
输入:
k
--沙堆输出:
SandpileConfig
示例:
sage: S = sandpiles.Cycle(4) sage: c = SandpileConfig(S, [1,0,0]) sage: c^3 {1: 1, 2: 1, 3: 0} sage: (c + c + c) == c^3 False sage: (c + c + c).equivalent_recurrent() == c^3 True sage: c^(-1) {1: 1, 2: 1, 3: 0} sage: c^0 == S.identity() True
---
_
配置的加法逆。
输出:
SandpileConfig
示例:
sage: S = sandpiles.Cycle(3) sage: c = SandpileConfig(S, [1,2]) sage: -c {1: -1, 2: -2}
---
配置减法。
输入:
other
--沙堆输出:
总和
self
和other
示例:
sage: S = sandpiles.Cycle(3) sage: c = SandpileConfig(S, [1,2]) sage: d = SandpileConfig(S, [3,2]) sage: c - d {1: -2, 2: 0}
---
add_random(distrib=None)
向随机顶点添加一粒沙子。或者,概率分布, distrib
,可以放在顶点上,也可以放在非墨水顶点上。详见注释。
输入:
distrib
--(可选)总和为1的非负数列表(表示一个问题)。距离)
输出:
SandpileConfig
示例:
sage: s = sandpiles.Complete(4)
sage: c = s.zero_config()
sage: c.add_random() # random
{1: 0, 2: 1, 3: 0}
sage: c
{1: 0, 2: 0, 3: 0}
sage: c.add_random([0.1,0.1,0.8]) # random
{1: 0, 2: 0, 3: 1}
sage: c.add_random([0.7,0.1,0.1,0.1]) # random
{1: 0, 2: 0, 3: 0}
我们计算了在网格图的最大稳定配置中加入随机沙粒所引起的雪崩的“大小”。功能 stabilize()
返回稳定化的触发向量,字典的值表示每个顶点在稳定化中激发的次数。示例:
sage: S = sandpiles.Grid(10,10)
sage: m = S.max_stable()
sage: a = []
sage: for i in range(1000):
....: m = m.add_random()
....: m, f = m.stabilize(True)
....: a.append(sum(f.values()))
sage: p = list_plot([[log(i+1),log(a.count(i))] for i in [0..max(a)] if a.count(i)])
sage: p.axes_labels(['log(N)','log(D(N))'])
sage: t = text("Distribution of avalanche sizes", (2,2), rgbcolor=(1,0,0))
sage: show(p+t,axes_labels=['log(N)','log(D(N))'])
注解
如果 distrib
是 None
,则概率是非墨水顶点上的一致概率。否则,有两种可能:
(i) 长度 distrib
等于顶点数,并且 distrib
表示所有顶点上的概率分布。在这种情况下,可以随机选择接收器,在这种情况下,配置不变。
(ii)否则 distrib
必须等于非墨水顶点的数量,并且 distrib
表示非墨水顶点上的概率分布。
警告
如果 distrib != None
,用户负责确保其条目的和为1,并且其长度等于sink顶点的数量或非sink顶点的数量。
---
burst_size(v)
配置相对于给定顶点的突发大小。
输入:
v
--顶点
输出:
整数
示例:
sage: s = sandpiles.Diamond()
sage: [i.burst_size(0) for i in s.recurrents()]
[1, 1, 1, 1, 1, 1, 1, 1]
sage: [i.burst_size(1) for i in s.recurrents()]
[0, 0, 1, 2, 1, 2, 0, 2]
注解
定义 c.burst(v)
如果 v 不是水槽,让 c' 是唯一的周期性的 c' + v 是 c . 爆裂的大小就是在稳定过程中进入水槽的沙子的数量。如果 v 是接收器,突发大小定义为1。
参考文献:
---
度()
配置的程度。
输出:
整数
示例:
sage: S = sandpiles.Complete(3)
sage: c = SandpileConfig(S, [1,2])
sage: c.deg()
3
---
双重化()
与最大稳定构型的差异。
输出:
SandpileConfig
示例:
sage: S = sandpiles.Cycle(3)
sage: c = SandpileConfig(S, [1,2])
sage: S.max_stable()
{1: 1, 2: 1}
sage: c.dualize()
{1: 0, 2: -1}
sage: S.max_stable() - c == c.dualize()
True
---
equivalent_recurrent(with_firing_vector=False)
与给定配置等价的循环配置。或者,返回相应的触发向量。
输入:
with_firing_vector
--(默认值: False
)布尔型
输出:
沙堆 [SandpileConfig, firing_vector]
示例:
sage: S = sandpiles.Diamond()
sage: c = SandpileConfig(S, [0,0,0])
sage: c.equivalent_recurrent() == S.identity()
True
sage: x = c.equivalent_recurrent(True)
sage: r = vector([x[0][v] for v in S.nonsink_vertices()])
sage: f = vector([x[1][v] for v in S.nonsink_vertices()])
sage: cv = vector(c.values())
sage: r == cv - f*S.reduced_laplacian()
True
注解
让 L 是简化的拉普拉斯方程, c 初始配置, r 返回的配置,以及 f 发射矢量。那么 r = c - fcdot L .
---
equivalent_superstable(with_firing_vector=False)
等效的超稳定配置。或者,返回相应的触发向量。
输入:
with_firing_vector
--(默认值: False
)布尔型
输出:
沙堆 [SandpileConfig, firing_vector]
示例:
sage: S = sandpiles.Diamond()
sage: m = S.max_stable()
sage: m.equivalent_superstable().is_superstable()
True
sage: x = m.equivalent_superstable(True)
sage: s = vector(x[0].values())
sage: f = vector(x[1].values())
sage: mv = vector(m.values())
sage: s == mv - f*S.reduced_laplacian()
True
注解
让 L 是简化的拉普拉斯方程, c 初始配置, s 返回的配置,以及 f 发射矢量。那么 s = c - fcdot L .
---
fire_script(sigma)
启动给定脚本。换句话说,按照 sigma
.
输入:
sigma
--SandpileConfig or(代表SandpileConfig的列表或dict)
输出:
SandpileConfig
示例:
sage: S = sandpiles.Cycle(4)
sage: c = SandpileConfig(S, [1,2,3])
sage: c.unstable()
[2, 3]
sage: c.fire_script(SandpileConfig(S,[0,1,1]))
{1: 2, 2: 1, 3: 2}
sage: c.fire_script(SandpileConfig(S,[2,0,0])) == c.fire_vertex(1).fire_vertex(1)
True
---
fire_unstable()
激发所有不稳定的顶点。
输出:
SandpileConfig
示例:
sage: S = sandpiles.Cycle(4)
sage: c = SandpileConfig(S, [1,2,3])
sage: c.fire_unstable()
{1: 2, 2: 1, 3: 2}
---
fire_vertex(v)
激发给定顶点。
输入:
v
--顶点
输出:
SandpileConfig
示例:
sage: S = sandpiles.Cycle(3)
sage: c = SandpileConfig(S, [1,2])
sage: c.fire_vertex(2)
{1: 2, 2: 0}
---
help(verbose=True)
SandpileConfig方法列表。如果 verbose
,包括简短描述。
输入:
verbose
--(默认值: True
)布尔型
输出:
打印字符串
示例:
sage: SandpileConfig.help()
Shortcuts for SandpileConfig operations:
~c -- stabilize
c & d -- add and stabilize
c * c -- add and find equivalent recurrent
c^k -- add k times and find equivalent recurrent
(taking inverse if k is negative)
<BLANKLINE>
For detailed help with any method FOO listed below,
enter "SandpileConfig.FOO?" or enter "c.FOO?" for any SandpileConfig c.
<BLANKLINE>
add_random -- Add one grain of sand to a random vertex.
burst_size -- The burst size of the configuration with respect to the given vertex.
deg -- The degree of the configuration.
dualize -- The difference with the maximal stable configuration.
equivalent_recurrent -- The recurrent configuration equivalent to the given configuration.
equivalent_superstable -- The equivalent superstable configuration.
fire_script -- Fire the given script.
fire_unstable -- Fire all unstable vertices.
fire_vertex -- Fire the given vertex.
help -- List of SandpileConfig methods.
is_recurrent -- Is the configuration recurrent?
is_stable -- Is the configuration stable?
is_superstable -- Is the configuration superstable?
is_symmetric -- Is the configuration symmetric?
order -- The order of the equivalent recurrent element.
sandpile -- The configuration's underlying sandpile.
show -- Show the configuration.
stabilize -- The stabilized configuration.
support -- The vertices containing sand.
unstable -- The unstable vertices.
values -- The values of the configuration as a list.
---
is_recurrent()
配置是否重复?
输出:
布尔
示例:
sage: S = sandpiles.Diamond()
sage: S.identity().is_recurrent()
True
sage: S.zero_config().is_recurrent()
False
---
is_stable()
配置是否稳定?
输出:
布尔
示例:
sage: S = sandpiles.Diamond()
sage: S.max_stable().is_stable()
True
sage: (2*S.max_stable()).is_stable()
False
sage: (S.max_stable() & S.max_stable()).is_stable()
True
---
is_superstable()
配置是否超稳定?
输出:
布尔
示例:
sage: S = sandpiles.Diamond()
sage: S.zero_config().is_superstable()
True
---
is_symmetric(orbits)
配置是否对称?返回 True
如果配置的值在 orbits
.
输入:
orbits
--顶点列表列表
输出:
布尔
示例:
sage: S = Sandpile({0: {},
....: 1: {0: 1, 2: 1, 3: 1},
....: 2: {1: 1, 3: 1, 4: 1},
....: 3: {1: 1, 2: 1, 4: 1},
....: 4: {2: 1, 3: 1}})
sage: c = SandpileConfig(S, [1, 2, 2, 3])
sage: c.is_symmetric([[2,3]])
True
---
命令()
等价递归元的阶。
输出:
整数
示例:
sage: S = sandpiles.Diamond()
sage: c = SandpileConfig(S,[2,0,1])
sage: c.order()
4
sage: ~(c + c + c + c) == S.identity()
True
sage: c = SandpileConfig(S,[1,1,0])
sage: c.order()
1
sage: c.is_recurrent()
False
sage: c.equivalent_recurrent() == S.identity()
True
---
沙堆()
结构的底层沙堆。
输出:
沙堆
示例:
sage: S = sandpiles.Diamond()
sage: c = S.identity()
sage: c.sandpile()
Diamond sandpile graph: 4 vertices, sink = 0
sage: c.sandpile() == S
True
---
show(sink=True, colors=True, heights=False, directed=None, ** 科威特第纳尔)
显示配置。
输入:
sink
--(默认值:True
)是否显示水槽colors
--(默认值:True
)是否对每个顶点上的沙子量进行颜色编码heights
--(默认值:False
)是否用沙子的数量标记每个顶点directed
--(可选)是否绘制定向边kwds
--(可选)传递给Graph的show方法的参数
示例:
sage: S = sandpiles.Diamond()
sage: c = S.identity()
sage: c.show()
sage: c.show(directed=False)
sage: c.show(sink=False,colors=False,heights=True)
---
stabilize(with_firing_vector=False)
稳定的配置。可选地返回相应的触发向量。
输入:
with_firing_vector
--(默认值: False
)布尔型
输出:
SandpileConfig
or [SandpileConfig, firing_vector]
示例:
sage: S = sandpiles.House()
sage: c = 2*S.max_stable()
sage: c._set_stabilize()
sage: '_stabilize' in c.__dict__
True
sage: S = sandpiles.House()
sage: c = S.max_stable() + S.identity()
sage: c.stabilize(True)
[{1: 1, 2: 2, 3: 2, 4: 1}, {1: 2, 2: 2, 3: 3, 4: 3}]
sage: S.max_stable() & S.identity() == c.stabilize()
True
sage: ~c == c.stabilize()
True
---
支持()
包含沙子的顶点。
输出:
列表-配置支持
示例:
sage: S = sandpiles.Diamond()
sage: c = S.identity()
sage: c
{1: 2, 2: 2, 3: 0}
sage: c.support()
[1, 2]
---
不稳定()
不稳定的顶点。
输出:
顶点列表
示例:
sage: S = sandpiles.Cycle(4)
sage: c = SandpileConfig(S, [1,2,3])
sage: c.unstable()
[2, 3]
---
值()
以列表形式显示配置的值。列表按顶点的顺序排序。
输出:
整数列表
布尔
示例:
sage: S = Sandpile({'a':['c','b'], 'b':['c','a'], 'c':['a']},'a')
sage: c = SandpileConfig(S, {'b':1, 'c':2})
sage: c
{'b': 1, 'c': 2}
sage: c.values()
[1, 2]
sage: S.nonsink_vertices()
['b', 'c']
---
SandpileDivisor¶
方法概述。
+ ---除数相加。
greater-equal ---
True
如果self
至少是other
.greater ---
True
如果self
至少是other
两个除数不相等。less-equal ---
True
如果self
最多是other
.less ---
True
如果self
最多是other
两个除数不相等。- ---除数的加法逆。
- ---除数的减法。
Dcomplex ---支持综合体。
add_random ---向随机顶点添加一粒沙子。
betti ---支持中心的贝蒂号码。
deg ---除数的度数。
dualize ---与最大稳定因子的差。
effective_div ---所有线性等价的有效除数。
fire_script ---启动给定脚本。
fire_unstable ---激发所有不稳定的顶点。
fire_vertex ---激发给定顶点。
help ---沙堆方法列表。
is_alive ---除数是稳定的吗?
is_linearly_equivalent ---给定的除数是线性等价的吗?
is_q_reduced ---除数q-减少了吗?
is_symmetric ---除数是对称的吗?
is_weierstrass_pt ---给定的顶点是Weierstrass点吗?
polytope ---决定整个线性系统的多面体。
polytope_integer_pts ---除数多面体内的整数点。
q_reduced ---线性等价q-约化因子。
rank ---除数的等级。
sandpile ---在沙堆下面。
show ---显示除数。
simulate_threshold ---闭Markov链中的第一个不稳定因子。
stabilize ---除数的稳定性。
support ---除数不为零的顶点列表。
unstable ---不稳定的顶点。
values ---除数的值作为列表。
weierstrass_div ---Weierstrass除数。
weierstrass_gap_seq ---给定顶点处的Weierstrass间隙序列。
weierstrass_pts ---Weierstrass点(顶点)。
weierstrass_rank_seq ---给定顶点的Weierstrass秩序列。
砂桩遮阳方法的完整说明。
---
+
除数相加。
输入:
other
--沙堆输出:
总和
self
和other
示例:
sage: S = sandpiles.Cycle(3) sage: D = SandpileDivisor(S, [1,2,3]) sage: E = SandpileDivisor(S, [3,2,1]) sage: D + E {0: 4, 1: 4, 2: 4}
---
>=
True
如果self
至少是other
.输入:
other
--沙堆输出:
布尔
示例:
sage: S = sandpiles.Cycle(3) sage: D = SandpileDivisor(S, [1,2,3]) sage: E = SandpileDivisor(S, [2,3,4]) sage: F = SandpileDivisor(S, [2,0,4]) sage: D >= D True sage: E >= D True sage: D >= E False sage: F >= D False sage: D >= F False
---
>
True
如果self
至少是other
两个除数不相等。输入:
other
--沙堆输出:
布尔
示例:
sage: S = sandpiles.Cycle(3) sage: D = SandpileDivisor(S, [1,2,3]) sage: E = SandpileDivisor(S, [1,3,4]) sage: D > D False sage: E > D True sage: D > E False
---
<=
True
如果self
最多是other
.输入:
other
--沙堆输出:
布尔
示例:
sage: S = sandpiles.Cycle(3) sage: D = SandpileDivisor(S, [1,2,3]) sage: E = SandpileDivisor(S, [2,3,4]) sage: F = SandpileDivisor(S, [2,0,4]) sage: D <= D True sage: D <= E True sage: E <= D False sage: D <= F False sage: F <= D False
---
<
True
如果self
最多是other
两个除数不相等。输入:
other
--沙堆输出:
布尔
示例:
sage: S = sandpiles.Cycle(3) sage: D = SandpileDivisor(S, [1,2,3]) sage: E = SandpileDivisor(S, [2,3,4]) sage: D < D False sage: D < E True sage: E < D False
---
除数的加法逆。
输出:
SandpileDivisor
示例:
sage: S = sandpiles.Cycle(3) sage: D = SandpileDivisor(S, [1,2,3]) sage: -D {0: -1, 1: -2, 2: -3}
---
除数的减法。
输入:
other
--沙堆输出:
差异性
self
和other
示例:
sage: S = sandpiles.Cycle(3) sage: D = SandpileDivisor(S, [1,2,3]) sage: E = SandpileDivisor(S, [3,2,1]) sage: D - E {0: -2, 1: 0, 2: 2}
---
Dcomplex()
支持综合体。(见注释。)
输出:
简单复形
示例:
sage: S = sandpiles.House()
sage: p = SandpileDivisor(S, [1,2,1,0,0]).Dcomplex()
sage: p.homology()
{0: 0, 1: Z x Z, 2: 0}
sage: p.f_vector()
[1, 5, 10, 4]
sage: p.betti()
{0: 1, 1: 2, 2: 0}
注解
“支撑复形”是由线性等价有效除数的支撑所决定的简单复形。
---
add_random(distrib=None)
向随机顶点添加一粒沙子。
输入:
distrib
--(可选)表示顶点上概率分布的非负数列表
输出:
SandpileDivisor
示例:
sage: s = sandpiles.Complete(4)
sage: D = s.zero_div()
sage: D.add_random() # random
{0: 0, 1: 0, 2: 1, 3: 0}
sage: D.add_random([0.1,0.1,0.1,0.7]) # random
{0: 0, 1: 0, 2: 0, 3: 1}
警告
如果 distrib
不是 None
,用户负责确保其条目的总和为1。
---
贝蒂()
支持中心的贝蒂号码。(见注释。)
输出:
整数字典
示例:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [2,0,1])
sage: D.betti()
{0: 1, 1: 1}
注解
“支撑复形”是由线性等价有效除数的支撑所决定的简单复形。
---
度()
除数的度数。
输出:
整数
示例:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.deg()
6
---
双重化()
与最大稳定因子的差。
输出:
SandpileDivisor
- 示例:
sage: S = sandpiles.Cycle(3) sage: D = SandpileDivisor(S, [1,2,3]) sage: D.dualize() {0: 0, 1: -1, 2: -2} sage: S.max_stable_div() - D == D.dualize() True
---
effective_div(verbose=True, with_firing_vectors=False)
所有线性等价的有效除数。如果 verbose
是 False
,则将除数转换为整数列表。如果 with_firing_vectors
是 True
然后给出了一个触发向量的列表,每个向量都规定了要触发的顶点,以获得一个有效的除数。
输入:
verbose
--(默认值:True
)布尔型with_firing_vectors
--(默认值:False
)布尔型
输出:
(除数)列表
示例:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[4,2,0,0])
sage: sorted(D.effective_div(), key=str)
[{0: 0, 1: 2, 2: 0, 3: 4},
{0: 0, 1: 2, 2: 4, 3: 0},
{0: 0, 1: 6, 2: 0, 3: 0},
{0: 1, 1: 3, 2: 1, 3: 1},
{0: 2, 1: 0, 2: 2, 3: 2},
{0: 4, 1: 2, 2: 0, 3: 0}]
sage: sorted(D.effective_div(False))
[[0, 2, 0, 4],
[0, 2, 4, 0],
[0, 6, 0, 0],
[1, 3, 1, 1],
[2, 0, 2, 2],
[4, 2, 0, 0]]
sage: sorted(D.effective_div(with_firing_vectors=True), key=str)
[({0: 0, 1: 2, 2: 0, 3: 4}, (0, -1, -1, -2)),
({0: 0, 1: 2, 2: 4, 3: 0}, (0, -1, -2, -1)),
({0: 0, 1: 6, 2: 0, 3: 0}, (0, -2, -1, -1)),
({0: 1, 1: 3, 2: 1, 3: 1}, (0, -1, -1, -1)),
({0: 2, 1: 0, 2: 2, 3: 2}, (0, 0, -1, -1)),
({0: 4, 1: 2, 2: 0, 3: 0}, (0, 0, 0, 0))]
sage: a = _[2]
sage: a[0].values()
[0, 6, 0, 0]
sage: vector(D.values()) - s.laplacian()*a[1]
(0, 6, 0, 0)
sage: sorted(D.effective_div(False, True))
[([0, 2, 0, 4], (0, -1, -1, -2)),
([0, 2, 4, 0], (0, -1, -2, -1)),
([0, 6, 0, 0], (0, -2, -1, -1)),
([1, 3, 1, 1], (0, -1, -1, -1)),
([2, 0, 2, 2], (0, 0, -1, -1)),
([4, 2, 0, 0], (0, 0, 0, 0))]
sage: D = SandpileDivisor(s,[-1,0,0,0])
sage: D.effective_div(False,True)
[]
---
fire_script(sigma)
启动给定脚本。换句话说,按照 sigma
.
输入:
sigma
--沙堆或(代表沙堆的列表或dict)
输出:
SandpileDivisor
示例:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.unstable()
[1, 2]
sage: D.fire_script([0,1,1])
{0: 3, 1: 1, 2: 2}
sage: D.fire_script(SandpileDivisor(S,[2,0,0])) == D.fire_vertex(0).fire_vertex(0)
True
---
fire_unstable()
激发所有不稳定的顶点。
输出:
SandpileDivisor
示例:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.fire_unstable()
{0: 3, 1: 1, 2: 2}
---
fire_vertex(v)
激发给定顶点。
输入:
v
--顶点
输出:
SandpileDivisor
示例:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.fire_vertex(1)
{0: 2, 1: 0, 2: 4}
---
help(verbose=True)
沙堆方法列表。如果 verbose
,包括简短描述。
输入:
verbose
--(默认值: True
)布尔型
输出:
打印字符串
示例:
sage: SandpileDivisor.help()
For detailed help with any method FOO listed below,
enter "SandpileDivisor.FOO?" or enter "D.FOO?" for any SandpileDivisor D.
<BLANKLINE>
Dcomplex -- The support-complex.
add_random -- Add one grain of sand to a random vertex.
betti -- The Betti numbers for the support-complex.
deg -- The degree of the divisor.
dualize -- The difference with the maximal stable divisor.
effective_div -- All linearly equivalent effective divisors.
fire_script -- Fire the given script.
fire_unstable -- Fire all unstable vertices.
fire_vertex -- Fire the given vertex.
help -- List of SandpileDivisor methods.
is_alive -- Is the divisor stabilizable?
is_linearly_equivalent -- Is the given divisor linearly equivalent?
is_q_reduced -- Is the divisor q-reduced?
is_symmetric -- Is the divisor symmetric?
is_weierstrass_pt -- Is the given vertex a Weierstrass point?
polytope -- The polytope determining the complete linear system.
polytope_integer_pts -- The integer points inside divisor's polytope.
q_reduced -- The linearly equivalent q-reduced divisor.
rank -- The rank of the divisor.
sandpile -- The divisor's underlying sandpile.
show -- Show the divisor.
simulate_threshold -- The first unstabilizable divisor in the closed Markov chain.
stabilize -- The stabilization of the divisor.
support -- List of vertices at which the divisor is nonzero.
unstable -- The unstable vertices.
values -- The values of the divisor as a list.
weierstrass_div -- The Weierstrass divisor.
weierstrass_gap_seq -- The Weierstrass gap sequence at the given vertex.
weierstrass_pts -- The Weierstrass points (vertices).
weierstrass_rank_seq -- The Weierstrass rank sequence at the given vertex.
---
is_alive(cycle=False)
除数是稳定的吗?换言之,除数在所有不稳定顶点的重复激发下会稳定吗?可选地返回结果循环。
输入:
cycle
--(默认值: False
)布尔型
输出:
布尔型或可选的沙堆编辑器列表
示例:
sage: S = sandpiles.Complete(4)
sage: D = SandpileDivisor(S, {0: 4, 1: 3, 2: 3, 3: 2})
sage: D.is_alive()
True
sage: D.is_alive(True)
[{0: 4, 1: 3, 2: 3, 3: 2}, {0: 3, 1: 2, 2: 2, 3: 5}, {0: 1, 1: 4, 2: 4, 3: 3}]
---
is_linearly_equivalent(D, with_firing_vector=False)
给定的除数是线性等价的吗?(可选)返回触发向量。(见注释。)
输入:
D
--代表除数的链表、元组等with_firing_vector
--(默认值:False
)布尔型
输出:
布尔或整数向量
示例:
sage: s = sandpiles.Complete(3)
sage: D = SandpileDivisor(s,[2,0,0])
sage: D.is_linearly_equivalent([0,1,1])
True
sage: D.is_linearly_equivalent([0,1,1],True)
(1, 0, 0)
sage: v = vector(D.is_linearly_equivalent([0,1,1],True))
sage: vector(D.values()) - s.laplacian()*v
(0, 1, 1)
sage: D.is_linearly_equivalent([0,0,0])
False
sage: D.is_linearly_equivalent([0,0,0],True)
()
注解
如果
with_firing_vector
是False
,返回True
或False
.如果
with_firing_vector
是True
那么:(i)如果self
线性等价于 D ,返回一个向量 v 这样的话self - v*self.laplacian().transpose() = D
. 否则,(ii)如果self
不是线性等价于 D ,输出为空向量,()
.
---
is_q_reduced()
是除数 q -减少了?这就意味着 self = c + kq 在哪里? c 超级稳定, k 整数,并且 q 是水槽顶点。
输出:
布尔
示例:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[2,-3,2,0])
sage: D.is_q_reduced()
False
sage: SandpileDivisor(s,[10,0,1,2]).is_q_reduced()
True
对于无向图或更一般的欧拉图, q -约化因子是线性等价的当且仅当它们相等。对于一般有向图,这一点并不成立:
sage: s = Sandpile({0:[1],1:[1,1]})
sage: D = SandpileDivisor(s,[-1,1])
sage: Z = s.zero_div()
sage: D.is_q_reduced()
True
sage: Z.is_q_reduced()
True
sage: D == Z
False
sage: D.is_linearly_equivalent(Z)
True
---
is_symmetric(orbits)
除数是对称的吗?返回 True
如果配置的值在 orbits
.
输入:
orbits
--顶点列表列表
输出:
布尔
示例:
sage: S = sandpiles.House()
sage: S.dict()
{0: {1: 1, 2: 1},
1: {0: 1, 3: 1},
2: {0: 1, 3: 1, 4: 1},
3: {1: 1, 2: 1, 4: 1},
4: {2: 1, 3: 1}}
sage: D = SandpileDivisor(S, [0,0,1,1,3])
sage: D.is_symmetric([[2,3], [4]])
True
---
is_weierstrass_pt(v='sink')
给定的顶点是Weierstrass点吗?
输入:
v
--(默认值: sink
)顶点
输出:
布尔
示例:
sage: s = sandpiles.House()
sage: K = s.canonical_divisor()
sage: K.weierstrass_rank_seq() # sequence at the sink vertex, 0
(1, 0, -1)
sage: K.is_weierstrass_pt()
False
sage: K.weierstrass_rank_seq(4)
(1, 0, 0, -1)
sage: K.is_weierstrass_pt(4)
True
注解
顶点 v 是除数的(广义)Weierstrass点 D 如果等级顺序 r(D - nv) 对于 n = 0, 1, 2, dots 不是 r(D), r(D)-1, dots, 0, -1, -1, dots .
---
多面体()
决定整个线性系统的多面体。
输出:
多面体
示例:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[4,2,0,0])
sage: p = D.polytope()
sage: p.inequalities()
(An inequality (-3, 1, 1) x + 2 >= 0,
An inequality (1, 1, 1) x + 4 >= 0,
An inequality (1, -3, 1) x + 0 >= 0,
An inequality (1, 1, -3) x + 0 >= 0)
sage: D = SandpileDivisor(s,[-1,0,0,0])
sage: D.polytope()
The empty polyhedron in QQ^3
注解
对于除数 D ,这是(i)由不等式组确定的多面体的交集 L^t x leq D 在哪里? L^t 拉普拉斯算子与(ii)超平面的转置吗 x_{{mathrm{{sink_vertex}}}} = 0 . 多面体被认为是坐在 (n-1) -维欧几里德空间 n 是顶点数。
---
polytope_integer_pts()
除数多面体内的整数点。这里提到的多面体是决定除数的完整线性系统的多面体(参见文档 polytope
)
输出:
整数向量元组
示例:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[4,2,0,0])
sage: sorted(D.polytope_integer_pts())
[(-2, -1, -1),
(-1, -2, -1),
(-1, -1, -2),
(-1, -1, -1),
(0, -1, -1),
(0, 0, 0)]
sage: D = SandpileDivisor(s,[-1,0,0,0])
sage: D.polytope_integer_pts()
()
---
q_reduced(verbose=True)
线性等价物 q -约化除数。
输入:
verbose
--(默认值: True
)布尔型
输出:
沙堆或代表沙堆的列表
示例:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[2,-3,2,0])
sage: D.q_reduced()
{0: -2, 1: 1, 2: 2, 3: 0}
sage: D.q_reduced(False)
[-2, 1, 2, 0]
注解
除数 D 是 qreduced if ` D=c+kq`其中 `c 超级稳定, k 整数,并且 q 是水槽。
---
rank(with_witness=False)
除数的等级。可选地返回有效除数 E 这样的话 D - E 无法获胜(有一个空的完整线性系统)。
输入:
with_witness
--(默认值: False
)布尔型
输出:
整数或(整数,沙盘)
示例:
sage: S = sandpiles.Complete(4)
sage: D = SandpileDivisor(S,[4,2,0,0])
sage: D.rank()
3
sage: D.rank(True)
(3, {0: 3, 1: 0, 2: 1, 3: 0})
sage: E = _[1]
sage: (D - E).rank()
-1
Riemann-Roch theorem::
sage: D.rank() - (S.canonical_divisor()-D).rank() == D.deg() + 1 - S.genus()
True
Riemann-Roch theorem::
sage: D.rank() - (S.canonical_divisor()-D).rank() == D.deg() + 1 - S.genus()
True
sage: S = Sandpile({0:[1,1,1,2],1:[0,0,0,1,1,1,2,2],2:[2,2,1,1,0]},0) # multigraph with loops
sage: D = SandpileDivisor(S,[4,2,0])
sage: D.rank(True)
(2, {0: 1, 1: 1, 2: 1})
sage: S = Sandpile({0:[1,2], 1:[0,2,2], 2: [0,1]},0) # directed graph
sage: S.is_undirected()
False
sage: D = SandpileDivisor(S,[0,2,0])
sage: D.effective_div()
[{0: 0, 1: 2, 2: 0}, {0: 2, 1: 0, 2: 0}]
sage: D.rank(True)
(0, {0: 0, 1: 0, 2: 1})
sage: E = D.rank(True)[1]
sage: (D - E).effective_div()
[]
注解
除数除数的等级 D 是-1如果 D 不是一个有效除数的线性等价物(即 D 无法获胜)。否则 D 是最大的整数 r 这样的话 D - E 与所有有效除数的有效除数线性等价 E 具有 deg(E) = r .
---
沙堆()
除数的底层沙堆。
输出:
沙堆
示例:
sage: S = sandpiles.Diamond()
sage: D = SandpileDivisor(S,[1,-2,0,3])
sage: D.sandpile()
Diamond sandpile graph: 4 vertices, sink = 0
sage: D.sandpile() == S
True
---
show(heights=True, directed=None, ** 科威特第纳尔)
显示除数。
输入:
heights
--(默认值:True
)是否用沙子的数量标记每个顶点directed
--(可选)是否绘制定向边kwds
--(可选)传递给Graph的show方法的参数
示例:
sage: S = sandpiles.Diamond()
sage: D = SandpileDivisor(S,[1,-2,0,2])
sage: D.show(graph_border=True,vertex_size=700,directed=False)
---
simulate_threshold(distrib=None)
闭Markov链中的第一个不稳定因子。(见注释。)
输入:
distrib
--(可选)表示顶点上概率分布的非负数列表
输出:
SandpileDivisor
示例:
sage: s = sandpiles.Complete(4)
sage: D = s.zero_div()
sage: D.simulate_threshold() # random
{0: 2, 1: 3, 2: 1, 3: 2}
sage: n(mean([D.simulate_threshold().deg() for _ in range(10)])) # random
7.10000000000000
sage: n(s.stationary_density()*s.num_verts())
6.93750000000000
注解
开始于 self
,反复选择一个顶点并在其上添加一粒沙子。返回到达的第一个不稳定除数。另请参见 markov_chain
下伏沙堆方法。
---
stabilize(with_firing_vector=False)
除数的稳定性。如果不稳定,则返回错误。
输入:
with_firing_vector
--(默认值: False
)布尔型
示例:
sage: s = sandpiles.Complete(4)
sage: D = SandpileDivisor(s,[0,3,0,0])
sage: D.stabilize()
{0: 1, 1: 0, 2: 1, 3: 1}
sage: D.stabilize(with_firing_vector=True)
[{0: 1, 1: 0, 2: 1, 3: 1}, {0: 0, 1: 1, 2: 0, 3: 0}]
---
支持()
除数不为零的顶点列表。
输出:
表示除数支持的列表
示例:
sage: S = sandpiles.Cycle(4)
sage: D = SandpileDivisor(S, [0,0,1,1])
sage: D.support()
[2, 3]
sage: S.vertices()
[0, 1, 2, 3]
---
不稳定()
不稳定的顶点。
输出:
顶点列表
示例:
sage: S = sandpiles.Cycle(3)
sage: D = SandpileDivisor(S, [1,2,3])
sage: D.unstable()
[1, 2]
---
值()
除数的值作为列表。列表按顶点的顺序排序。
输出:
整数列表
布尔
示例:
sage: S = Sandpile({'a':['c','b'], 'b':['c','a'], 'c':['a']},'a')
sage: D = SandpileDivisor(S, {'a':0, 'b':1, 'c':2})
sage: D
{'a': 0, 'b': 1, 'c': 2}
sage: D.values()
[0, 1, 2]
sage: S.vertices()
['a', 'b', 'c']
---
weierstrass_div(verbose=True)
Weierstrass除数。它在一个顶点上的值是该顶点作为Weierstrass点的权重。(参见 SandpileDivisor.weierstrass_gap_seq
)
输入:
verbose
--(默认值: True
)布尔型
输出:
SandpileDivisor
示例:
sage: s = sandpiles.Diamond()
sage: D = SandpileDivisor(s,[4,2,1,0])
sage: [D.weierstrass_rank_seq(v) for v in s]
[(5, 4, 3, 2, 1, 0, 0, -1),
(5, 4, 3, 2, 1, 0, -1),
(5, 4, 3, 2, 1, 0, 0, 0, -1),
(5, 4, 3, 2, 1, 0, 0, -1)]
sage: D.weierstrass_div()
{0: 1, 1: 0, 2: 2, 3: 1}
sage: k5 = sandpiles.Complete(5)
sage: K = k5.canonical_divisor()
sage: K.weierstrass_div()
{0: 9, 1: 9, 2: 9, 3: 9, 4: 9}
---
weierstrass_gap_seq(v='sink', weight=True)
给定顶点处的Weierstrass间隙序列。如果 weight
是 True
,然后计算每个间隙值的权重。
输入:
v
--(默认值:sink
)顶点weight
--(默认值:True
)布尔型
输出:
整数的列表或(列表的列表)
示例:
sage: s = sandpiles.Cycle(4)
sage: D = SandpileDivisor(s,[2,0,0,0])
sage: [D.weierstrass_gap_seq(v,False) for v in s.vertices()]
[(1, 3), (1, 2), (1, 3), (1, 2)]
sage: [D.weierstrass_gap_seq(v) for v in s.vertices()]
[((1, 3), 1), ((1, 2), 0), ((1, 3), 1), ((1, 2), 0)]
sage: D.weierstrass_gap_seq() # gap sequence at sink vertex, 0
((1, 3), 1)
sage: D.weierstrass_rank_seq() # rank sequence at the sink vertex
(1, 0, 0, -1)
注解
整数 k 是除数的Weierstrass缺口 D 在顶点 v 如果 D - (k-1)v 不等于等级 D - kv . 让 r 等级 D 让 k_i 成为 i -第个间隙 v . 重量 v 对于 D 是 (k_i - i) 作为 i 范围从 1 到 r + 1 . 它测量序列之间的差异 r, r - 1, ..., 0, -1, -1, ... 以及等级序列 mathrm{{rank}}(D), mathrm{{rank}}(D - v), mathrm{{rank}}(D - 2v), dots
---
weierstrass_pts(with_rank_seq=False)
Weierstrass点(顶点)。或者,返回相应的秩序列。
输入:
with_rank_seq
--(默认值: False
)布尔型
输出:
顶点元组或列表(顶点,秩序列)
示例:
sage: s = sandpiles.House()
sage: K = s.canonical_divisor()
sage: K.weierstrass_pts()
(4,)
sage: K.weierstrass_pts(True)
[(4, (1, 0, 0, -1))]
注解
顶点 v 是除数的(广义)Weierstrass点 D 如果等级顺序 r(D - nv) 对于 n = 0, 1, 2, dots 不是 r(D), r(D)-1, dots, 0, -1, -1, dots
---
weierstrass_rank_seq(v='sink')
给定顶点的Weierstrass秩序列。计算除数的秩 D - nv 从开始 n=0 当等级达到 -1 .
输入:
v
--(默认值: sink
)顶点
输出:
整数元组
示例:
sage: s = sandpiles.House()
sage: K = s.canonical_divisor()
sage: [K.weierstrass_rank_seq(v) for v in s.vertices()]
[(1, 0, -1), (1, 0, -1), (1, 0, -1), (1, 0, -1), (1, 0, 0, -1)]
---
其他¶
firing_graph ---点火图。
parallel_firing_graph ---平行点火图。
random_DAG ---随机有向无环图。
sandpiles ---沙堆的一些例子。
wilmes_algorithm ---查找具有相同整数行跨度的矩阵
M
这是有向图的约化拉普拉斯。
方法的完整描述。
firing_graph(S, eff)
在两个除数之间创建一个以除数为顶点和边的有向图 D 和 E 如果发射一个顶点 D 给予 E .
输入:
S
--沙堆eff
--除数列表输出:
DiGraph
示例:
sage: S = sandpiles.Cycle(6) sage: D = SandpileDivisor(S, [1,1,1,1,2,0]) sage: eff = D.effective_div() sage: firing_graph(S,eff).show3d(edge_size=.005,vertex_size=0.01)
---
parallel_firing_graph(S,eff)
在两个除数之间创建一个以除数为顶点和边的有向图
D
和E
如果发射所有不稳定的顶点D
给予E
.输入:
S
-沙堆eff
-除数列表输出:
DiGraph
示例:
sage: S = Sandpile(graphs.CycleGraph(6),0) sage: D = SandpileDivisor(S, [1,1,1,1,2,0]) sage: eff = D.effective_div() sage: parallel_firing_graph(S,eff).show3d(edge_size=.005,vertex_size=0.01)
---
random_DAG(num_verts,p=1/2,weight_max=1)
返回一个随机有向无环图
num_verts
顶点。该方法从sink顶点开始,一次添加一个顶点。每个顶点只连接到先前定义的顶点,每个可能连接的概率由参数给出p
. 边的权重是介于1
和weight_max
.输入:
num_verts
-正整数
p
- number between 0 and 1
weight_max
-- integer greater than 0输出:
有向无环图 0
示例:
sage: S = random_DAG(5, 0.3)
---
sandpiles
沙堆的一些例子。
以下是可用的示例;您也可以键入“sandpiles.”,然后按tab键以获取列表:
“完成()”
“循环()”
“钻石()”
“网格()”
“房子()”
示例:
sage: s = sandpiles.Complete(4) sage: s.invariant_factors() [1, 4, 4] sage: s.laplacian() [ 3 -1 -1 -1] [-1 3 -1 -1] [-1 -1 3 -1] [-1 -1 -1 3]
---
wilmes_algorithm(M)
计算整数矩阵
L
具有与相同的整数行跨度M
就这样L
是有向多重图的约化拉普拉斯算子。输入:
M
-满秩平方整数矩阵输出:
L
-整数矩阵示例:
sage: P = matrix([[2,3,-7,-3],[5,2,-5,5],[8,2,5,4],[-5,-9,6,6]]) sage: wilmes_algorithm(P) [ 1642 -13 -1627 -1] [ -1 1980 -1582 -397] [ 0 -1 1650 -1649] [ 0 0 -1658 1658]笔记:
这个算法是由johnwilmes提出的。
帮助¶
可通过Sage在线帮助系统获取每种方法的文档:
sage: SandpileConfig.fire_vertex?
Base Class: <type 'instancemethod'>
String Form: <unbound method SandpileConfig.fire_vertex>
Namespace: Interactive
File: /usr/local/sage-4.7/local/lib/python2.6/site-packages/sage/sandpiles/sandpile.py
Definition: SandpileConfig.fire_vertex(self, v)
Docstring:
Fire the vertex ``v``.
INPUT:
``v`` - vertex
OUTPUT:
SandpileConfig
EXAMPLES:
sage: S = Sandpile(graphs.CycleGraph(3), 0)
sage: c = SandpileConfig(S, [1,2])
sage: c.fire_vertex(2)
{1: 2, 2: 0}
注解
替代 SandpileConfig.fire_vertex?
在前面的代码示例中 c.fire_vertex?
如果 c
是沙堆鱼。
进入 Sandpile.help()
, SandpileConfig.help()
和 SandpileDivisor.help()
有关可用沙堆特定方法的列表。
一般Sage文档可在http://doc.sagemath.org/html/en/。
联系¶
请联系davidp@reed.edu包括问题、错误报告、附加功能和其他改进的建议。
- BN(1,2)
马修·贝克,谢尔盖·诺琳, Riemann-Roch and Abel-Jacobi Theory on a Finite Graph 《数学进展》215(2007),766--788。
- BTW
Per Bak,Chao Tang和Kurt Wiesenfeld(1987年)。 Self-organized criticality: an explanation of 1/f noise ,体检通知书60:381--384; :wikipedia:`Bak-Tang-Wiesenfeld_sandpile` .
- CRS
罗伯特·科里,多米尼克·罗辛和布鲁诺·萨尔维, 沙堆的多项式理想及其Gröbner基 ,理论计算机科学,276(2002)第1--2,1--15号。
- H
亚历山大·霍罗伊德、莱昂内尔·莱文、卡罗拉·梅萨罗斯、尤瓦尔·佩雷斯、詹姆斯·普洛普、大卫·B·威尔逊, Chip-Firing and Rotor-Routing on Directed Graphs , :arxiv:`0801.3306` . 本文的旧版本出现在 平衡点内外2 ,Eds.V.Sidoravicius,M.E.Vares,在《概率进展》系列文章中,Birkhauser(2008)。
- PPW2013
D、 帕金森、J.珀尔曼和J.威尔姆斯。 沙堆代数几何入门 . 热带和非阿基米德几何,当代。数学,605,阿默尔。数学。加州,普罗维登斯,RI,2013年。 :arxiv:`1112.6163` .