引言
图论在密码学、网络设计、信息科学、工业生产和企业管理等现代科学技术的研究中有着重要的理论价值和广泛应用，因此，对于图论的理论研究尤为重要，也受到了广泛关注。Spencer[1]于1986年提出了无向图上的一个balancing game。随后，Björner等[2]将该博弈进一步推广，即chip-firing games (筹码分发博弈)，其规则如下：起初在简单图G=(V, E)的顶点上放置若干个筹码(chips)，如果顶点vi∈V的度数不超过其筹码数，即deg(vi)≤ci，其中ci为顶点vi上的初始筹码数，称该顶点vi可以分发(firing)；分发后该顶点对其相邻的顶点各发射一枚筹码，这样顶点vi的筹码数为ci-deg(vi)，其相邻顶点的筹码数将分别增加1个；经过若干次分发后，如果所有顶点不可再分发，则称图G在该初始状态下博弈次数是有限的。该博弈对理论物理研究有着重要作用，如阿贝尔沙堆模型是chip-firing games的变体，Bak等[3]在1987年基于该模型发现了动力系统展现的自组织临界性。目前，围绕该博弈的理论研究吸引了大批数学领域的学者，特别是运用代数组合方法找到该博弈与Tutte多项式、群理论以及超平面构形(hyperplane arrangements)等方面的联系。如Biggs[4]利用阿贝尔群的性质描述有限状态下的chip-firing games博弈过程，此时群的阶数等于图的树的个数; López[5]证明了图G的初始critical配置的生成函数等于图G的Tutte多项式，基于此结果可以计算图构形(graphic arrangements)的特征多项式。针对某一特定的图，研究者们给出了该博弈的性质。例如，Jeffs等[6]描述了n-圈图上共有n个筹码时博弈的无限分布状态；Zhuang等[7]研究了完全图上该博弈次数有限的充要条件; Hopkins等[8]研究了该博弈在无限路径图上的状态分布特性；Len[9]探讨了此理论在代数几何中应用。更多其他关于chip-firing games的研究成果可参考文献[10-14]。但是，对于许多种类的图，筹码分布的初始状态与博弈的有限性的关系还未能确定。在本文中我们将得出完全二部图上博弈次数有限的充要条件。
1 无向连通图上的筹码分发博弈
定义1 图G是由点集V={v1, v2, …, vn}和连接顶点的边集合E={e1, e2, …, em}组成的二元组，记作G=(V, E)。称顶点集合的基数n为图的阶数，称图G为n阶图。
定义2 对于无向连通图G=(V, E)，如果V=A∪B且A∩B=ϕ，A中的每一顶点与B中的任一顶点均有且仅有1条边相连，则称G为完全二部图。
定义3 若图G中任一顶点vi∈V的筹码数为ci，称向量c =(c1, c2, …, cn)∈ $\mathbb{Z}_{\geqslant 0}^n$ 为该状态的筹码配置。
定义4 设G=(V, E)是n阶图，定义图的拉普拉斯矩阵Δ(G)为
定义5 如果图G中的任一顶点vi的筹码数ci小于其度数，博弈无法进行，称其处于稳定状态。如果图G可以达到稳定状态，称博弈是有限的；否则称博弈是无限的。
同一连通图G的初始筹码配置不同，博弈进程也会不同，这样博弈可能无限次发生，也可能是有限的。Klivans[13]给出了博弈的有限性与初始筹码数、边数和顶点数的关系。
定理1[13] 如果无向连通图G=(V, E), 其中|V|=n, |E|=m且图G的总筹码数为N，那么
(1) 若N>2m-n，则图G上的博弈是无限的；
(2) 若N < m，则图G上的博弈是有限的；
(3) 若m≤N≤2m-n，则博弈可能有限，也可能无限。
定理2[12] 如果无向连通图G上的每个点均被分发过至少一次，那么博弈次数是无限的。
定理1的证明显示，对于一般的图G，当筹码总数m≤N≤2m-n时，该图博弈的有限性不仅与筹码总数相关，也与筹码的初始配置相关。本文将给出完全二部图上的博弈有限性由初始配置和筹码总数决定的充要条件。
2 完全二部图上的筹码分发博弈
完全二部图的特点是一部图的每一个顶点与另一部图的任一顶点都相连，当一个顶点被分发时，另一部的每个顶点均接受一个筹码。设完全二部图G=(V, E)，用点集A, B表示图G的两部顶点，即V=A∪B，A∩B=ϕ，|A|=p, |B|=q，并且记A={v1, v2, …, vp}，B={vp+1, vp+2, …, vp+q}。
例1 如图 1 ，顶点数n=7，边数m=12，其不确定区间为[12, 17]，设总筹码数N=15。该图的博弈过程如图 2 所示。
分发过程如下：图 2(a) 中数字为初始配置的筹码数，分发第三个顶点得到图 2(b) ，再依次往下分发。上述博弈过程显示，顶点v7分发后，图上每个顶点的筹码数都小于其度数，达到稳定状态。因此，该博弈是有限的。
如果完全二部图的其中一部只含1个顶点，即V={v0}∪{v1, v2, …, vn}(n≥1)，那么该图的边数m=n。由定理1知，若总筹码数N < n，博弈总是有限的；若N>n，博弈总是无限的；如果N=n，无论初始配置如何，经过若干次分发后，顶点v0的筹码数总可以达到n，接着分发顶点v0，其他顶点均可得到一个筹码，这样所有顶点均可至少分发一次。由定理2可知，该博弈是无限的。下文所讨论的完全二部图的每一部顶点数都不小于2。
定义6 若一个二部图的筹码配置为
定义映射σ, τ：$\mathbb{Z}_{\geqslant 0} \rightarrow \mathbb{Z}_{\geqslant 0}$ ，使得
且τ(ci)=mod (ci, deg (vi))。为叙述方便，记
由上述定义可知，σ(ci)为顶点vi在配置c下可连续分发的次数，τ(ci)为顶点vi在配置c下连续分发σ(ci)次后剩余的筹码数。例如，在图 1 所给的初始配置c =(0, 1, 5, 0, 1, 4, 4)下，σ(c)=(σ(c1), σ(c2), …, σ(cp+q))=(0, 0, 1, 0, 0, 1, 1)。
此时，v3, v6, v7可分发1次
这就表明v3, v6或v7在配置c下分发1次后剩余的筹码数为1。
定理3 设图G=(V, E)，其顶点集V=A∪B，A∩B=ϕ，|A|=p，|B|=q，如果顶点vi, vj属于同一部，在配置c =(c1, c2, …, cp+q)下，τ(ci)=τ(cj)，经过若干次分发后，筹码配置变为d =(d1, d2, …, dp+q)，则τ(di)=τ(dj)。
证明：不妨设vi, vj∈A，由于A中的一个顶点v分发时，共输出deg(v)整数倍个筹码，因此τ(vi)和τ(vj)的值始终不变。由|A|=p, |B|=q可知，deg(vi)=deg(vj)=q, deg(vk)=p。
根据σ, τ定义，在配置c =(c1, c2, …, cp+q)下
若对B中的顶点vk进行分发，vi, vj的筹码数各增加1个，此时
或
因此，τ(bi)=τ(bj)。
定义7[13] 设有图G=(V, E)且|V|=n，Δ(G)为其拉普拉斯矩阵，c, d为$\mathbb{Z}_{\geqslant 0}^n$ 中的向量，若d-c =Δ(G) z，z ∈ $\mathbb{Z}_{\geqslant 0}^n$ ，则称d与c是等价的，记作d ~ c。
参考此等价定义，本文针对完全二部图提出了一个新的等价定义。
定义8 设G=(V，E)为完全二部图，有两个筹码配置b =(b1, b2, …, bp+q)和c =(c1, c2, …, cp+q)∈ $\mathbb{Z}_{\geqslant 0}^n$ 。如果
并且存在置换δ1, δ2∈Sp和δ3, δ4∈Sq，满足
和
则称配置b和c是等价的。
注意到定义8的等价包含在定义7中。
引理1 设完全二部图G=(V，E)上两种初始筹码配置是等价的，则其博弈的有限性相同。若博弈有限，则达到稳定后所分发的次数相等。
证明：若完全二部图G=(V，E)，V=A∪B且A∩B=ϕ，A(B)中顶点分发1次时，则B(A)中顶点均接受1个筹码。假设初始筹码配置为b =(b1, b2, …, bp+q)，c =(c1, c2, …, cp+q)∈ $\mathbb{Z}^{p+q} _{\geqslant 0}$ 等价。在初始配置b下对A部顶点分发$\sum\limits_{i=1}^p \sigma\left(b_i\right)$ 次，对B部顶点分发$\sum\limits_{i=p+1}^{p+q} \sigma\left(b_i\right)$ 次，得到配置
类似地，在该配置下对A部顶点分发$\sum\limits_{i=1}^p \sigma\left(c_i\right)$ 次，对B部顶点分发$\sum\limits_{i=p+1}^{p+q} \sigma\left(c_i\right)$ 次得到配置
则存在置换δ1, δ2∈Sp和δ3, δ4∈Sq，满足
和
从而在不考虑顶点顺序的情况下，配置b′, c′筹码分布相同。因此，定理成立。
引理2 若一个完全二部图的博弈次数有限，某一配置的筹码数为c =(c1, c2, …, cp+q)，则有$\sum\limits_{i=1}^p \sigma\left(c_i\right)<p$ 且$\sum\limits_{i=p+1}^{p+q} \sigma\left(c_i\right)<q$ ，即该配置下相同度数的顶点能分发的次数之和小于其度数。
证明：假设$\sum\limits_{i=1}^p \sigma\left(c_i\right)=p$ ，A部顶点可连续分发p次，则B部顶点均接受p个筹码，从而对$\forall v_j \in B$ ，均有σ(cj+p)≥1。此时，B中顶点都可分发，从而所有顶点均可分发1次，由定理2知，博弈无限。同理，$\sum\limits_{i=p+1}^{p+q} \sigma\left(c_i\right)=q$ 时，博弈也无限。与假设矛盾，定理得证。
定理4 设完全二部图G=(V，E)，初始配置为c =(c1, c2, …, cp+q)，若其博弈次数有限，则对$\forall v_i \in V$ ，vi在整个博弈中所分发的次数不超过σ(ci)+1次。
证明：假设vi∈A在博弈进程中共分发了σ(ci)+2次。由于ci=σ(ci)deg(vi)+τ(ci)，顶点vi可连续分发σ(ci)次，此时vi的筹码数为τ(ci) < q。因为vi还需分发两次，所以vi需要从B中吸收至少2q-τ(ci)>q个筹码。这样，必然使得A中其他顶点至少能分发1次，由引理2可知，该配置下的博弈次数无限，与假设矛盾。
定义9 若一个完全二部图的初始筹码分布为c =(c1, c2, …, cp+q)，定义以下记号：
在以上定义中规定，若i < j，则τ(Ai) < τ(Aj), τ(Bi) < τ(Bj)。
该定义将A部顶点按函数τ分为s个，B部顶点分为t个。
根据二部图顶点的筹码配置，文献[13]对顶点作出如下定义。
定义10 当1≤i≤s-1时，若τ(Ai+1)-τ(Ai)≥2，则称Ai是断层的；当i=s时，若deg(v)- τ(As)≥2, v∈A，则称As是断层的；Bi(1≤i≤t)断层的定义亦如此。
例2 在例1中的初始筹码分布下，对于上面一部顶点，有
对于下面一部顶点有
因为
所以A2, B2是断层的，A1, B1不是断层的。
定义11 对于vi∈V，且该顶点的筹码数满足τ(ci)=deg (vi)-1，称vi是准分发点，vi所在的点子集称为准分发点集。
引理3 若一个完全二部图不存在断层点子集，则博弈次数无限。
证明： 若完全二部图不存在断层点子集，则由定义9可知，A的子集满足
B的子集满足
在初始筹码配置下，必有$\sum\limits_{i=1}^{p+q} \sigma\left(c_i\right) \geqslant 1$ ，否则初始筹码分布就是一个稳定的状态。那么，一定存在可分发的点子集Ai(或Bj)，该点集的某一顶点分发后，会使得准分发点集Bt(或As)变成可分发的；同时，可生成新的准分发点集As-1(或Bt-1)。以此类推，初始配置下最小的τ(ci)对应的顶点vi也被分发，此时图上的所有顶点均被分发过，由定理2可知，博弈次数无限。
完全二部图博弈次数有限的一个必要条件是点集A和B至少存在一个断层的子集。由引理1知对任意初始配置c，存在与之等价的配置b，且在配置b下，可分发的点只集中在As中。由引理3可知，两种配置下博弈的有限性是一样的。例如，图 3(a) 中筹码数为4和6的点均可分发一次，然后这两个顶点分别将其4个筹码转移到同一部的τ(ci)最大的顶点上。
定理5 设完全二部图G=(V, E)，顶点集满足V=A∪B，|A|=p，|B|=q；并且A、B两部顶点按τ函数分别写为无交并，即
假设图G上初始配置c =(c1, c2, …, cp+q)，博弈有限当且仅当存在u, w∈ $\mathbb{Z}_{>0}$ ，Au是断层的且满足
或存在u, w∈ $\mathbb{Z}_{>0}$ ，Bw是断层的且满足
证明: 若在初始配置下存在可分发的B部顶点，将这些顶点全部分发直到对任意vi∈B，其筹码数小于度数，即不可再分发。此时，只有A部顶点可分发。因此，不妨设初始配置c =(c1, c2, …, cp+q)，只有A部顶点可分发，如图 4(a) 所示。
先证必要性。A上的点分发$\sum\limits_{i=1}^p \sigma\left(c_i\right)$ 次，使Bt, Bt-1, …变为可分发点集，记Γ1，如图 4(b) 。此过程中，B上每个顶点接收$\sum\limits_{i=1}^p \sigma\left(c_i\right)$ 个筹码。由引理2知，$\sum\limits_{i=1}^p \sigma\left(c_i\right)<p$ 。分发Γ1中的点，使As, As-1, …变为可分发点集，记作Η1，如图 4(c) 。分发Γ1上的顶点，其每个点发射p个筹码，此时Γ1上的余数变为
由于
因此，Γ1中顶点的余数均小于B1中的。由定理2知，在以后的博弈进程中，Γ1中的点不会第二次被分发。分发Η1中的顶点，使得B中一部分顶点变为可分发点，将这些点集记作Γ2，如图 4(d) 。重复上述过程，得到一系列A和B的子集族Η={Η1, Η2, …, Ηm}和Γ={Γ1, Γ2, …, Γn}，如图 4(e) 、(f) 所示。
情况1 分发Γn中的顶点，Au不可分发，博弈结束，Ηm={Au+1, Au+2, …}，Γn={Bw+1, Bw+2, …}。此时
情况2 分发Ηm中的顶点，Bw不可分发，博弈结束，Hm={Au+1, Au+2, …}，Γn={Bw+1, Bw+2, …}。此时
因此必要性成立。
再证明充分性。若初始配置满足式(1)、(2), 则将初始配置下的A分发$\sum\limits_{i=1}^p \sigma\left(c_i\right)$ 次后，随着博弈的进行，B上的顶点一共从A中吸收$\sum\limits_{i=1}^p \sigma\left(c_i\right)+\left|A_{u+1}\right|+\cdots+\left|A_s\right|$ 个筹码。由式(2)知，这些筹码恰好使得Bw+1中的顶点分发而不会使Bw分发。式(1)能够使得Bw+1分发结束后，V上不含有可分发点，博弈结束，因此博弈次数有限。同理，若初始配置满足式(3)、(4), 博弈也有限。
3 结束语
本文根据完全二部图上点的初始配置数，将完全二部图的顶点进行分类，通过定义函数σ(ci)、τ(ci)和断层等解决了完全二部图分发次数有限的充要条件。