（应用数学专业论文）图的chipfiring+game问题的研究.pdf

图的c h i p - f i r i n gg 鲤呈塑塑鱼堡究 摘要 本文主要讨论这样一种游戏c h i p - f i r i n gg a m e s ：先给出个图g = ( ke ) ， g 的每个点匕都包含若干个碎片，当个点v 上的碎片数c ( t ，) 大于等于t ，的度数 d ( t ，) 时 就可以对该点进行崩塌，在秒点次崩塌之后，顶点t ，上的碎片数减少 d ( t ，) 个，而t ，的任邻点u 与t ，连有八涤边，u 的碎片数朝时曾加几个，g 的其 它顶点碎片数不变游戏按此规则进行，每个状态的总碎片数保持：不变如果 某时刻，g 上的任意点1 3 都有c ( w ) 2 m n ，g 上的c h i p - f i r i n gg a m e s 是无限的； ( b ) 若n m ，g 上的c h i p - f i r i n gg a m e s 是有限的； ( a ) 若m n 2 m n ，结果刁訇朔定 当m n 2 m 一佗的时候，情况是极其复杂的，即使是对于最简单的图形 上的c h i p - f i r i n gg a m e s ，同样也是如j 眩比如说圈上的c h i p - f i r i n gg a m e s ， 结果不确定的情况只有一种，即总碎片数n = 7 n = n 时但这方面的问题直 到1 9 9 5 年才由j j e f f s 和s s e a g e r ( 6 ) 解决：他们将碎片的初始分布称为个 n c h i p - f i r i n gg a m e s 的初始状态，并定义状态的权：( 鱼) = i a i ( m o d1 2 ) ，其中 1 a 表示- - - q v j 劁t 态，m 表示在初始状态a 中，点叻上的碎片数j j e f f s 等 人证明了对于圈上的c h i p - f i r i n gg a m e s ，在n = n 的情况下，任起始于初 始状态a 的c h i p - f i r i n gg a m e s 是有限的当且仅当t l ，( 彭= w ( t ，1 ，1 ) 除圈的情况，至今仍无法用完满的方法( 给出充要条件的形式) 来判别其它图 形上的c h i p - f i r i n gg a m e s 哪些是有限，哪些是无限鉴于这项工作的难度，本 文将分成两个部分在第部分中，将给出个算法，对于任何个顶点数较少 的图，只要给定总的碎片数的值，本算法就能利用图形的邻接矩阵来分别给出 所有有限和无限的c h i p - f i r i n gg a m e s 的初始状态；在第二部分中，将研究完全 图上的c h i p - f i r i n gg a m e s ，并将给出个笋4 断完全图上的c h i p - f i r i n gg a m e s 是有限的充要条件 在本章中未给出明确定义的记号或术语可参见f 7 】 第二章判别图的c h i p - f i r i n gg 鲫e s 有f g - - 5 否鲍算法 6 第二章判别图的c h i p - f i r i n gg a m e s 有限与否的算法 我们已经知道对于任意个图，要判断图上哪类的c h i p - f i r i n gg a m e 是有 限的是个极其困难的问题，即使在最简单的图形上的c h i p - f i r i n gg a m e s 都难 以判断其有限与否于是在本节中，任意给定个顶点数较少的图，我们将借助 算法来分别给出图e 所有有限和无限的c h i p - f i r i n gg a m e s 的初始状态在此之 前，我们先儆些准备工作 2 1 预备知识 在本节中，我们给出三个声明； 1 在本篇文章中，对于个给定的图g ，我们用表示该图匕拥有的总碎 片数； 2 给定个图g ，由定理1 1 可知，当g 上碎片的初始分布( 初始状态) 确定后，接下来遗行的c h i p - f i r i n gg a m e s 的结果也就确定了于是在本篇文章 中，如果从个初始状态0 出发的c h i p - f i r i n gg a m e s 是有限的，我们就称状态 口为有限状态；反之称为无限状态 ， 3 在本南文章中，图g 上的初始状态均用数列的形式表示设g 拥有n 个 顶点，则数列的第i ( 1 i 佗) 个元素f 弋表初始状态下q 上的碎片数( 仇 y ( g ) ) 接着我们给出三个用来构造算法的引理： 引理2 1 1 1 】a 1 1 ( n d ) 其中，n 与d 分别表示g 的顶点数与直径，a 1 是图g 的l a p l a c e 矩阵的 所有正的特征值中的最小直，g 的l a p l a c e 矩阵是个n n 的矩阵且满足： 第二章判别图的c h i p - f i r i n gg a m e s 有限与否的算法 7 引理2 2 1 1 】在任意的拥有n 个顶点的图上的有限c h i p - f i r i n gg a m e s ，总的 崩塌次数至多是2 n a 1 次 引理2 3 【1 】如果图g 上的个c h i p - f i r i n gg a m e s 是有限的，那么必定存在 个顶点从未被崩塌 2 2 算法的构造 下面介绍算法的步骤： 1 输入目标图g 的邻接矩阵； 2 先手动算好m 与2 m n 的值，再将h ，2 m n 】这一区间内的整数逐 个输入 3 输入个数，就将其进行拆分，并去掉元素个数多于扎个的拆分，将元素 个数少于n 的拆分补零，使其元素个数达到n ，将其看做个数列 4 将拆分好的数列进行全排列，以得到所有可能的状态 5 将步骤4 中处理好的数列中的每个元素依次代表v o ，i 1 ，一1 上的碎 片数，根据步骤1 中已输入的邻接矩阵来不断崩塌各点，最终可在至多2 n 2 n d + l 轮内判断该数列代表的状态是否为有限 第步中将g 的邻接矩阵输入计算机是为了让计爱嘲了解g 的构造，尤其是 点与点之间的关系；在第三步中将输入的数进行拆分，用到了d o n a l dl k r e h e r 和d o u g l a sr s t i n s o n 所写的? c o m b i n a t o r i a la l g o r i t h m s 【1 】中的算法3 1 ，在 本文中由于情况所需做了些微的变化，具体如下 算法2 1 g l e 适 侧 州 巧否 09 k 妣o q ，-，、-l一， 第二章判别图的c h i p - f i r i n gg a m e s 宣醒与否的算法 8 g e n p a r t i t i o n s ( m ) p r o c e d u r e r e c p a r t i t i o n ( m ，b ，) i fm = 0 ， t h e n 【i fn n ， t h e n f o rk = 1 t o1 1 ， b k = 0 ， f o rs = 1t on 6 j 卜a s ， o u t p u t ( b 1 ，6 2 ，k 】) ， e l s e f o ri = 1t om i n ( b ，m ) ， d o a n + l 。l ， r e c p a r t i t i o n ( m i ，i ，n + 1 ) ) m a i n r e c p a r t i t i o n ( m ：m ，0 ) 这个算法应用递归的原理，要对个数r n 进行拆分，首先先给定a 1 = 1 ，并 将1 作为e 界( 即后面的元素a 2 ，a 3 ，的取值不能超过1 ) ；然后就对m 一1 进行拆分，给定a 2 = 1 ，再次将1 作为上界；接着对m 一2 进行拆分，以这种 方式递归，可得出所有首个元素是1 的拆分做到这步就跳出递归，回到a 。， 对其重新赋值，令a l = 2 ，并将2 作为上界，同1 羊可得出所有首个元素是2 的拆 分以此类推，最终可以列出所有可能的拆分耳每个拆分中的元素按从大到小 的顺序排列对于这些拆分，由于我们要将它们看做具有n 个顶点的图的初始状 第二章判别图的c h j 呻咝堡塑竺宣堡与蚕的算法 9 态，因此我们并不需要那些元素个数大于n 的拆分，匕述算法会将这样的拆分抛 弃，并将元素们睨! 汗n 的拆分补零，使其元素个数达到n 举个例子，将整数1 2 用上述的算法进行拆分，可以得到下列4 7 个数列。 【1 2 ，0 ，0 ，0 ，o 】， 1 1 ，1 ，0 ，0 ，o 】，【1 0 ，2 ，0 ，0 ，o 】，【9 ，3 ，0 ，0 ，o 】，【8 ，4 ，0 ，0 ，o 】，【7 ，5 ，0 ，0 ，0 】， 【6 ，6 ，0 ，0 ，o 】， 1 0 ，1 ，1 ，0 ，o 】，【9 ，2 ，1 ，0 ，0 】，【8 ，3 ，l ，0 ，o 】，【7 ，4 ，1 ，0 ，0 】， 6 ，5 ，1 ，0 ，o 】， 8 ，2 ，2 ，0 ；o 】，【7 ，3 ，2 ，0 ，o 】，【6 ，4 ，2 ，0 ，o 】，【5 ，5 ，2 ，0 ，o l ，【6 ，3 ，3 ，0 ，o 】， 5 ，4 ，3 ，0 ，o 】， 4 ，4 ，4 ，0 ，0 】，【9 ，1 ，1 ，1 ，0 】，【8 ，2 ，1 ，1 ，o 】，【7 ，3 ，1 ，1 ，o 】，【6 ，4 ，1 ，1 ，o 】，【5 ，5 ，1 ，1 ，o 】， 【7 ，2 ，2 ，1 ，o 】，【6 ，3 ，2 ，1 ，0 】，【5 ，4 ，2 ，1 ，o 】，【5 ，3 ，3 ，1 ，o 】， 4 ，4 ，3 ，1 ，o 】， 6 ，2 ，2 ，2 ，o 】， 【5 ，3 ，2 ，2 ，0 】， 4 ，4 ，2 ，2 ，o 】，【4 ，3 ，3 ，2 ，0 】，【3 ，3 ，3 ，3 ，o l ，【8 ，1 ，1 ，1 ，1 】，【7 ，2 ，1 ，1 ，1 】 【6 ，3 ，1 ，1 ，1 】，【5 ，4 ，1 ，1 ，1 】，【6 ，2 ，2 ，1 ，1 】，f 5 ，3 ，2 ，1 ，1 】，【4 ，4 ，2 ，1 ，1 】，【4 ，3 ，3 ，1 ，1 】， 【5 ，2 ，2 ，2 ，1 】，【4 ，3 ，2 ，2 ，1 】，【3 ，3 ，3 ，2 ，l 】，【4 ，2 ，2 ，2 ，2 】，【3 ，3 ，2 ，2 ，2 】 得到这些数列后，为了保证能够得到全部可能的状态，我们将拆分好的数列逐 个进行全排列，具体程序如下： 算法2 2 榉i n c l u d e ， 移i n c l u d e v o i ds w a p ( h a t 木a ，i n t ) ； v o i da r r a n g e ( i n t 木s a m p l e ，i n t 七，i n tm ) ； i n tn = o ： f i l e 木f d ； i n tm a i n ( ) i n ts a m p l e 2 5 6 ； i n tm ： c h a ra c b u f 3 2 ； p r i n t f ( ”i n p u ts a m p l e ( o n l ys u p p o r tn u m b e r ，o k t os h o wr e s u l t n ”) ； 第二章判别图的c h i p - f i r i n gg a m e s 有限与否的算法 1 0 m = 0 ： d o ( m e m s e t ( a c b u f , 0 ，s i z e o f ( a c b u f ) ) ； s c a n f ( ”s ”a c b u f ) ； s a m p l e m 】= a t o i ( a c b u f ) ； 仇+ + ： w h i l e ( s t r c m p ( a c b u f , ”o k ”) i = o ) ； f d = f o p e n ( ”l i s t t x t ”，”+ ”) ； i f ( d = = n u l l ) p r i n t f ( ”c r e a t ef i l ef a i l n ”) ； e 妃t ( 1 ) ； p r i n t f ( ”c o n t e n t ：n ”) ； a r r a n g e ( s a m p l e ，0 ，m 一2 ) ； p r i n t f ( ”t o t a l ：d n ”，n ) ； f c l o s e ( f d ) ； r e t u r no ： ) v o i ds w a p ( i n t 木a ，i n t 半b ) i n tm ： m = 丰a ： 木a = 术b ： 木b = 仇： 一 i i l ：董 鼢 坤 ；埘 一 一 一 一一 a 一 一，。吣。一。一一卜一一一，一。一。一一一， 第二章判别图的c h i p - f i r i n gg a m e s 有限与否的算法 1 2 这个全排列算法用到了递归，我们举个例子说明：对于组数a l ，o , 2 ， 首先，对最后两个数n n 1 a n 进行全排列，就有a n - 1 ，a n 和a n ，a n - 1 两懒，然 后进行递归，对最后三个数a n - 2 ，a n - 1 ，a n 进行全排列，方法就是将a n - i 这个数对 之前已有的两个数组n ，l l ，和o n ，a n 一1 进行插入操作，于是得到a n - 2 ，a n 一1 ，a n ； a n 一2 ，a n ，a n 一1 ；a n 一1 ，0 n 一2 ，a n ；a n ，a n 一2 ，a n 一1 ；a n 一1 ，a n ，a n 一2 ；a n ，a n 一1 ，a n 一2 以此类推，就可以实现全排列，最后把所有的数列存放在列表l i s t 中 为了保证判别算法在有限时间内进行，我们应给出个运行次数的上界，当一 个图上的c h i p - f i r i n gg a m e s 崩塌的步数超过这个匕界时，就判断正在检验的状 态为无5 艮由引理2 1 和引理2 2 可得出，有限状态的崩塌次数hs2 n a l 2 n n ( 1 n d ) = 2 n 2 n d 这也就是我们的判别算法中需要的上界 下面给出的是检验列表中的数列所表示的初始状态是有限或无限的判别算祛： 算法2 3 t e s t ( ) h 卜0 ，e 卜0 ，h 卜1 2 f ， f o ra n yx l i s t ， f o rf = 0 t on 一1 ， d od 】卜d ( v 1 ) ，a i r 】卜x 【，】， f o ri = 0t o2 n 2 n d ， _ 【s 卜0 ，c l e a nh ， f o rj = 0t on 一1 i fa j 】d b 】， t h e n 4 【】卜a j 】一d b 】， f o rk = 0t on 一1 【i f ( 吻) = 1 ， t h e na k 】卜a k 】+ 1 ，) 第二章判别图的c h i p - f i r i n g g a m e s 有堡与否的算法 1 3 i fjg 日， t h e nj _ h ， i fi h l = n ， t h e n 【i n f i n i t e l i s t e 】卜x ，e 卜e + 1 ，b r e a k ； ) e l s es 卜s + 1 ，) i f8 = 佗， t h e n f i n i t e l i s t h 】卜x ，h 卜h + 1 ，b r e a k ； ) i n f i n i t e l i s t e 】卜x ，e 卜e + 1 ) 在匕面的算法中， c h i p - f i r i n g0 a m e s 进行了2 n 2 n d + 1 轮，每轮都依 次检查v o ，u 1 ，v n 一1 ，若存在仇满足c ( v i ) d ( 仇) ( 在e 面算法中表现为 a i 】d ，就崩塌该点，否则令s 卜s + 1 若该轮结束时s = n ，说明在该轮 中没有点崩塌，也崩浞蜊此时对于任意点t ，都有c ( v ) 。d ( 0 ，于是目前检验的 状态有限；若s n ，说明该轮中有至少个点崩塌，于是令8 清零，进入下一 轮另外，在算法中还设定了个集合h ，当任意点忱崩塌时，若igh ，就做 i _ 日：若某时刻i h i = n ，即每个点都被崩塌过，根据引理2 3 ，立即可以确 定该状态为无限已知有限状态至多崩塌2 舻n d 步；如果某个状态将2 n 2n d + 1 轮进行完，说明该状态亦是无限 下面我们给出个例子： g - - 章判别图的c h i p - 五r i n _ gg a m e s 有堡与蚕茧笋法 在匕面这个图中，点数是5 ，把总碎片数的值定为9 首先由算法2 1 可 列出下列的拆分： 【9 ，0 ，0 ，0 ，o 】，【8 ，1 ，0 ，0 ，o 】，【7 ，2 ，0 ，0 ，0 】，【6 ，3 ，0 ，0 ，o l ，【5 ，4 ，0 ，0 ，0 】，【7 ，1 ，1 ，0 ，o 】， 【6 ，2 ，1 ，0 ，o 】，【5 ，3 ，1 ，0 ，o 】，【4 ，4 ，1 ，0 ，o 】，【5 ，2 ，2 ，o ，o 】，【4 ，3 ，2 ，0 ，o 】， 3 ，3 ，3 ，0 ，o 】， 【6 ，1 ，1 ，1 ，o 】，【5 ，2 ，1 ，1 ，o 】，【4 ，3 ，1 ，1 ：o 】，【4 ，2 ，2 ，1 ，o 】，【3 ，3 ，2 ，1 ，o 】，【3 ，2 ，2 ，2 ，o 】， 【5 ，1 ，1 ，1 ，1 】，【4 ，2 ，1 ，1 ，1 】，【3 ，3 ，1 ，1 ，1 】，【3 ，2 ，2 ，1 ，1 】，【2 ，2 ，2 ，2 ，1 】 然后经过算法2 2 得到所有的初始状态，并由算法2 3 得出有限的初始状态是下 列5 3 项： 9 ，0 ，0 ，0 ，o 】，【0 ，8 ，0 ，1 ，o 】， 0 ，7 ，1 ，1 ，0 】，【0 ，7 ，2 ，0 ，o 】，【0 ，7 ，0 ，2 ，0 1 ，【0 ，0 ，6 ，3 ，o 】， 【0 ，0 ，6 ，2 ，1 】，【0 ，0 ，4 ，3 ，2 1 ，【0 ，0 ，4 ，4 ：1 】：【0 ，0 ，5 ，3 ，1 】，【0 ，0 ，5 ，0 ，4 】， 0 ，0 ，3 ，3 ，3 】， 【0 ，0 ，3 ，2 ，4 1 ，【0 ，0 ，4 ，1 ，4 1 ，【6 ，1 ，1 ，0 ：l 】：【0 ，1 ，2 ，1 ，5 】，【0 ，1 ，1 ，4 ，3 1 ，【6 ，1 ，0 ，2 ，o 】， 【6 ，0 ，0 ，3 ，0 】， 7 ，0 ，0 ，1 ，1 ，【7 ，170 ，l ? o 】： 3 ，0 ，0 ，3 ，3 】，【3 ：0 ，2 ，2 ，2 】，【3 ，1 ，2 ，1 ，2 】， 【3 ，1 ，2 ，2 ，1 】， 2 ，4 ，1 ，1 ，1 】，【2 ，4 ，1 ：2 ，o 】：f 2 ，3 ，l ，2 ，1 】， 2 ：5 ，0 ，1 ，1 】，【2 ，5 ，0 ，2 ，0 】， 【2 ，5 ，1 ，0 ，1 】，【2 ，1 ，2 ，2 ，2 ，【1 ，8 ，0 ，0 ：o 】：【1 ，7 ，0 ，1 ，o 】，【1 ：6 ，0 ：2 ，o 】，【1 ，5 ，0 ，2 ，1 】， 1 ，5 ，0 ，3 ，o 】， 1 ，5 ，1 ，1 ，1 】，【1 ，4 ，4 ，0 ：o 】： 1 ，4 ，2 ，1 ，1 】，【1 ：4 ：3 ，1 ，o 】，【1 ，4 ，3 ，0 ，1 】， 1 ，4 ，0 ，4 ，0 1 ，【1 ，4 ，l ，2 ，1 】，【1 ，3 71 ：1 3 】【l ，2 ，2 ，2 ，2 】， 5 2 0 0 2 】，【5 ，3 ，1 ，0 ，o 】， 5 ，3 ，0 ，1 ，o 】，【5 ，4 ，0 ，o ，o 】，【5 ：l ：1 ，111 】：【4 ：0 ，0 ，2 ，3 】：阻0 1 0 4 】 无限的初始状态是下列7 4 项： 【8 ，1 ，0 ，0 ，o 】， 0 ，9 ，0 ，0 ，o 】，【0 ，8 ，1 ，0 ：0 】，【0 ，7 ，1 ，0 ，1 】，【0 ：0 ：6 172 】： 0 ，0 ，6 ，0 ，3 】， 1 4 第二章判别图的c h i p - 丘r i n gg a m e s 有限与否的算法 【0 ，0 ，4 ，5 ，o 】，【0 ，0 ，5 ，2 ，2 】，【0 ，0 ，5 ，1 ，3 】，【0 ，0 ，3 ，5 ，l 】，【0 ，0 ，3 ，4 ，2 】，【0 ，0 ，2 ，5 ，2 】， 0 ，0 ，2 ，6 ，1 】，【0 ，1 ，6 ，1 ，l 】， 0 71 75 2 ：1 】，【6 ，l ，2 ，0 ，o 】，【0 ，1 ，2 ，3 ，3 1 ， 0 ，1 ，2 ，4 ，2 】， 【0 ，1 ，2 ，2 ，4 】，【0 ，l ，4 ，1 ，3 】，【0 1 ，3 ，2 ，3 】， 0 ，2 ，3 ，2 ，2 】，【7 ，0 ：0 ，0 ，2 ，【3 ，0 ，0 ，6 ，o 】， 【3 ，0 ，0 ，4 ，2 】，【3 ，0 ，0 ，5 ，1 】，【3 0 ：5 ，0 j1 】，【3 ，0 ，1 ，4 ，1 1 ，【3 ，0 ，1 ，3 ，2 】，【3 ，0 ，1 ，2 ，3 1 ， 3 ，0 ，1 ，1 ，4 】，【3 ，0 ，2 ，0 ，4 】， 3 0 2 ：1 ：3 】： 3 ，0 ，3 ，0 ，3 】，【3 ，1 ，3 ，1 ，1 】，【2 ，7 ，0 ，0 ，o 】， 【2 ，4 ，1 ，0 ，2 】，【2 ，4 ，0 ，3 ，o 】： 2 ：4 ，0 ：1 ：2 】，【2 ，4 ，0 ，0 ，3 】，【2 ，2 ，5 ，0 ，o 】，( 2 ，3 ，3 ，1 ，o 】， 【2 ，3 ，2 ，0 ，2 】，【2 ，3 ，2 ，1 ，1 1 ，【273 ，2 72 ，o l ，【2 ，3 ，1 ，3 ，o 】，【2 ，6 ，l ，0 ，o 】，【2 ，6 ，0 ，l ，0 】， 【1 ，7 ，1 ，0 ，0 】，【1 ，6 ，1 ，0 ，1 】，【1 ，6 ，1 ，1 ，o 】，【1 ，6 ，0 ，0 ，2 】，【1 ，5 ，3 ，0 ，o 】，( 1 ，5 ，0 ，1 ，2 】， 【1 ，5 ，2 ，0 ，1 ，【1 ，4 ，2 ，0 ，2 】，【1 ，4 ，2 ，2 ，o l ，【1 ，4 ，0 ，3 ，l 】，【1 ，3 ，1 ，2 ，2 】，【1 ，3 ，1 ，3 ，1 】， 【1 ，3 ，2 ，0 ，3 】，【1 ，3 ，2 ，1 ，2 】，【1 ：3 ，2 j3 ，o 】，【5 ，2 ，0 ，1 ，1 】，【5 ，2 ，0 ，2 ，o 】，【5 ，2 ，1 ，0 ，1 】， 【4 ，0 ，0 ，0 ，5 】，【4 ，0 ，0 ，1 ，4 】， 4 ，0 ，2 ，0 ，3 1 ， 4 ，0 ，2 ，1 ，2 】，【4 ，0 ，2 ，2 ，1 】，【4 ，0 ，1 ，3 ，1 】， 【4 ，0 ，l ，1 ，3 】，【4 ，1 ，2 ，l ，1 】 这个算法最大的缺点就在于时间复杂度，当n 较大时，等待时间将极为漫长， 于是灌种中构佣另币杉穷攒对完全图进彳亍 研究 1 5 第三章完全图的c h i p - f i r i n gg a m e s 第三章完全图的c h i p - f i r i n gg a m e s 1 6 在完全图中，我们所未知的区域是砩sn 2 c 2 一n 这范围，在研究之 前，首先给出两点声明： 1 对于个c h i p - f i r i n gg a m e s ，它任意时刻的状态妒都可以由个数列表 示t妒= ( c ( 伽) ，c ( 秒1 ) ，c ( 一1 ) ) ，若另状态砂中的若干元素经过_ 定的 排列后，能变成妒，由于完全图的结构特性，我们就认为妒三，并称为妒的 等价状态 2 c h i p - f i r i n gg a m e s 中的任点口，在不同时刻可能会有不同的碎片数， 为了避免产生混淆，对于任状态妒，我们用c ( u ) i 妒代表在状态妒下t ，上的碎 片数 根据定理1 2 的叙述，当n 砩) 设最小 断层左右两点分别是牡，u i + l ，有c ( u ) 芝c ( u i ) + 2 j 下面分三种情况考虑： 1 在妒1 中，有目仅有蜘，使c ( 牡o ) = 0 且j 0 ( 即最小断层未发生在 咖，t l 之间) 第三章完全图的c h i p - r i n gg a m e s 1 8 令地+ l ，u i + 2 ，i l n - 1 蔓蝴塌，萤臣uc ( u 。) n - 1 ，v s i + 1 ，i + 2 ，n 一 1 ) ，将此时的状态记为0 ，由于之前假设p 1 是无限的，所以c ( u , ) l o n 一1 由引 理3 2 知c ( u , ) l o = 扎一1 ，且在u o ，牡l ：t “中，不存计k ( os 忌i 一1 ) ，使 c ( u k ) = c ( u j , + 1 ) 0 令h = 咖，u l ，地 ，= t t + 1 ，u t + 2 ，一1 ) 由上 面的分析有( c ( u o ) ，c o , x ) ，c ( 碥) ) b = ( n - i - 1 ，n - i ，n 一1 ) ，尽可能多地 取顶点( 仇。， 0 i ：，) p c 2 ) 设次小断层的两 i 堕为t z ，t z + 1 ( 1 z n 一2 ) 魁上。u z + l ，t z + 2 ，t 正n l 孟茎些坚寰主生彳= 亍崩塌，直 到c ( u 。) n l ( v s z + 1 ，z + 2 ，n 一1 ) ) ，糯蝴状态证沩0 由于 妒1 无限，所以c ( 仳z ) 1 0 n 1 由于u l