（应用数学专业论文）图的临界群研究.pdf

摘要 摘要 图g 的l a p l a c i a n 矩阵l ( g ) 是研究图的性质的一个重要工具人们传统上 用l ( g ) 的特征值来研究图论，得到很多很好的结论近二十年来，人们发现l ( g ) 的s m i t h 标准型和特征值一样，同为图的同构精细不变量，自然也是研究图论 的好工具作者最早接触到的临界群概念，是源自g o d s i l 和r o y l e 的著作g t m 2 0 7 国际著名数学家b i g g s 在1 9 9 9 年的时候证明了图的临界群能够被l ( g ) 的 s m i t h 标准型所刻划本文研究了两类c a r t e s i a n 乘积图g 和a c _ 的 l a p l a c i a n 矩阵，得到了它们的s m i t h 标准型，给出了这两类图的临界详细群结构 和生成树数目对于一般化的图，我们给出了其s m i t h 标准型的前三个不变因子 的精确上界 下面的是本篇论文得到的主要结果，其中的参数在正文对应部分都有详细的 介绍 若礼= 2 s + l ，则g ( m ，礼3 ) 的临界群为 五n ，如) o 磊。o 面。o o 磊巳。乙of z m h so o k ，o 乙， - _ _ - _ - _ o 、j _ - _ _ _ _ ，1 - - - _ _ _ - _ _ _ j - - - _ _ - _ - o ， 其中一= 而h 8 ( 珏，) ，妒= 丽n m h 万s 若礼= 2 s ，则g ( m ，n 3 ) 的临界群为 互2 n ) o 么。乙m ，2 ) 钍。o o 互m ，2 ) 珏。o 磊。乙o & o o 么o 么， 、_ - - l _ l l - _ i 、j _ - _ _ l l l _ _ i _ - ，l - _ _ l 、，l _ - o r m - 3 m 一3 其中 广让s 【n ，缸8 ，4 丁8 j 2 芒r ， f u 。2 l 1 叼= 坐菘n 糍4 t s 掣) ， 【，乱s ， p = 坠瓮辫，i 佗，一4 j l m ，z ) x = 糌， ，n m ( m + 4 ) u 5，：= ( m n ，( m + 4 ) u ，2 n ) 摘要 由此得到g 的支撑树的数口为 熹( ( 翌尘生兰譬) n + ( ! _ 二生雩) n 一2 ) m 一1 若n = 2 s + 1 ，则a c km 3 ) 的临界群为 级撕，k ) o s ，a ) 。z 错。级。z n 嘴渊。z 踽。z 两 l，一， jl n o 儿 j ， oj、 5 ， 5 ，肌a 4 ， 0 ， 若孔= 2 s 且s 为奇数，则q g 3 ) 的临界群为 z ( 舭，1 ) 。z ( ，i ) 。z 獬 z e e 。j。z 黜i s )。z 耥。z 融 j t，o ，l j te 儿e 8 c 0 j j5 e s ，4 j d 0 4 j ， 若n = 2 s 且s 为偶数，则a g ( 佗3 ) 的临界群为 缸舭， ) 。反e ，厶) 。z 等高将俨。磊e 。z 号黯e 最s ) 鼎。z 舶。z t s e s 当s ，8 ，jj to ，0 jo a ，j ， 5 j 4 ，o ， 由此得到图仅g 的支撑树的数目为 嚣( ( 锈+ 1 ) n 一( 锯一1 ) - - 1 ) 4 。( ( 讵+ 1 ) n 一( 钷一1 ) - - 1 ) 2 ，若n 为奇数； l - 南( ( 佰+ 1 ) n 一( 镛一1 ) n ) 4 ( ( 以+ 1 ) n 一( 钜一1 ) n ) 2 ， 若礼为偶数 从而证明了当礼 3 时有以下三角函数恒等式成立 t l 一1 兀i4 j = l 菇1 【( 2 2c o s 号 4 ( 此外，对仃5 阶的简单连通非完全图g ，还得到了它的第三位不变因子的 定位：8 3 ( g ) 并且8 3 ( g ) = n 当且仅当g = 一e ，其中e 的任意一条边； 8 3 ( g ) = 礼一1 当且仅当g = 口一l ，其中7 t 5 且g 由完全图一l 连接一个 垂点2 ，所得；s a ( g ) = 扎一2 当且仅当佗= 5 且g = 熄一2 e ，其由凰删除两条不相 邻的边所得，或g = 磁一q ，其由蚝删除长为4 的圈的边所得；8 3 ( g ) = 礼一3 当 且仅当g 为下述六种图之一：鲍，3 ，蚝一g ，甄一伤，硒一2 岛，凰，3 及坼一凰，3 关键词：l a p l a c i a n 矩阵，s m i t h 标准型，临界群，不变因子 n 一以一 ， ) 以型n+ 2 一 l 一，一曲 6 g 2 一 一、，2 旦仃一 打i 一 劫 融 面 a b s t r a c t a bs t r a c t t h e l a p l a c i a nm a t r i xi sap o w e r f u lt o o li ng r a p ht h e o r y t r a d i t i o n a l l y ，t h ep e o p l e u s et h ee i g e n v a l u e so ft h el a p l a c i a nm a t r i xt od e s c r i b et h ep r o p e r t i e so fg r a p h sa n d g e tal o to fv e r yn i c er e s u l t s i nt h el a s tt w e n t yy e a r s ，t h es m i t hn o r m a lf o r mo fl ( g ) i sf o u n dt ob et h ef i n ei n v a r i a n to fi s o m o r p h i s mo ng r a p h sa sw e l la st h el a p l a c i a n e i g e n v a l u e s ，s oi ti sm e a n i n g f u lt op a yo u ra t t e n t i o nt ot h es m i t hn o r m a lf o r mo fl ( g ) w ek n o wt h ec r i t i c a lg r o u pf r o mg t m 2 0 7 ，w h i l et h ef a m o u sm a t h e m a t i c i a nn b i g g s s t a t e dt h a tt h ec r i t i c a lg r o u po fag r a p hi sd e p e n do ni t ss m i t hn o r m a lf o r mi n 1 9 9 9 i nt h i st h e s i sw ed e s c r i b et h es m i t hn o r m a lf o r m so ft w ok i n d so fc a r t e s i a np r o d u c t g r a p h s ：ga n dq g t h e nw eg e tt h e i rc r i t i c a lg r o u p sa n dt h es p a n n i n gt r e e n u m b e r s i nt h el a s tc h a p t e ro ft h i st h e s i sw ew i l ls h o wt h es h a r pu p p e rb o u n d so ft h e f i r s tt h r e ei n v a r i a n tf a c t o r so ft h es m i t hn o r m a lf o r mo fg r a p hg t h ef o l l o w i n g sa r e t h em a i nr e s u l t sw h e r et h ep a r a m e t e r sw i l lb ee x p l a i n e di nt h e c o r r e s p o n d i n gp a r to ft h em a i nt e x t i f 仃= 2 s + 1 ，t h e nt h ec r i t i c a lg r o u po fk r m g ( m ，n 3 ) - i s 反m 9 。) 。磊。迢：旦0 里圣：，。乙。冬生旦0 里圣。乙， t r 卜一2 m - 3 w h e r e 7 = 瓦h 面8 ( n ，九。) ，垆= 瓦n m 面h s i f n = 2 s ，t h e nt h ec r i t i c a l g r o u po f k 击g ( m ，n 3 ) i s z ( u 。，2 n ) o 反oz ( m ，2 ) u 。o oz ( 。，2 ) u 。o 乙。乙。么o o 反。么， 、o - - _ _ - _ _ l l _ _ - _ o 、j _ - i l _ l - l - l _ 一、- _ l _ _ l o 、j _ _ _ _ _ _ - 一 m 一3m 一3 u l a b s t r a c t w h e r e t h e nt h en u m b e ro fs p a n n i n gt r e e so fk mxgi s 景( ( ! 三三乒) n + ( 翌生竺二譬) n 一2 ) m 一1 i f n = 2 s + 1 ，t h e n t h ec r i t i c a lg r o u p o f a c ( n 3 ) i s 互撕k ) 9 缸k ) 。z 错。乙a 。z 渊。z 蹁。z 赢f l t , a 8 l n ，k a ， jt n ，k 5 儿一， jj ， jl n 0 一j j i f n = 2 sw i t hso d d ，t h e nt h ec r i t i c a lg r o u po fq 仅( t , 3 ) i s 瓦，| ) 。，| ) 。z 黜。五一。z 渊( e 8。z 黼。z 赫t $ c ，oj，ic oj，j0 0 ，ajl j 0 to ，5 ，e ，j i f 竹= 2 sw i t hse v e n ，t h e nt h ec r i t i c a lg r o u po fa g m 3 ) i s 厶) 。，厶) 。z 黼彤f l 、厶7 6 e 。z 黜。z 熬。z 蒜群0 ，8 0 ，jjo 8 5 儿o o t ，j )c 5 ，j ，t o o 8 ，s - 8 0 ，jj t h e nt h en u m b e ro fs p a n n i n gf l e e so fq gi s 杀( ( 锯+ 1 ) 一( 锯一1 ) 州) 4 ( ( 以+ 1 ) - ( v 互- i ) n - 1 ) 2 ， 南( ( 锈+ 1 ) n 一( 锈一1 ) n ) 4 ( ( 以+ 1 ) n 一( 以一1 ) n ) 2 ， s o ，i fn 3 ，t h ef o l l o w i n ge q u a t i o nh o l d s n一-l(h 4 o 孚) 2 ( 6 地o s 等) = 去 ( 2 + 娟) 鸶一( 2 一怕) 号 4 ( 1 + 以) n 一( 以一1 ) n 2 i f ni s o d d ； i f 仃i s e v e n a b s t r a c l f u r t h e rm o r e ，f o ras i m p l ec o n n e c t e dg r a p hg 玩w i t ho r d e r7 , 5 ，t h et h i r d i n v a r i a n tf a c t o r8 3i sd e s c r i b e da sf o l l o w ：s 3 ( g ) 礼a n d8 3 ( g ) = 佗i fa n do n l yi f g = 一e ，w h e r eei sa ne d g eo f ；s 3 ( c ) = 死一1i fa n do n l yi fg = 移。一1 ； s 3 ( g ) = 一2i f a n do n l yi f n = 5a n dg = k 5 2 eo rg = 蚝一瓯；s 3 ( c ) = n 一3 i f a n do n l yi f gi so n eo f t h ef o l l o w i n gg r a p h s ：鲍蚝一伤，甄一g ，玛一2 6 3 ， k z 3a n dk 7 一k 3 3 k e y w o r d s ：l a p l a c i a nm a t r i x ，s m i t hn o r m a lf o r m ，c r i t i c a lg r o u p ，i n v a r i a n tf a c t o r v 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论义中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志 对本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。 保密的学位论文在解密后也遵守此规定。 州作者虢 凇f 6 年石月) e 1 第一章引言 第一章引言弟一早ji 百 1 1 图的基本概念 图是一种二元的拓扑结构，由两个部分构成：顶点和边顶点集合( v e r t e xs e t ) 是图的基础部分，记为y ，而边集( e d g es e t ) 表示了顶点与顶点之间的关系，记为 e 顶点集合与边集共同构成一个图 对某个具体的图g ，e ( g ) 可以看做是建立在v ( g ) v ( g ) 上的个映 射：e e ( g ) = ( z ，! ，) ，这里z ，秒y ( g ) 称顶点茁，y 为边e 的两个端点( e n d p o i n t ) ，边e 和顶点z ，可是相关联的( i n c i d e n t ) ，而称z 和y 是相邻或邻接的 ( a d j a c e n t ) 若这样的顶点对( z ，y ) 是无序的，即e = ( z ，y ) = ( ! ，z ) ，则称e 是无向 的；反之，若这样的顶点对( x ，y ) 是有序的，即e = ( z ，y ) ( y ，z ) ，则称e 是有向 的 若e ( g ) 中所有的边e 都是无向的，则称图g 为无向图( u n d i r e c t e dg r a p h ) ； 对应的，若e ( g ) 中所有的边e 都是有向的，则称图g 为有向图( d i r e c t e d g r a p h ) 一个图可能既包含有向边，又包含无向边本文中若无特别说明，均讨论无向图的 情形 若某条边的两个端点相同，即e = ( z ，z ) ，那么边e 称为环( 1 0 0 p ) 如果两 条或者更多的边具有相同的两个端点，即e 1 = e 2 = = e k = ( x ，秒) ，则称 e l ，e 2 ，e k 为一组重边( m u l t i e d g e s ) 或者平行边( p a r a l l e le d g e s ) 一个图中如 果没有环和重边，我们称它为简单图( s i m p l eg r a p h ) 本文中若无特别说明，图g 均是指简单图 我们来看一些常见的图设v = z 1 ，z 2 ，z n ) 为图的顶点集把任意两 点都连起来就得到完全图( c o m p l e t eg r a p h ) ，用记号k 表示，它的边集是( z i q ： 1 i u z 1 ) 如果无向图中任意两点之间都至少存在一条路相连，则称这样的图为连通图 ( c o n n e c t e dg r a p h ) 1 第一章引言 1 2图的运算 图与图之间有多种乘积，我们只给出本文所用到的笛卡尔( c a r t e s i a n ) 乘积的 定义 两个图g l 和g 2 的笛卡尔乘积用g 1 g 2 表示，定义如下： 设g 1 = ( ，e 1 ) ，g 2 = ( v 2 ，岛) 是两个简甲图，他们的笛卡尔乘积图为 g = ( ve ) ，其中v = ( 笛卡尔积) ，对心l ，u 2 ) 。 t ，0 2 ) v ，( u 1 ，u 2 ) 和( u l ，刀2 ) 在g l g 2 巾相邻当且仪当让1 = t ，1 ，( t 正2 ，饱) e 2 ，或者缸2 = 耽， ( u l ， 1 ) e 1 例如下图： 9 i t l g 1 l 上l 乱2 ( 乱l ，z 1 2 )( u l ，v 2 )( u l ， 0 2 ) 也 口 ? 3 2 ( t ，l ，让2 )( ? 3 1 ，2 3 2 )( u l ，? - 1 3 2 ) g 1 g 2 图1 2 笛卡尔乘积图 1 3 与图相关的矩阵 下面我们引入几个与图关系密切的矩阵在无向图g = ( e ) 中，顶 点集记为v = v l ， 0 2 ， ，边集为e = 2 m n ，则游戏会无限进行下去 ( 2 ) 若msn 2 m 一死，游戏可能无限进行下去或者在有限步之后停下。 ( 3 ) 若n 2 m 一礼，根据抽屉原理，在任意状态下，一定会存在一个顶点， 它上面的筹码数不小于它的顶点度，此时游戏可以进行下去状态是任意的，所以 游戏会无限进行同样的，当n 2 m n 时，如果某个状态下每个顶点上的筹码 数量都小于等于d ( u ) 一1 ，则每个顶点都不能被发射，即游戏到此为止，一定是有 限步 要完成( 2 ) 的验证，还需要我们给出当n m 时，游戏可以无限进行下去的 情形显然的，只需要建立n = m 时( 2 ) 成立的情况即可： 我们将图g 的所有佗个顶点钉l ， 0 2 ，都给个标号，分别为1 ，2 ，n 两 个顶点z 和之间若存在边e ，则规定e 的方向为从小标号端点指向大标号端点 在此定向之下，规定顶点口上的初始筹码数目为以u 作为小标号端点的边的数 目。由于每一条边都有且只有一个小标号端点，所有此时图g 上的筹码总数和边 的数目相同，为m 考虑标号为1 的顶点t ，1 ，它的所有邻边都以它为小标号端点， 所以它上边的筹码数目恰好等于它的度数，也就是说，此状态下顶点u l 是可以发 射的，即游戏可以进行下去接下去要考虑u l 发射之后的筹码分布状态，我们发 现，它恰好是这样的一个状态：将图g 的所有n 个顶点钞l ，口2 ，都给个标 号，分别为t t + 1 ，2 ，礼，边的定向和筹码分布的规则和之前相同此时来看 2 ，类似于之前对 1 的讨论，它也是可以发射的事实上，某个顶点u 发射之后的 状态都恰好是将它的标号增加铭，其他顶点标号不变所得的分布状态显然，以此 类推，顶点标号有无限种，所以游戏可以无限进行下去 而当 m 时，发射过程只能在进行有限步后停下 6 第二章图的临界群和弧r i r e 多项式 这里涉及到无圈定向的概念般的说，将一个无向图的每条边都规定一个 方向，若由此得到的有向图不包含有向圈，则此规定为无图定向( 参见【1 4 1 ) 本章的 后面我们还会提到这个概念 对于可以无限发射下去的游戏状态，任意时刻都存在可以发射的顶点，并且 在同一时刻可以发射的顶点数可能不止一个，那么自l 果我们选择的发射顺序不 同，是否会对游戏的进行造成影响? 例如同时存在两个可发射的顶点时，先发射 其中个可以让游戏无限进行下去，而如果选择先发射另外一个的话会不会让游 戏在某一个状态就停下来了? b j o r n e r 在文章1 3 】中给出了一些定理来来阐述这些 可能性，同样的在代数图论的教材中也能找到答案 定理2 1 2 【1 3 】3 2 3g 是连通图，8 是某个给定的初始状态那么从s 开始的任 意发射序列，或者都是无限的，或者都终止于某个相同的状态 此定理说明了发射的顺序是不影响的游戏进行的最终结果的在有多种选择 的情况下，任意选择发射的顺序都不会对游戏结果造成影响 在b i g g s 的文章【9 】中，他将图进行标号，对于一个发射序列，我们可以用一 个发射向量来表示其每一个顶点发射的次数，向量的第i 个分量就表示顶点讧在 整个过程中发射的次数对于两个发射向量z 和y ，我们定义向量运算zvy 如下 ( v 影) 罄= ? 珏8 z z 缸，玩) 对应的，如果和1 - 是两个发射序列，我们定义序列运算仃丁如下： 对每个顶点钍，如果似在。中发射了i 次，就从7 中去掉u 的前i 次发射( 如果不 到i 次就全部去掉) ，余下的按顺序保留在盯后而，组成新的发射序列 我们会发现，原来的两个发射序列在此运算下得到的新序列也是一个发射序 列，即如下定理 定理2 1 3i 9 】g 是一个连通图，盯和7 - 是从同一个初始态8 开始的两个发射 序列，其发射向量分别为z 和可，则在7 - 之后接上序列o r 丁也是从8 开始的一个 发射序列，并且其发射向量为zv 影。 这个定理用具体的算法说明了对于同一个初始态，选择不同的发射顺序并不 能改变游戏的最终状态设丁是一个从8 开始的只能进行有限步的发射序列，口 是从8 开始的另一个发射序列，由上述定理可知，盯丁只能是仃，因此盯也是有限 的现在假设o r 终止于另外一个状态，由于7 和下盯都是o r ，所以口和彳具有 相同的发射向量游戏的最终状态只由初始态以及发射向量决定，从而这两个发 射序列必然终止于相同的状态 7 第二章罔的临界群和t i l l 多项式 在一个无限发射的游戏中，显然会有些顶点发射了无数次，但是否会存在 某些顶点，只发射了有限次，从某个状态开始就再也不发射了，或者从始至终都没 有发射过呢? 下述的定理给出了问题的结论 定理2 1 4 【1 3 】3 2 1 对于一个能够无限地进行下去的游戏，它的每一个顶点都 会被发射无数次 这个性质告诉我们，在一个无限发射的过程中，任何一个顶点都会不停地发 射反之，若存在某个顶点从某个状态开始不再发射，则发射必然会在有限步之后 停下来 若一个游戏在有限步之后停。卜了，我们可以研究它从开始至停下来发射的总 次数，文章f 1 3 】3 2 3 中给出了以下估计 定理2 1 5g 是连通图，有钆个顶点，e 条边，其直径为d ，则筹码在g 上的 发射总次数不超过2 n e d 这个定理给出了顶点的发射总次数的一个上界对应的，如果引入大家熟悉 的l a p l a c i a n 矩阵的特征值，还可以得到另一个上界 定理2 1 6 【1 3 l3 2 5g 是连通图，有礼个顶点，g 上共有个筹码若游戏在有 限步之后停下，则发射总次数不大于以绍入2 ，其中a 2 是l a p l a c i a n 矩阵z ( o ) 的第二小的特征值，即最小正特征值( 代数连通度) 定义2 1 对于状态8 ，如果存在一个发射序列，使得s 在经过这个序列的发射 后，又重新回到了状态8 ，我们就称8 是一个循环态 显然，任意一个初始态在经过一个序列发射之后如果变成了循环态，那么它 将一直循环下去，这时游戏是无限的相反的，如果发射在有限步之后停下了，那 在整个发射过程中都不会有循环态出现也就是说给定了初始态，游戏能无限进 行下去当且仅当在某次发射之后游戏状态变成了循环态 现在我们引入个新的概念发散态( d i f f u s es t a t e ) 定义2 2 若在某个状态下，若图g 的任何一个点导出子图x 都至少包含一 个点u ，它上面的筹码数不少于。在子图x 中的度数，则称此状态为发散态 8 事实上，发散态和循环态是等价的 定理2 1 7 一个状态是循环态当且仅当它是发散态 第二章图的l 晦界群轺n 玎r e 多项式 证明：我们只需要证明以下两利- 情况： 设s 是一个循环态，仃是一个发射序列，s 经过序列仃发射后又回到s x 是g 的任意一个点导出子图考虑x 中最先结束发射的顶点v ，我们会发现口在 x 中的邻点在 的结束发射之后都至少还会再发射一次因此回到循环态s 时， 钞上筹码的个数一定不小于它在x 中的度数即8 是发散态 反过来，假设s 是发散态由于g 可以视为它本身的一个导出予图，因此 上面至少有一个点是可以发射的现假设有某些点已经发射过一次，考虑剩下的 那些点的导出子图，记为x 由发散态的定义，x 中至少有一个点口，它原本的筹 码数不小于u 在x 中的度数；而由假设，它的那些不属于x 的邻点都已经发射 过一次，所以此时 上的筹码数一定不小于它在g 中的度数，所以此时v 是可以 发射的由归纳法可知，发射过程可以一直继续下去，并且容易发现发射过程中每 个点都只发射一次s 经历一个循环后会回到初始状态，因此s 是循环态口 在上述定理的证明过程中，我们还可以得到下面的结论 定理2 1 8 图g 是连通图，有仇条边，则g 的无圈定向和g 上的筹码总数为 仇的发散态之间存在一一对应 i e n ：设“，是图g 的一个无圈定向，诱导定义5 = s ( 叫) = ( 8 1 ，8 2 ，s n ) 其中，对任意的1 i n ，8 t 表示顶点地在无圈定向叫下的出度这样，8 就是图 g 的一个状态我们只需要证明，是无圈定向当且仅当s 是发散态 ( 1 ) 若u 是无圈定向 考虑g 的某个点导出子图x ，g 上的无圈定向u 限定在x 上也是x 的一 个无圈定向i x 那么在x 上至少存在一个顶点，它限制在x 上的出度恰好等于 它限制在x 上的度，所以这个点上的筹码数等于这个点限制在x 上的度，由定 义s 是发散态 ( 2 ) 若8 是有m 个筹码的发散态 考虑从8 开始发射到下一个sm 现之间的发射情况此过程中每个点恰好发 射了一次，发射序列构成了顶点集的一个轮换按照所有n 个顶点在轮换中出现 的先后顺序v 1 ，v 2 ，给它们作标号，分别记为1 ，2 ，礼两个顶点x 和 y 之间若存在边e ，则规定e 的方向为从小标号端点指向大标号端点此定向叫是 一个无圈定向，而由定理2 1 1 的证明可知，此时s ) 恰好是个循环态，也即是发 散态口 若在某个状态下，有且只有顶点q 是可发射的，则称该状态为q 一稳定的这 时若q 不发射，其他顶点就不能发射若一个状态既是q 一稳定的，又是循环态，则 称它为g 一临界态 9 第二章图的临界群和1 弋r i t e 多项式 口一临界态是循环态，由定理2 1 1 可知，图g 上的筹码总数不少于图的边数 而当筹码总数恰好为边数时，我们有以下结论 定理2 1 9 图g 是有m 条边的连通图，则在m 个筹码的口一临界态与图g 的以q 为唯一发射源的无圈定向之间存在一个一一对应 定理2 1 1 0 图g 是有9 7 z 条边的连通图，令t 是一个口一临界态，那么存在一 个有m 个筹码的q - i f $ 界态8 ，使得对任意顶点 上面的筹码数，都有8 t 移 由此我们可以将那些有m 个筹码的口一临界态看作是最小临界态，其余那些 筹码数大于m 的临界态，可以由某个最小临界态在某些顶点上加上一些筹码得 到 注释2 1 1 1 在口一临界态中，g 点上的筹码是没有限制的，甚至可能是无穷大， 而其它点”上筹码的个数都不超过d ( u ) 一1 ，且不小于零因此，整个图上的筹码 数是没有上限的。 2 2 临界群 在b i g g s 的文章1 9 】中，将筹码发射游戏的规则做了改进：在图中取定一个特 殊的顶点g ，在发射的过程中，q 发射当且仅当其它的顶点都不能发射我们把此 规则下的筹码发射游戏称为美元游戏( d o l l a rg a m e ) 如果把图中除q 以外的顶点 看做是独立的经济体，每次发射过程看成是它们之间的资金流通，那么g 则扮演 政府的角色；也就是说，在资金流通顺畅的情况下，政府不做动作，如果资金流通 中断，也即其它顶点都不能再发射的时候，“政府”q 就必须发射以带动其它顶点 发射 美元游戏以及筹码发射游戏都与图的l a p l a c i a n 矩阵都有着紧密的联系回 顾之前的定义，令8 是美元游戏中的一个状态，它表示在某一时刻图中顶点上的 筹码数目，s ( u ) 就表示顶点t ，上的筹码数目事实上，我们可以将8 看作一个向 量，其维数等于图的顶点数，每个分量表示对应顶点上的筹码数目令s 是个 非空有限的发射序列( 当然同一个顶点可以发射多次) ，在这个序列的发射过程中， 顶点v 发射的次数记为z ( u ) 8 经过s 这个发射序列后变为8 7 ，8 7 可以表示如下 s 7 ( 口) = s ( u ) 一z ( u ) d ( u ) + 。( 叫) ( ，伽) 叫钉 每次t ，发射都会失去d ( 钉) 个筹码，而其它的顶点叫u 发射时，秽都会得到 l ，( u ，幻) 个筹码，其中( u ，叫) 是u 与叫2 _ 1 ；- 1 的连边数 1 0 第二章图的临界群和n 1 1 r r e 多项式 我们可以用图的l a p l a c i a n 矩阵l ( o ) 将上面的两个状态联系起来 其中 = 8 一l z ， ，rd ( u ) ， b u y2 气 【一工，( 牡， ) ， 若u = u ， 若乱u ， 注释2 2 1 在美元游戏中，我们不关心顶点g 上的筹码数，因为不论它上面 有几个筹码，只要当其它顶点都不能发射的时候，q 就必须要发射因此q 点上的 筹码数，根据讨论的问题不同，会有不同的设定一般情况下，我们默认q 上的筹 码数是负的，其大小恰好等去其他所有顶点上的筹码总数，这样，整个图的筹码总 数为零 b i g g s 在文章【1 0 】里就使用了这样的设定，他取定口点一t - 的筹码数为 s ( 口) = 一s ( u ) 0 t ，g 筹码发射游戏中给出的各种定义，在美元游戏中也有对应定义 定义2 3 如果除q 以外的每个顶点秽上的筹码数都满足0 s ( v ) d ( ) ，即 除了q 点之外都不能发射，则称s 为稳定态 定义2 4 一个发射序列称为是q 一合法的，当且仅当序列中q 点发射时其它 的顶点都已经不能发射。 定义2 5 若存在某个非空的g 一合法序列，使得状态s 在经过该序列的发射 之后又返回到自身，则称状态8 是循环态 显然，从状态8 开始，可以进行无限个口一合法序列的发射，在此过程中，8 是 会循环出现的 定义2 6 如果一个状态既是稳定态又是循环态，那么我们把它称它是一个临 界态 临界态一定是稳定态，但是稳定态不一定是临界态例如每个顶点上的筹码 都为0 时，这显然是一个稳定态，但是却不是临界态 1 1 第二章网的临界群和t u l l e 多项式 定义2 7 如果一个发射序列s 中q 点没有被发射。则我们称这个序列是合适 美元游戏是筹码发射游戏的一个变形，所以大部分性质在本质上是相同的， 所以同样有以下几个性质成立。 性质2 2 2 在美元游戏中，任意给定一个状态8 ，若它存在一个合适的口一合 法序列s ，则s 的长度是有上界的，即发射，必然在某个时候停止下来，不会无限的 发射下去 从筹码发射游戏的角度来看，任意一个状态8 ，在其中的口点不发射的情况下 也是不可能无限的发射下去的( 性质2 1 4 ) ，必然会在有限步之后停下来 性质2 2 3 对于任意的状态8 ，存在临界态c ，使得s 在经过一个口一合法序列 的发射后能够变为c 在这里的8 本身并没有任何要求，既可以不是稳定态，也可以不是循环态，但 是在经过个q 一合法序列的发射后，能够变换成一个临界态c ，而这正是我们所 研究的 定理2 2 4c 是一个循环态，如果经过一个g 合法的发射序列s 的发射后它 又回到自身，则s 的表示向量u 是全一向量。 发射过程可表示为c l u = c ，所以上面的发射序列s 的表示向量u 也恰好 是l u = 0 的解，而l a p l a c i a n 矩阵的解空间是一维的，其中所有分量都相同，所以 牡是所有分量都相同的常向量也就是说，循环态c 经过一系列发射后回到c 自 身，这个发射过程中，所有顶点发射的次数一定是相同的事实上，所有顶点都正 好发射了次， 定理2 2 5 临界态c 经过一个g 一合法序列s 的发射后变为另一个临界态d ， 则c = d 从这个性质中我们会发现，虽然任何一个状态都可以通过顶点的发射到达某 个临界态，但是一个临界态却不能通过顶点的发射到达另一个临界态，发射后到 达的临界态依然会是它本身 综合上面两个性质，我们有 1 2 定理2 2 6 对于任意一个状态s ，存在唯一的一个临界态c ，使得8 在经过一 第二章网的临界群和t i 1 t e 多项式 个q 一合法序列的发射后能够变为c 这就意味着任意的一个状态在合法序列发射的条件下都只有一个临界态与 之对应所以我们可以用临界态来将这些状态进行分类，而临界态就是每个类的 代表元 令伊( g ，z ) 和c 1 ( g ，z ) 分别是定义在顶点集y 和边集e 上的整值函数， 它们可以视为向量空间中的向量，而关联矩阵d 和它的转置d t 则可视为如下向 量空间上的同态 d ：伊( g ，z ) _ c 1 ( g ，z ) ， d ：c 1 ( g ，z ) _ c o ( g ，z ) 那么l a p l a c i a n 矩阵l = d d 2 可以看做是一个g o ( g ，z ) _ c o ( g ，z ) 的同 态，我们定义o ( y ) = e 射，( 钞) ，那么盯就是伊( g ，z ) _ z 的同态在b i g g s 的文 章【9 】中证明了如下的性质 定理2 2 7i mq 是k e r 盯的正规子群 对于每个状态0 ，令7 ( 0 ) 表示与之对应的唯一的临界态，由于任意一个态都 属于k e r 盯，用【0 】表示p 关于i mq 的陪集，定义 r ：k e ra i mq k ( g ) ， 其中7 ( 0 1 ) = - r ( o ) ，k ( g ) 表示图g 的临界态所构成的集合除了这个定理， 文章【9 】还给出了如下结果 定理2 2 8 连通图g 的临界态的集合k ( a ) 与阿贝尔群k e rt r i mq 之间存 在一一映射 其中阿贝尔群k e r a i m q 的加法定义为：【叮+ 】= p + 9 ，】 k ( a ) 的加法定义 为：c c ，= 7 ( c + ) ，其中c 和c ，都是临界态 这个由临界态所构成的群就是我们所研究的l l 台i 界群，通常就记为k ( g ) ，在 有些文章中也被称为雅可比群( j a c o b i a ng r o u p ) 【l5 i l o r e n z i n i 在早期的文章【1 6 l 中已经简单介绍了一些临界群的内容c o d 在文章1 1 7 】中还证明了平面图与其对 偶图的临界群之间的联系 对于一个平面图g ，它一定可以找到一个平面表示m 则g 的对偶图伊是 以m 的面为顶点的图，以相邻的两个面之间连一条边 定理2 2 9 平面图g 与它的对偶图口有相同的临界群 1 3 第二章图的临界群和吓胛e 多项式 为了证明这个定理，我们需要用到边集上的一个赋值考虑边的一个定向赋 值u ，使得每条定向的边所赋的值都是正整数，即对于任意的边n ，w ( a ) z + ；如 果u ( o ) = 0 ，则不给这条边定向若某条边e 的赋值取负，方向也取相反，其他边 的定向赋值不变，得到了定向赋值u 7 ，我们认为u = u ，即这两个定向赋值是同一 个示意图如下： 1 4 2 图2 1 1 边的一个定向赋值u 2 图2 1 2 定向赋值= u 在定向赋值u 下，若e = 忱_ ，则称e 为仇的出边，为的入边 第二章图的临界群和t i r r r e 多项式 这样给的边上的定向赋值，我们还可以诱导定义出顶点上的赋值o w 以及 面上的赋值扩u 它们分别如下： 对于顶点v i ，( 钆) t 等于钆的所有出边的赋值之和减去所有入边的赋值之和； 对于面 ，( 0 u ) t 等于面五的所有邻边的有向赋值和，即邻边e 的定向和正向 相同的，赋值取u ( e ) ，否则取一( e ) ( 一般取逆时针方向为正向) 图2 2 诱导的顶点赋值孔 5 图2 3 诱导的面赋值伊u 1 5 第二章图的临界群和n 臃多项式 定理2 2 1 0 若u 是连通图g 的一个顶点赋值，满足条件： u t = 0 i = 1 则一定存在边上的赋值u 使得a ) = t 证明：要证明存在满足条件的u ，只需要考虑图g 的支撑树即可，其他的边可 以都赋零值 取定g 的支撑树t ，则t 肯定存在根节点满足条件：存在边的某个定向， 使得任意一个顶点 都有到的有向路，即所有的边都指向根节点显然t 中连接u 和的路有且只有一条，所以在这样的定向下，除了没有出边之外， 其他的任意顶点都有且只有一条出边考虑如下的边赋值u ： 若边e 岳t ，则u ( e ) = 0 ： 若边e 关联到t 的某个垂点仇，则u ( e ) = u i ； 若边e 是某个顶点优的唯一出边，则u ( e ) = u +u ( a ) 我们可以断言，此就是满足条件的边定向赋值： 首先，由第一条，去掉其他边，只需要考虑t 上的赋值即可 对于r 的所有垂点地，由第二条，蚴= u ( e ) = ( 钆) ； 若仇不是垂点，e 是它的唯一出边，则 u 产( e ) 一 u ( 口) = ( 钆) t ； o 是仇的入边 r t - 1 对于根结点，u n = 一= 一叫( o ) = ( 钆) t 口 讧l n 是的入边 类似的，以下定理也成立 定理2 2 1 1 若矿是连通图g 的一个面赋值，满足条件： u 净0 。i 。e ，：1 1 喜：薹：笔支兰； l 0 否贝| j 第二章图的临界群和t i 丌_ r e 多项式 从向量的角度来看，其诱导顶点赋值o d i 恰好为矩阵l ( g ) 的第i 个行向量t ， 即a d i = a t ；而其诱导面赋值伊d i = 0 图2 4 由顶点v 2 取定的边定向赋值d 2 同样的，对于某个面五，我们还可以取边定向赋值叫如下： 。：c e ，= 冀：篙主曼翥；黧主宝； 和前一个结论类似的，其诱导面赋值矿d ：恰好为矩阵l ( g + ) 的第z 个行向量：， 即矿删= ：；而其诱导顶点赋值o d ：= 0 1 7 第二章图的临界群和脚多项式 图2 5 由面如取定的边定向赋值d ： 参考文献【1 8 l 给出了以下定理： 定理2 2 1 2g 是平面图，u 是它的一个边定向赋值，若o w = 0 ，则u 一定可 以表示成若干d ：的线性组合 现在，我们可以回过头来证明定理2 2 9 了 定理2 2 9 的证明：设面是k ( g ) 的某个元素，则它必然对应了某个临界 态让，如同注释2 2 1 所言，可以取定u i = 0 若将此临界态视为顶点赋 值，则由定理2 2 1 0 ，存在边定向赋值使得o w = u 定义临界群之间的映射 妒：k ( a ) hk ( g + ) 如下 妒( 面) = 0 + u 其中瓦为扩u 对应的临界态在k ( g ) 中的像 首先说明，这样定义的妒是有意义的，即妒( - ) 不会因为“和u 的取值不同 而变化 由前面对临界态的性质的讨论可知，瓦和心是一一对应的； 当u 取定的时候，若存在u 满足钆= 批= 钆，则由定理2 2 1 2 ，u u 7 是 d i ，d ：的线性组合，从而必有 钆一o w 7 ， 前面已经说了，o d ：= 0 ，所以 瓦= 丽：面 1 r 第二章图的临界群和，r 【，t t e 多项式 从而的取值不影响结果 接下来要说明，q o 是个一一映射事实上，由于a 和伊都是线性作用，所以妒 也是个线性作用： 对于临界群k ( c ) 中的任意两个元素面，可，存在边定向赋值u 和t 满足 钆= u ，挑= 秒，从而 妒( 瓦+ 虿) = 伊0 + t ) = 0 + u + 0 t 临界群k ( g ) 和k ( g + ) 都只有一个单位元，所以妒只能是一一映射了口 事实上，临界群k ( a ) 是一个有限生成的阿贝尔群，具有如下形式的直和分 解 k ( g ) = ( z n , z ) o ( z n 2 z ) o o ( 纠珥z ) 其中的吼就是本文提到的不变因子，满足条件整除啦+ 1 要确定这些不 变因子就等于在确定关系矩阵l ( g ) 的s m i t h 标准型，其对角线上的元素就