论文部分内容阅读
图上的沙堆模型是研究自组织临界现象的一个很重要的模型，沙堆模型是在代数与图论的基础上进行研究的，具有广泛的应用.图上沙堆模型中的循环态构成了一个有限交换群，也称为沙堆群.沙堆群有其丰富的数学结构和代数结构.沙堆群中的重要组成元素-循环态与极小循环态有一些很完美的性质.根据循环态与parking函数的关系，B.Benson和P.Tetali已经给出了任意非极大G-parking函数g是在其控制下的极大Parking函数f的交.本文推广了此文献中的结论:得到了非极小循环态是若干个不大于它的极小循环态的并，且这样的极小循环态个数至多为|V(G)|-1个;另外，根据图的有唯一源点的无圈定向与极小循环态的一一对应关系[4]以及燃烧算法[8]，本文得到了一些图运算的循环态与极小循环态.具体得到如下结论:
(1)任意图的非极小循环态是若干个不大于它的极小循环态的并，且这样的极小循环态个数至多为|V(G)|-1个.设u是图G的任一个循环态用Rumin表示不大于u的极小循环态的集合，则结论可表示为:u=(V)c∈RuminC
(2)图G的极小循环态可以用删除与收缩一条与根点相邻的边e={q，s}后图的极小循环态表示:Rmin(G)=Rsumin(G)URmin(G-e)，其中Rsmin(G)表示在点s处沙粒数为d(s)-1的图G极小循环态的集合，Rmin(G-e)表示图G-e的极小循环态集.
(3)分割图G的任一一条边e={s，t}后得到新图记为图H，则图H的极小循环态可以表示为:Rmin（H）=R1UR2.其中R1是满足c’(v)={1， v=w;c（v），其他.图H的所有极小循环态构成的集合.R2是满足{c(t)+1，v=t且c（t)＜d（t)-1;c(v)=0， v=wc（v），其他.图H的所有极小循环态的集合.c是图G的任意一个极小循环态.
(4)图G的循环态可以用删除与收缩一条与根点相邻的边e={q，s}后图的循环态表示为:R(G)=(R）1U R(G-e).其中（R）1是在点s处沙粒数为d(s)-1循环态集，R(G-e)表示图G-e的循环态集.