足球比分直播

图上沙堆模型的循环态.pdf

返回
图上沙堆模型的循环态.pdf_第1页
第1页 / 共28页
图上沙堆模型的循环态.pdf_第2页
第2页 / 共28页
图上沙堆模型的循环态.pdf_第3页
第3页 / 共28页
图上沙堆模型的循环态.pdf_第4页
第4页 / 共28页
图上沙堆模型的循环态.pdf_第5页
第5页 / 共28页
点击查看更多>>
资源描述:
ABSTRACTThe sandpile model of a graph is an important one about the self-organizedcriticality phenomenon,It is studied based on algebra and graph theory and it WaSbeen widely applied in recent years.What is more,a fnite commutative groupWas constituted by the recurrent configuration of a graph,also known as sandpilegroup,which has its rich mathematical and algebra structure。As important elementsof the sandpile group-recurrent configurations have beautiful nature.B.Bensonand P.Tetali have obtained the conclusioneach non-maximal Gparking function gis the intersection of the maximal parking function{under their control of g.Inthis paper,We extend the conclusion and get the resultsevery non-minimal config-uration is the union of the minimum configurations which is not greater than thenon-minimal configuration,and also the number of minimum configurations is atmost l yGI-l;In addition,according to the one-to-one relationship of a uniquesource of acydic orientation graph and the minimum configurations[4】and also theburning algorithm[8],we have obtained the relationship of minimal recurrent config-uration,recurrent configuration for the operation of graphs,the conclusions are asfollows1every non-minimal configuration is the union of the minimum configura-tions which is not greater than the nonminimal configuration,and also the numberof minimum configurations is at most yGl一1.Let也be recurrent configurationsof a graph G,砩讥is the union of minimum configurations under the control of锃.We C8.工1 get the following conclusionU 2 C2The min-configurations of graph G Can be expressed by the graph whichdelete and contract the edge e{g,s,let焉讥Gis the rain-recurrent unionIVnV豫蚝图上沙堆模型的循环态which has ds一1 sands in vertex S,‰讥Geis the min-recurrent union ofgraph Ge.3We get new graph H by spliting any edge e{s,tof the graph G.Then therain-recurrent configurations can be expressed as‰伽日R1 u冗2.the element inR1 are as follow∞,‰,the element in R2 are as followf c亡17c,u{0,k,UWelse.4The configurations of graph G can be expressed by the graph which deleteand contrauct the edge e{g,s】.,let矗1 is the recurrent union of graph G which hasds一1 sands in vertex S,naeis the recurrent union of graph GeKeywordsSandpile model,recurrent configuration,minimal recurrent con-figuration,the operation of graphV目录中文摘要.I英文摘要.V1.综述..11.1引言11.2沙堆模型中基本概念..221.3已有的结论.41.4本文的主要工作.52.循环态与极小循环态.72.1基本定义与引理.72.2循环态是极小循环态的并83.图运算的极小循环态与循环态..133.1收缩与去掉与根点相邻的边e{q,s的极小循环态133.2分割图的任一一条边的极小循环态153.3收缩与去掉与根点相邻的边e{g,s的循环态184.结束语.22参考文献.24致谢.27学位论文原创性声明和版权使用授权书29图上沙堆模型的循环态1 综述1.1 引言图论是研究一些有相互关系的事物的一门学科,它用一些点来表示这些事物,用边来代表这些事物之间的联系或相互关系,比如任意的5个人,我们就可以用5个顶点来代表这5个人,他们之间任意两个人相互认识的话就在那两个与之对应的顶点之间连一条边,否则不连边.我们就用这种抽象图形来研究这些顶点与边之间的特性,从来研究与之对应的事物.图论作为数学的一个分支已有二百多年的历史,特别是在计算机出现以后,随着计算机的发展与推动下,图论也得到了迅速的发展,其应用也日趋广泛,比如在系统工程,通讯网络,运筹学以及社会科学等等方面.而代数图论是代数与图论相交叉结合的一门学科,也是近年来发展相当迅速的一个数学分支,主要通过建立图结构的代数表示,应用一些代数的理论来研究图结构的拓扑性质。他ilion群论,代数数论等数学分支联系密切,其中的沙堆群的理论是代数图论中一个相当重要的研究方向.他的研究与社会的发展有着重要的理论和现实意义。它不仅促进和丰富了图论和组合数学本身的研究,在化学,物理学,生物学,社会学,经济学,通讯以及工程建设等都有着广泛的应用.代数中群论的有关知识与图结合在一起考虑会呈现出一些优美的数学结构.其中,沙堆模型是建立在图论与代数基础上的经典模型.沙堆模型是一个沙堆形成和倒塌的模拟过程.比如用一个画满了小正方形格子的平面来表示沙堆所在的区域,每个小格子表示沙堆中的一个局部区域j而小格子中所给出的数字表示了这个局部地区的沙粒的数目.根据我们玩沙粒的经历,可以知道当沙堆堆到一定的高度时,便会发生一1一硕士学位论文倒塌.当某个小格子的沙粒超过一个特定的坍塌数值比如4,这个小格子中的沙粒会因为不稳定而会发生”沙崩”,所有的沙粒都会因为倒塌而平均流向相邻的格子中局部的”沙崩”会引起连锁的反应,可能会使得相邻格子的沙粒超过了倒塌数值发生倒塌,然后又继续影响它周围的格子.如此循环下去,我们这里的倒塌数值也就是该点所能承担的最大沙粒数,我们可以根据某一个沙崩影响格子的多少来定义一个沙崩的大小.当你不断的向这个”沙堆”加入沙粒,取决于沙堆的状态和沙粒添加的位置,倒塌会不断的产生,不停的演化.这是一个很简单的模型,但有很大的普遍性,比如说如果认为地震过程也只是地壳间的摩擦碰撞,地震的发生就遵循着与沙堆模型同样的规律.另外现实中的森林火灾,泥石流,山洪暴发,交通堵塞等都遵循沙堆模型中的倒塌规律.在沙堆模型动力学背后,蕴藏着自组织临界性的思想。早在1987年,美国的三位科学家Bak,Tang与Wiesenfeld等就提出了自组织临界性理论【2】.这是一个有趣且普遍适用于动力系统的理论,它的出现几乎解决了所有的动力学问题.该理论认为一类由多个组元相互作用的、远离平衡的、开放的且具有动力学特征的复杂系统,各个组元相互作用。在不需要外部干涉、引导的情况下会自动演化为临界状态,也称为是循环态,当系统达到临界状态时,任何一个小的扰动,比如加一粒沙,其所发生的效应都会扩展到整个复杂的系统,所引起的后果是不可预测的.作为当今非平衡统计物理学的最基本概念之一启组织I临界性理论解释了大自然为什么是一种复杂的机制,并描述了了所形成的简单的规则通过相互作用网络的蔓延和反馈从而涌现出复杂的特征.自组织临界态中的经典模型就是我们所说的沙堆模型.沙堆模型中的循环态构成了沙堆群,也称为有限交换群或者临界群.沙堆模型有其丰富的数学结构和不同的表达式,Biggs[17]从不同的角度出发,给出了沙堆群的代数组合结构.随后,Dhar和Creutz[8]发现了沙堆群的Abelian结构,从组合数图上沙堆模型的循环态学的观点看,从这个结构中得到了临界群的阶数等于图的生成树数目,体现了沙堆模型的完美性质.在文献[191、【20】、【21】、【22】中,侯耀平教授刻画了一些有意义的图的沙堆模型的临界群结构,更多沙堆模型中沙堆群的完美结构,在文献【9]、[10】、[11]、【14】、[15】、【18】都给出了详细的介绍.沙堆模型中的循环态有其特殊的性质,在倒塌规则的作用下,临界状态下的沙粒的倒塌个数遵从漂亮的数学规律,文献【3】中给出了完全图、圈以及棒棒糖图的倒塌多项式.同时还得到了特殊的组成元一极小循环态与图的无圈定向之间的一一对应关系f4】.这些都是一些特殊图上沙堆群的循环态结构.那么对于一般图的循环态与极小循环态是否也有一些很好的规律,这是本文要解决的一大问题.此外,根据文献[51中图的任意非极大Gparking函数g是在其控制下的极大Parking函数f的交,在此结论的基础上,本文对此结论进行了推广.1.2 沙堆群的基本概念在现实生活中,很多问题都可以简化为一个图形来描述,比如说各个国家之间的贸易往来关系,可以用点表示这些国家用线来表示国家之间的某些关系.设GK q,E是一个简单连通图,其中yq,钉,,V2,,%,q是图G的根点,EG是边集.e{Vi,%的端点为吣uj的边。对有向图用矿%表示以点矾为起点的有向边的数目,称作点饥的出度;用d一吼表示以点仇为终点的有向边的数目,称作点Vi的入度,d%表示点V。在图G中的度有时候为避免混淆用dG%表示点忱在图G中的度.对于定向图中的任一点%都有dqd一uidv;成立.非负整数向量U让秒,,让晚,...,仳%称为图G上的Abelian沙堆模型的一个态,也称为图G的一个态,它是从顶点集y到自然数集Ⅳ的映射,直观的说,u%表示在点%处的沙粒数,若点仇满足u忱dGv;,则称点q是稳定点.若对Vi∈{1,2,,n},有弘%dcvt,则称U是稳定.3一硕士学位论文态.若有札仇≥dcv。,则称点忱是不稳定点.此时,点%便会按照下面的倒塌规则进行倒塌.倒塌规则若存在不稳定点饥≠q,那么点Vi即会发生倒塌,使得该点的每个邻点都获得一个沙粒,同时点仇上的沙粒数就会减少dcv;,也就是说口果存在不稳定的顶点,那么该点就会倒塌,但是点q不会发生倒塌,它是这个模型的边界,吸收来自它邻点的沙粒.最终使得这些被吸收的沙粒离开这个模型,经过一系列的倒塌后回到稳定态,倒塌停止.所有的不稳定态都可以通过不断倒塌不稳定的顶点最终得到稳定态,且得到的稳定态与顶点倒塌的顺序没有关系.但并不是所有的稳定态都能由不稳定态倒塌得到,例如态乱0,0,,o就不能由任何一个不稳定态得到.在稳定态中,只有一部分U在某些顶点上增加一些沙粒数后经过一系列的倒塌又回到稳定态牡,这部分的特殊稳定态称为循环态.循环态在沙堆模型中具有重要的作用和很好的代数性质,他们构成了一个有限交换群,也称为图的沙堆群.对图G的所有循环态组成的集合记为冗G.Dhar在文献[41 c0给出了判定一个稳定态U是否为循环态的有效方法,称为燃烧算法.燃烧算法【8】任取图G一个稳定态U,在顶点q的每个邻点上都加一个沙粒,按照上面的倒塌规则,除去点口外,若每个顶点都恰好倒塌一次最后又回到态珏,则珏是图G的循环态.1.3 已有的结论循环态是沙堆群的重要组成元素,有很多完美的性质,在文献【3】给出了树、圈、完全图以及lollypop图的循环态结构圈G。的循环态结构为1n表示由n个1组成的一个态和ln一,o表示由n-1个1和1个0组成的态,一共有n1个.一4一图上沙堆模型的循环态文献14]给出了图的任一极小循环态与图G的有唯一源点的无圈定向之间的一一对应关系一个态让∈%伽G是图的一个极小循环态当且仅当存在图G的有唯一源点q的无圈定向与之对应,使得对任一的u∈yG,有仳udu.文献【5]中已经给出了极大Gparking函数集与图G的有唯一源点g的无圈定向集之间的一一对应关系,非极大parking函数g与在g控制下的极大parkin9函数f2_1;3的运算关系非极大parking函数9与在g控制下的极大p口r兢纷9函数,之间的运算关系即9入lICE9其中B表示在g控制下的极大parking函数,的集合.1.4 本文的主要工作在参阅了大量的文献后,本文根据循环态与parking-麈]数的对应关系,对己有结论进行了推广,然后根据前面结论的思想对一般的图运算的循环态以及极小循环态进行了探讨,得到下面的结论1任意图的非极小循环态是若干个不大于它的极小循环态的并,且这样的极小循环态个数至多为IyGl_1个.设牡是图G的任一个循环态,用磁。礼表示不大于u的极小循环态的集合,则结论可表示为链V cc∈j喘‘n2图G的极小循环态可以用删除与收缩一条与根点相邻的边e{q,s].后图的极小循环态表示‰讯G%概GU%伽Ge,其中蠕协G表示在点s处沙粒数为ds一l的图G极小循环态的集合,Rm伽Ge表示图Ge的极小循环态集.一5一硕士学位论文3分割图G的任一一条边e{s,亡后得到新图记为图H,则图H的极小循环态可以表示为Rm讥日R。U R2.其中R,是满足m‰,措;图H的所有极小循环态构成的集合.R。是满足f c£1,钞蛆c£dt一1;c,u{0, uWI cu, 其他.图H的所有极小循环态的集合.c是图G的任意一个极小循环态.4图G的循环态可以用删除与收缩一条与根点相邻的边e{q,s后图的循环态表示为RG袁,URGe.其中矗。是在点s处沙粒数为ds一1循环态集,RGe表示图Ge的循环态集,一6一图上沙堆模型的循环态2 循环态与极小循环态2.1 基本定义与引理循环态与极小循环态的是沙堆群中的重要组成元素,在沙堆模型中扮演着重要的角色,有很多完美的性质.但这些性质都是他们各自的一些特征,那么循环态与极小循环态之间是否也存在某些关系.本章主要介绍了沙堆模型中非极小循环态是不大于它的极小循环态的并,且这些极小循环态的个数至多有Iva一1f个.下面给出本章节用到的基本引理和定义.定义2.1【4】设札是图GV q,E的一个循环态,.厂秽1,”2,,‰是图G关于循环态乱的一个倒塌序列.定义一个燃烧图G,U q,F,其中E,{虢斗%I{Vi,%∈EAiJU{g,u№,钉}∈E其中i_歹表示点忱在%之前倒塌,A表示交即多个条件同时满足.根据燃烧图的定义可知,循环态的燃烧图不唯一且是一个无圈定向图.燃烧图的个数与循环态的倒塌序列个数相同.这个定义在本篇文章中有重要的作用,根据下面的图形来说明循环态与燃烧图的关系.如图1所示,给定图1的一个循环态让2,1,1,在燃烧算法下有不同的倒塌序列、如,图2是与倒塌序列.fi1,2,3对应的燃烧图.图3是与倒塌序列止1,3,2对应的燃烧图.这两个图都是图l对应的有唯一源点的无圈定向图.27一图3
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播