论文部分内容阅读
图上的沙堆模型是研究自组织临界现象的一个很重要的模型,沙堆模型是在代数与图论的基础上进行研究的,具有广泛的应用.图上沙堆模型中的循环态构成了一个有限交换群,也称为沙堆群.沙堆群有其丰富的数学结构和代数结构.沙堆群中的重要组成元素-循环态与极小循环态有一些很完美的性质.根据循环态与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的循环态集.