（运筹学与控制论专业论文）手镯图的临界群.pdf

手饲图的临界群 中文摘要 连通图的临界群是图生成树数目的一个加细，它是定义在图上的一 个有限交换群其群结构是图的一个精细不变量，它与图的l a p l a c i a n 理 论密切相关本文主要研究手镯图g ，s 【( 1 2 ) 】，g ，s 【( 1 2 3 ) 】和圈与路图的积图 rx a 的临界群，得到了如下结论： ( 1 ) 手镯图的定义如下：给定常数p z 且p 2 给定整数n 3 和n 个 置换o 1 ，0 2 ，靠有n 个完全图n b ，不妨将它们以1 ，2 ，n 标号它们 之间按照如下的规则连边：将第 个凰中的顶点。与第( i + 1 ) 个中 的顶点0 d r ) 连边可以方便的认为行+ 1 = 1 这样我们就得到了手镯 图，记为g 。a p l ，0 2 ，】本文主要考虑盯= ( 1 2 ) 和0 - ；( 1 2 3 ) 时，手镯图 g s 【( 1 2 ) 】，g 。3 ( 1 2 3 ) 】的临界群结构为： ( n 1 ) 当n = 2 m 且3 t 竹时，g ，3 【( 1 2 ) 】的临界群为z ( 。h ) o ( z 。) 2 0 z o z 纽珥当n = 2 m 且3 i n 时，瓯，3 【( 1 2 ) 】的临界群为z i 埤止o ( z 。) 2o z 2 l ho z 型9 4 这里如= 5 s , 一l 一- 2 ，初值为：8 0 = 0 ，s l = 1 n t ( n 2 ) 当n = 2 m + l 且3 十馆时，g 3 【( 1 2 ) 】的临界群为z ( 。，。) o z 。o z 丧訾 当n ；2 m + 1 且3 i n 时，g ，3 【( 1 2 ) 】的临界群为z 虹吐。瓦。o z 触这里 s n = 5 s n l 一8 n - - 2 ，初值为：8 0 = 0 ，s l = 1 ( 6 1 ) 当n = 3 k 且n = 2 m 时，g ，3 【( 1 2 3 ) 】的临界群为z 虹鳓o ( 瓦。) 2o z 2 l h o z 挚! i 这里= 5 s 。一1 一- 2 初值为：印= 0 ，s l = 1 n m j ( 6 2 ) 当n = 3 k 且n = 2 m + 1 时，g ，3 【( 1 2 3 ) 】的临界群为z i 埠吐o ( z 。) 2 0 。o z 当4 这里，v n = 5 v , 一1 一一2 ，初值为：v o = 1 ，仇= 6 硬士学位论文 ( 6 3 ) 当n = 3 k + 1 或n = 3 k + 2 时，g ，3 【( 1 2 3 ) 】临界群为：z 加m ) o z 。o z 虹这里t ，i = 5 一l t ，i 一2 1 ，初值为u o = 1 ，u l = 2 ( 2 ) r q 的临界群结构为：当n 2 时，有 舻 = ：= j ) 兰：麓2 耋：淼 其中序列的定义为却= o ，s l = 1 ，如= 6 s 。一l 一一2 2 ) ；序列k 的定义 为i o = o ，t l = 1 ，“= 4 t 。一l 一“一2 2 ) 关键词：图的l a p l a c i a n 矩阵；临界群；沙堆群；矩阵的s m i t h 标准形；手 镯图 i i 手饲图的临界群 a b s t r a c t t h ec r i t i c a lg r o u po f ac o n n e c t e dg r a p hi saf i n i t ea b e l i a ng r o u pw h o s es t r u c t u r e i sas u b t l ei s o m o r p h i s mi n v a r i n n to ft h eg r a p h i ti sc l o s e l yc o n n e c t e dw i t ht h eg r a p h l a p l a c i a n i nt h i sp a p e r ，w ed e t e r m i n e dt h es t r u c t u r eo ft h ec r i t i c a lg r o u po nt h e c a r t e s i a np r o d u c t sg r a p hr qa n db r a c e l e t sg r a p hg 3 ( 1 2 ) 】a n d f ( 1 2 3 ) 】，w e p r o v e dt h a t ( 1 ) t h ec r i t i c a lg r o u po fb r a c e l e t sg r a p hg ，3 【( 1 2 ) 】a n dg ，3 【( 1 2 3 ) 】： ( d 1 ) f o re v e ni n t e g e rn = 2 m ，t h ec r i t i c a lg r o u po fg ，3 【( 1 2 ) 】i si s o m o r p h i c t oz ( n i m ) 。( z m ) 2 。z 。z 嚣哿w h e n3f 忆a n d z 虹弘。( ) 2 。z 2 l 坼。z 嚣哿 w h e n3 l n ( 口2 ) f o ro d di n t e g e rn = 2 m + l ，t h e c r i t i c a lg r o u po fg ，3 【( 1 2 ) 】i si s o m o r p h i c t oz o 。z 龋w h e n3tna n dz 掣。z 耥w h e n 3 1 - ，w h e r e 如= 5 s n 一1 一$ n - 2 ，w i t h i n i t i a lv a l u e ：8 0 = 0 ，8 l = 1 ( b 1 ) f o rn = 3 ka n dn = 2 m ，t h ec r i t i c a lg r o u po fg ，3 ( 1 2 3 ) 】i si s o m o r p h i c t oz 虹乒。( z h ) 2 。z 2 l 。z 嚣哿，w h e r e 知25 一l s n 一2 ，w i t hi n i t i a lv a l u e ： 8 0 = 0 8 1 = 1 ( 6 2 ) f o r n = 3 k a n d n = 2 m + l ，t h ec r i t i c a l g r o u po f g 。z ( 1 2 3 ) 1 i s i s o m o r p h i c t oz 虹弘。( ) 2 。z 3 。z 啬器，w h e r e 25 一l 一一2 ，w i t hi n i t i a lv a l u e ： v 0 = 1 ，t ，l = 6 ( 6 3 ) f o rn = 3 k + l o rn = 3 k + 2 ，t h ec r i t i c a lg r o u po fg o 【( 1 2 3 ) 1i si s o m o r p h i c t o z 扣，) oz t ，i o z 毒器，w h e r e u 25 u 一l t i 一2 1 ，w i t h i n i t i a l v a l u e u o 。1 ，n 1 2 2 i i i 硬士学位论文 ( 2 ) t h ec r i t i c a lg r o u po fr c 4 ： w h e nn 2 ，w eh a v e m 吲岂 乏= 盏兰i 羹：w h e n n i b s o d d w h e r et h es e q u e n c e 如i sd e f i n e d 硇s o = 0 ，8 1 = 1 ，如= 6 $ n 一1 一一2f o rm 2 ) ； a n ds e q u e n c e k i sd e f i n e d 船t o = 0 ，t l = 1 ，k = 4 t 一1 一k 一2 f o r 似2 ) k e yw o r d s ：g r a p hl a p l a c i a n ；c r i t i c a lg r o u p ；s a n d p i l eg r o u p ；t h es m i t h n o r m a lf o r m ；b r a c e l e t sg r a p h ； i v 手镯图的i 瞄界群 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不含任何 其他个人或集体已经发表或撰写过的作品成果对本文的研究做出重要 贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本声明 的法律结果由本人承担 学位论文作者签名t 渖堕j h 7 年 月沾日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅本人授权湖南师范大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文 本学位论文属于 1 、保密口，在一一一年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打“ ”) 作者签名；1 辛监 日期：2 u - 7 年，月日 导师签名吖毛煽吩日期孵妒棚 一4 9 手镯图的临界群 第一章综述 1 1自组织临界性与沙堆模型 大自然是如此的精彩，却又如此的神秘人们总希望能简洁，明快地描 述它和解决实际问题，并将复杂的事物和问题简单化，甚至在方法论上将 简单与科学之美联系在一起，把简单性作为科学追求的目标之一，但也不 得不承认现实世界的复杂性，而复杂的世界是不能简单的归结为几个已 知的原理和定理的现代科技发展的历史表明，要在复杂的世界中求得生 存，就必须对复杂系统进行深入的研究而非线性正是构成复杂世界的核 心和关键因素，研究复杂性态和复杂系统的科学潮流开始形成并迅速发 展，非线性系统与复杂性态研究成了现代科学的主题之一 自组织临界性作为观察大自然的一种新方法应运而生自组织临界 性( s e l f - o r g a n i z e dc r i t i c a l i t y ，简称s o c ) 的概念是由美国布鲁克海汶实验室 三位年轻的博士后b a kp ，t a n gc 和w i e s e n f e l dk 于1 9 8 7 年为解释非线性 复杂系统无序的行为特征而提出的【1 ，2 】他们发现存在一类耗散的连续 系统，即包含了成千上万个发生短程相互作用组元的复合系统，在特定的 条件下，系统将自动演化，最终达到一个临界的稳定态，他们把它叫做自组 织临界态在此状态下，由外部流入系统的能量，按系统的组元的内在规 律相互作用( 即自组织) 的结果而被系统吸收和耗散掉，系统的能量状态 平均值在某一个临界值附近呈无规律的变化，在自组织临界状态下，小事 件引起的连锁反应能够对系统中任何数目( 包括大数目) 的组元产生影 响，从而可能导致大规模事件( 大灾难) 的发生虽然复合系统发生的小 事件比大规模事件多，但是遍及所有规模的连锁反应是动态特性的一个 必不可少的部分，根据此理论，小事件与大事件的发生都起因于同一种机 制b a k 等人认为，自组织临界状态理论属于整体理论，即它所描述的总体 特征( 如大、小事件的相对数量) 不取决于微观机制因此，不能通过分 别分析系统中的各个部分去了解其总体特征，它是使整体理论适用于动 态系统的模型或数学描述 硕士学位论文 s o c 作为大自然复杂行为中的一种新的物理规律涉及到自然界中非 常广泛的现象：地震，森林火灾，雪崩，大脑和神经网络，生物种类多样性， 疾病的传播，战争，股票波动等研究这些现象的共同规律是具有重大的科 学与实际意义的 ”沙堆模型，( s a n d p i l em o d e l ) 是自组织临界状态的一个典型模型，近来 受到特别的重视，以至著名物理学家诺贝尔得主d eg e n n e s 在谈到凝聚态 物理的不同层次时就提出过”回到沙堆中去”的想法他认为”一个沙丘 与银河系或原子核同样可以作为漂亮的研究课题” 沙堆模型是b a k 等在1 9 8 7 年首先提出来的【l 】：考虑放一个平整的台 子，把沙缓缓地加到台子上，而且每次只加一粒沙沙粒可以被加到任意 的位置上，或者只加到在某个点上，如台子的中心台子的这种平坦的状 态就代表了一种普遍的平衡态，这个平衡态具有最低能量最初，沙粒或 多或少地会停留在它们落下的位置上当我们不断加进沙子的时候沙堆 会变得陡峭起来，并且小沙粒会滑动起来或者说雪崩发生了沙粒会附在 其他沙粒的顶部，同时跌到一个较低的层次这个过程也会使其他沙粒轮 流倒塌一粒沙的加入只会导致一个局域的扰动，而对沙堆来说不会有任 何戏剧性的事情发生尤其值得注意的是，沙堆的某个部分所发生的事不 会影响位于沙堆较远部分的沙粒在这个阶段，沙堆内部并不存在整体的 交流，而只是一些个别沙粒之间的交流但是当沙堆变得更为陡峭的时候， 一粒沙就有可能使其他沙粒倒塌最终，当沙堆的陡峭到达一定程度的时 候，沙堆就不可能再增长了，因为平均来看加到沙堆上的沙的数量与从沙 堆边缘上掉下的沙的数量是相等的这就成为一个稳定态，因为随着时间 的增长，沙的平均数量与沙堆的平均斜率都趋于常数很明显，为了具有 这种平衡，也就是加到沙堆上的沙，如加到中间的，和从边缘落下去的沙之 间的平衡，那么整个系统内部必定存在着交流偶尔，整个沙堆也有雪崩 事件插进来这就是自组织临界( s o c ) 态 2 手镯图的临界群 1 2 图的临界群 图的临界群( c r i t i c a lg r o u p ) 就源于自组织临界态的研充它具有丰 富的数学结构和多种不同的表现形式l o v 缸z 和b i g g s 从不同的数学角度 ( c h i pf i r i n gg a m e ) 进行了研究【3 】i 但尚有许多的问题等待研究，如给出一 个图，如何求出它的临界群这一基本问题，目前还只对某些非常特殊的图 类能确定它的临界群图的临界群的研究不仅与自组织临界态的研究有 关而且在理论计算机的研究中有着重要的作用它潜在的a b e l i a u 结构被 d h a r 【4 】和c r e u t z 5 】所发现特别地，这个群的阶恰好是图的生成树数目【4 1 ， 且有两个基本的双射存在从纯数学上来看，图的临界群可以认为是图的 生成树数目的一个加细，即在图的生成树集上定义一个群结构，便可以利 用有限群的理论来研究图的生成树的数目图的临界群的单位元的临界 状态表示具有很有趣的分形结构这些都值得我们去研究 s a n d p i l e 模型可看作是在一个根图( 取一个顶点为根的连通图) g 上一 个元胞自动机( c e l la u t o m a t o n ) ，这个自动机上的细胞对应图g 上顶点每 个顶点上指定一个数，这个自动机的转换由以下，倒塌规则”给出：当顶点 上指定的数大于它在图g 上的度数时，会发生倒塌，把这个顶点上的数分 别指定到它的每个邻点上，这时，此顶点上的数减少了度数个，而它的邻点 均增加1 根r 不会倒塌，可以看作是收集所有在系统中减少的数的顶点 令g = ( k e ) 是一多图，x = 钆x 2 ，z 。) 是顶点集，g 中顶点毛的 度记作也，d ( g ) = d i a g ( d l ，如，d 1 ) 是图g 的度矩阵，a ( g ) = ( 啦，) 是g 的 邻接矩阵，d = 。a q 如果一个多图其中有一顶点视为根，则此图是 根图若没有其他说明，我们假设给顶点适当标号，使得z 。是根本论文 中讨论的都是连通图 图g 的一个状态u 是以图的顶点集为指标集的整数向量，记作= “- ，t 2 ， ，其中地是分配给以的整数一个状态u 若满足t 也，“= 1 ，2 ，n ) 则称此状态是稳定态，一个状态缸是稳定的，在增加某些顶点 上指定的数后经过一系列倒塌仍回到原状态，则称此状态为临界态对任 意图g ，所有临界态的集合在二元运算o ( 直和) 下作成一个群耳( g ) ，我们 3 硬士学位论文 称( g ) 为临界群 状态以= ( 0 ，0 ，1 ，0 ，o ) ( 其中1 在i 位置上，i = 1 ，2 ，n ) 我们考虑 由和a 0 = 1 ，2 ，n ) 生成的舻的子群z x ( o ，靠) = x n ，a l ，2 ，。) ( 其中l = 函戤一1 9 如叼巧) ，注意到i g 。 = 0 ，所以a x ，2 ，n 是 线性相关的，可以去掉其中一个图g 的l a p l i a n 矩阵l ( g ) = d ( g ) - a ( g ) 在代数图论中，由矩阵树定理【6 】知，g 的生成树数目r ( g ) = ( 一1 ) d e t ( l ( g ) ) 玎 其中( l ( g ) ) 妤为矩阵l ( g ) 的元素的代数余子式这个定理的另一个表 达方式是商群z a ( g ，) 是有限的，且它的阶等于r ( g ) ，我们称此商群为 g 的临界群k ( g ) 临界群在代数中还有另一种表述：对于图g ，令m 是所有稳定态的 集合，在朋中定义一加j 去 运算o ，则m 在。下是一个半群，令k ( g ) 是朋唯一的极小理想，则k ( g ) 称为g 的临界群 临界群k ( g ) 也称为s a n d p i l e 群，p i c a r d 群，j a c o b i a n 群和树群【2 ，3 ，4 ，5 ， 7 ，8 ，它与图的l a p l a c i a n 理论 2 3 】密切相关将l ( g ) 看作映射矛+ z “， 它的余核形式为 c o k e r l ( g ) = z ”l ( g ) z 皇zo ( g ) 其中k ( g ) 称为图g 的临界群 关于图的临界群的研究已有的结论如下 ( 1 ) 格图r b 的临界群【4 】： k ( r 岛) 兰z 由o z 出 其中d = 篮号掣，如= g c d ( 脚+ l i + t ) 且脚和满足下面关系 = 三娑：二= 初始条件为_ 【o = = n = 0 ，p 1 = 1 ( 2 ) n 一轮图w 0 的临界群 s l ： 4 手饲图的临界群 当，l 为偶数时，耳( 0 ) 皇z 嘛o z 厶； 当n 为奇数时，k ( 仉名) 鲁z 厶一，+ 厶+ 。oz 一。+ “1 其中厶为f i b o n a c c i 数列 ( 3 ) b g 的临界群 9 】： ( 1 ) 当n = 2 m + 1 时，k ( 岛g ) 望z 扣h ) o z ho z 害鲁； ( 2 a ) 当n ；2 m 且m 是奇数时，k ( p 2 g ) 掣z ( n ，k ) o o z 害k ； ( 2 b ) 当n = 2 m 且m 是偶数时k ( 岛g ) 皇z 虹斟oz 2 k o z 粤k 其中k 定义为a o = 1 ，h l = 5 ，k = 4 一l k 一2 ；k 定义为= 0 ，k l = 1 ，j k = 4 k i n 一1 一j 一2 ( 4 ) 完全多部图的临界群【1 0 】： ( 。m ，m ) 笪o ( z n , z ) ”2 。g g z 。g h z0 z a n z 1 i ! 1 ) 利用的递归关系，对磊做 如下行变换 。”“ 晶2 ( 如：1 _ 川一( 裂o 1 。( ：一8 2 m 。、一( 。= ：；。l 。= = 二? 1 ) = ( 。一0 。坼1 i - l1 。 ks r 1 一s m l o 将r 的第三行乘以( 一3 ) 加到第行，又由注3 2 1 可得晶，f ：一生姿咝一举1 n 一宁虹1 产 2 3 一