（基础数学专业论文）布尔矩阵的广义指数.pdf

布尔矩阵的广义指数 摘要 布尔矩阵的指数理论已经得到了广泛的研究本文研究布尔矩阵的三种 类型的广义指数我们着重研究第三种类型的广义本原指数和一般布尔矩阵 的第一种类型的广义幂敛指数对第三种类型的广义本原指数，我们得到了 nxn 布尔矩阵类的这种指数的最大值，刻画了极矩阵对n n 几乎可约 布尔矩阵类，也得到了类似的结果对第一种类型的广义幂敛指数，我们得 到了礼xn 布尔矩阵类，n n 可约布尔矩阵类，佗xn 临界可约布尔矩阵 类的这种指数的最大值，刻画了极矩阵最后我们对不可约布尔矩阵的弱指 数进行了讨论 a b s t r a c t t h e r ei sa ne x t e n s i v el i t e r a t u r co nt h ei n d e xt h e o r yo fb o o l e a nm a t r i c e s w es t u d i e dt h r e et y p e so fg e n e r a l i z e di n d i c e so fb o o l e a nm a t r i c e s w ef a c u 8o i lt h et h i r dt y p eo fg e n e r a l i z e d ( p r i m i t i v e ) e x p o n e n t so fa n dt h ef i r s t t y p eo fg e n e r a l i z e di n d i c e so fc o n v e r g e n c ef o rg e n e r a lb o o l e a nm a t r i c e s w e d e t e r m i n et h em a x i m u mv a l u e so ft h et h i r dt y p eo fg e n e r a l i z e d ( p r i m i t i v e ) e x p o n e n t sf o ra l ln nb o o l e a nm a t r i c e s c h a r a c t e r i z et h ee x t r e m em a t r i c e s ，i e ，t h o s eb o o l e a nm a t r i c e sw h o s et h i r dt y p eo fg e n e r a l i z e de x p o n e n t s a c h i e v et h em a x i m u mv a l u e s w ea l s oo b t a i ns i m i l a rr e s u l t so nn e a r l yr e d u c i b l eb o o l e a nm a t r i c e s w ed e t e r m i n et h em a x i m u mv a l u e so ft h ef i r s t t y p eo fi n d i c e so fc o n v e r g e n c eo f 住扎b o o l e a nm a t r i c e s r e d u c i b l em a t r i c e s ，c r i t i c a l l yr e d u c i b l em a t r i c e sr e s p e c t i v e l y ，c h a r a c t e r i z et h ec o r r e s p o n d i n g e x t r e m em a t r i c e s f i n a l l yw ed i s s c u s st h ew e a k e x p o n e n t so fi r r e d u c i b l em d ：- t r i c e s k e y w o r d s ：b o o l e a nm a t r i x ，p r i m i t i v em a t r i x ，i n d e x ，e x p o n e n t ，d i g r a p h i l a c k n o w l e d g e m e n t s 1w o u l dl i k et ot h a n km y s u p e r v i s o r ，p r o f e s s o rl i ub o l i a n i ti s h ew h o i n t r o d u c e dm et oc o m b i n a t o r i c s h eh a sb e e ng i v i n gi l l ee n c o u r a g e m e n t ， s u g g e s t i o n sa n dh e l pa l lt h e s ey e a r s it h a n kp r o f e s s o rs h a oj i a y u ，w h o h a s b e e ng i v i n gm ee n c o u r a g e m e n tf o rm yr e s e a r c h 1i n t r o d u c ti o n ab o o l e a nm a t r i xi sam a t r i xw h o s ee n t r i e sa r e0a n dl ：t h ea r i t h m e t i c u n d e r l y i n gt h em a t r i xm u l t i p l i c a t i o na n da d d i t i o ni sb o o l e a n ，t h a ti s ，i ti s t h eu s u a li n t e g e ra r i t h m e t i ce x c e p tt h a t1 + 1 = 1 l e tb 。b et h es e to fa l l ”xnb o o l e a nm a t r i c e s f o ram a t r i xa 日n ，t h ed i g r a p h ，d ( a ) ，o fai st h ed i g r a p ho nv e r t i c e s 1 ，2 ，佗s u c ht h a t ( i ，j ) i sa n a r ci f a n do n l yo 玎= 1 t h e g i r t ho fad i g r a p h di st h el e n g t ho fas h o r t e s tc y c l eo fd 7 h e nai ss y m m e t r i c ，t h e nd ( a ) i s as y m m e t r i cd i g r a p h ，w h i c hc o r r e s p o n d sn a t u a l l yt oa n ( u n d i r e c t e d ) g r a p h g ( a ) o b t a i n e df r o md ( a ) b yr e p l a c i n ge a c hp a i ro fa r c s ( u ，v ) a n d ( ，“) b ya ne d g e “u f o ra 鼠z ，i ft h e r ei s ap e r m u t a t i o nm a t r i xps u c ht h a t p a p 7 = b ，t h e n w es a yai sp e r m u t a t i o ns i m i l a rt oam a t r i xb ( w r i t t e n a b ) n o t e t h a ta vbi f fd ( a ) i si s o m o r p h i ct od ( b ) am a t r i xa b ni sr e d u c i b l ei f a 一( a g la 0 。) w h e r ea 1a n da 2a r es q u a r e ，a n dai si r r e d u c i b l ei fi ti sn o tr e d u c i b l e i ti sw e l lk n o w nt h a ti fam a t r i xa b 。i sr e d u c i b l e ，t h e n 曼。) w h e r ea a 2 2 ，a “( t 2 ) a r ei r r e d u c i b l em a t r i c e sa n dw ec a l lt h e mt h e c o m p o n e n t so fa c l e a r l y , d ( a n ) ，d ( a “) a r et h es t r o n gc o m p o n e n t so f d ( a ) f o ram a t r i xa b n ，t h es e q u e n c eo fp o w e r sa o = i ，a ，a 2 ，i sa f i n i t es u b s e r n i g r o u po f 岛t h u st h e r ei sam i n i m u mn o n n e g a t i v ei n t e g e r = k ( a 1s u c ht h a ta 2 = a 2 + f o rs o m et 1 ，a n dam i n i m u mp o s i t i v e i n t e g e rp = p ( a ) s u c h t h a ta = a p t h ei n t e g e r s = k ( a ) a n dp = p ( a ) a r ec a l l e dt h ei n d e xo fc o n v e r g e n c eo faa n dt h ep e r i o do fa r e s p e c t i v e l y 1 o如如 1 1 l山如a ，。一 a ab o o l e a nm a t r i xa b n i sp r i m i t i v ei ft h e r ei sa n o n n e g a t i v ei n t e g e rm s u c ht h a ta ”= 厶，t h ea l l o n e sm a t r i x t i l er n i n i n m m s u c hm i sc a l l e dt h e e 。p o n e n to fa ，i ti sw e l lk n o w nt h a tam a t r i xi sp r i m i t i v ei fa n d o n l yi fi ti s i r r e d u c i b l ew i t hp e r i o d1 ，t h ee x p o n e n to fa p r i m i t i v ei n a t r i xc o i n c i d e sw i t h i t , si n d e xo fc o n v e r g e n c ea n d 山i s t h eo n l yp r i m i t i v em a t r i xw i t he x p o n e n t 0 l e m m a 1 1 ( 【5 0 】) s u p p o s esi s i n t e g e r sm 0 ，q21 ，a ”= a t m + 目 a f i n i t es e m i g r o u p f o ra n ya sa n d i ia n do n l yi f m k ( a ) a n d p ( 口) b p r o o f s u p p o s em2k ( a ) a n dp ( a ) l q t h e n 仃l = ( ) + fw i t hl 0 g = 扣( o ) w i t h t 1 ，h e n c e a m = a i o ( 。) = a l 。( 8 ) + 印( 。) = 。k ( n ) + 印( 。) = n m + 。 o nt h eo t h e r h a n d ，s u p p o s eo “= n 怕t h e n m ( ) l e tm = ( ) + f w i t hf 0 ，q = t p ( a ) + rw i t h0 r p ( a ) 一1 c h o o s e 8 0s u c ht h a t p ( u ) l ( t + s ) l e tf + s = h p ( a ) t h e na m + s = a m + s + g a n dh e n c e t h i s i m p l i e s t h a tr = 0 o k ( 口) = i + s = o k ( n ) + h s = 印( n ) + a k ( o ) + 岫( 。) ：o ( 4 ) + ( + 咖( n ) 押 a k ( n ) ：扩( n ) 竹 l e m m a 1 2 ( ( 5 0 ) s u p p o s ea 毋h a st h e ，0 m a = ( a g la 0 。) w h e r ea 1a n d a 2a r es q u a r e t h e np ) = l c m p ( a 1 ) ，p ( a 2 ) ) 口 p r o o f w r i t ed = l e m p ( a 1 ) ，p ( a 2 ) ) f r o ma 2 ( 4 ) = a 2 ( 4 ) + p ( 4 ) ，w eh a v e 4 ：4 ) = a ：4 ) + 9 4 f o ri = 1 ，2 h e n c ep ( a ；) 1 2 ) ( a ) f o ri = 1 ，2 ，i m p l y i n g d i p ( a ) b yi n d u c t i o nw eh a v e a 1 = ( 坠。玺竹。a 曼。) c h o o s e 七s u c ht h a tk k ( a 1 ) + k ( a 2 ) i fa + 4 + 1 = a + 2 8 “，t h e np ( a ) i d i nt h ef o l l o w i n gw e p r o v ea + 。+ 1 = a + 2 d + 1 n o t et h a t f o ri = 1 ，2 ，钟州“= a ；+ 2 4 + 1s i n c ek k ( a 1 ) a n dp ( a i ) l d w eo n l yn e e d t op r o v e 譬k + o da ；g a ：+ 4 = ；k + 0 2 4 如c | a ：捌 a n y t e r mi n b k + o d 如g a i + 扎2c a nb ew r i t t e na s 删* t = 三辫：i f 震z k ( a 1 ) k ( a 1 ) a n dh e n c ei sat e r mi n b k + 0 2 8a i g a + 2 。一 s i m i l a r l ya n yt e r mi n # k + 0 2 4 鸽g a + 2 扣c a nb ew r i t t e na s a ；g a ：+ 2 d = 三薹a c ：a + 2 。+ 一2 。4 ；i ，f ：；：辜：竿宅f a 。， a n dh e n c ei sat e r mi n ；k + o d 冯g a ：州 i tf o l l o w st h a t 扭k + o da ；a a + 8 = 活k + 0 2 d1 4 ；g a f + 2 d 叫a n dh e n c ea + 。+ 1 = a k + 2 d + 1 口 b yl e m m a1 2 ，o n ec a ne a s i l yp r o v e t h ef o l l o w i n g t h e o r e m1 3 ( 4 1 ) 1 1 a b 。i si r r e d u c i b l e ，t h e n p ( a ) i st h eg r e a t e s te o ? n 。 $ r z o nd i v i s o ro a l lt h ed i s t i n c tc y c l el e n g t h si nd ) ，玎a b ni sr e d u c i b l e w i t hc o m p o n e n t s a l l ，a 2 2 ，a “( t 2 ) ，t h e n p ( a ) = i c m p ( a u ) ，p ( a “) ) h e n c et h ep e r i o dp r o b l e mf o rb o o l e a nm a t r i c e sh a sb e e ns e t t l e d t h e b e h a v i o ro ft h es e q u e n c eo fc o n s e c u t i v ep o w e r so fab o o l e a nm a t r i xh a sb e e n 3 s t u d i e de x t e n s i v e l yd u et oi t si n s t r i n s i c i m p o r t a n c ei ng r a p ht h e o r y , c o r n b i n a t o r i c s ，m a t r i xt h e o r ya n dt h e i ra p p l i c a t i o n si nc o m m u u i c a t i o ns y s t e m ， m a r k o v c h a i n s ，t h e o r e t i c a lc o m p u t e rs c i e n c e s ；f o rm o r e d e t a i l ss e e 1 ，4 ，8 ，2 5 l e tmb eac l a s so fb o o l e a nm a t r i c e s w ea r ei n t e r e s t e di nt h ef o l l o w i n g t h r e ek i n d so fp r o b l e m s 【1 9 ，2 5 ： ( i ) m a x i m u mv a l u ep r o b l e m ：d e t e r m i n et h e m a x i m u mv a l u ek ( m ) m a x k ( a ) ：a m ) ； ( i i ) e x t r e m em a t r i xp r o b l e m ：c h a r a c t e r i z et h em a t r i c e si ni ( m ) = a mw i t hk ( a ) = e ( m ) ) ； ( i i i ) i n d e xs e tp r o b l e m ：d e t e r m i n et h es e tk ( m ) = k ( a ) ：a m ) w eu s et h ef o l l o w i n gn o t a t i o n sf o rt h ec l a s so fb o o l e a n m a t r i c e s b n i b 。 i b 。，p r b 。 岛 s i 忍 瓦 r d nd n nb o o l e a nm a t r i c e s i r r e d u c i b l em a t r i c e si nb n m a t r i c e si nib nw i t hp e r i o dp r e d u c i b l em a t r i c e si n 取 s y m m e t r i cm a t r i c e si n 玩 s y m m e t r i cm a t r i c e si ni b n ，2 n e a r l yr e d u c i b l em a t r i c e si nb n t o u r n a m e n t si n 玩 f u l l yi n d e c o m p o s a b l em a t r i c e si nb n m a t r i c e si nb nw i t he x a c t l ydn o n z e r o so i lt h em a i nd i a g o n a l s f o rab o o l e a nm a t r i xc l a s sm ，i fn o te v e r ym a t r i xi nmi sp r i m i t i v e ，w e d e n o t et h ec l a s so fp r i m i t i v em a t r i c e si nm b yp m w el i s tt h er e s u l t so nt h e s et h r e ep r o b l e m sf o rd i f f e r e n tc l a s s e so fb o o l e a n m a t r i c e s 4 1 s c h w a r z 4 3 ： k ( b 。) = k ( p b 。) = ( n 一1 ) 2 + 1 ， a n da i ( b 。) ( = k ( p b 。) ) i f fai sp e r m u t a t i o ns i m i l a rt ot h ew i e l a n d t m a t r i x1 眠，w h e r e f 010 1 00l 眠：i ! ! 1ooo i11oi k ( p b n ) i sd e t e r m i n e db yl e w i na n dv i t e k 1 r ，s h a o 4 5 a n dz h a n g 6 7 ( 风) i sd e t e r m i n e db yj i a n ga n ds h a o 1 5 2 ，s c h w a r z 4 3 ，s h a oa n dl i 【5 4 m c ，b 。= ：p 2 2 r + 2 + 8 ：三： w h e r er = l n p j ，s = n p r ( b 。，p ) i sd e t e r m i n e di n 【5 4 ，w h i l e i ( ，玩口) i ss t u d i e di n 5 6 3 s h a o 4 8 ：k ( r b 。) = 一2 ) 2 + 2 p e r m u t a t i o ns i m i l a rt o ( 譬1 w i t ha = ( 1 ，0 ，o ) ( r 玩) i sd e t e r m i n e db yj i a n ga n ds h a o 1 5 4 h o l l a d a ya n dv a r g a 1 4 ，s h a o 【4 6 ：( p s n ) = 2 n 一2 ( p 品) = 1 ，2 n 一2 ) o n ，2 n 一2 ，w h e r eo a ，6 d e n o t e s t h es e to fo d d i n t e g e r s 。w i t ha z b ；a i ( p & ) i f f g ( a ) i si s o m o r p h i c t oap a t h o fo r d e rnw i t hal o o pa t t a c h e dt oo n eo fi t se n dv e r t e x ( d e n o t e db y 磁) 4 6 5 s r ar0a厅 、)n 日r ，【 七a d、 暑 o o 5 s h a oa n dl i 5 5 ：k ( s ) 2n i s o m o r p h i ct oap a t ha n dk ( s ) n = 2 2 ( n 2 ) ，a 矗( s 。) i f fg ( a ) i s = 1 ，- n 一2 ) i f 礼3a n d o ) i f 6b r u a l d ia i l dr o s s 7 ：k ( p n p h ) = n 2 4 n + 6 ，a n da ( p n r 。) i f f a 一z n ，w h e r e 磊 01 o0 o0 0o 10 01 0o 10 0 o o0 o0 11 0 o o 0 i r 礼5 ，a n d2 i = ( i ； k ( p n r 。1i sd e t e r m i n e db ys h a oa n dh u 5 2 7 s h a o 【4 9 d e t e r m i n e dk ( i b n p 忍) 8 m o o n 3 9 ：( 瓦) = 礼+ 2 ，a ( 瓦) i f fd ( a ) i s t h eu n i q u et o u r n a m e n t w i t hd i a m e t e r 扎一1f u pt oi s o m o r p h i s m ) a n d ( 瓦) = 3 ，4 ，住+ 2 ) ( 扎6 ) 9 ，l i ua n dl i 【2 6 】：k ( d 。，d ) = m a x 2 n - d 一1 ，( n d 一1 ) 2 + 1 ) k ( d n ，d ) a n d ( 巩，d ) a r ed e t e r m i n e db yz h o ua n dl i ui n 7 0 a n d 7 4 r e s p e c t i v e l y 2g e n e r a l i z e de x p o n e n t so fm a t r i c e s l e ta 风a n dd = d ( a ) f o ra n yo x v ( d ) ，d e f i n ee x p d ( x ) t o b et h el e a s ti n t e g e rms u c ht h a tf o re a c hv e r t e xi o fdt h e r ee x i s t saw a l k f r o ms o m ev e r t e xi nxt oi o fl e n g t hm i fn os u c hme x i s t s ，t h e nd e f i n e e x p d ) = 。 f o r “v ，d e n o t ee x p d ( “) = e x p d ( 钍 ) i fw ec h o o s et oo r d e rt h e v e r t i c e so fdi ns u c haw a yt h a t e x p d ( u 1 ) se x p d ( 札2 ) s e x p d ( u n ) 6 t h e nw ec a l le x p d ( 女) t h ek - t hf i r s tt y p eo fg e n e r a l i z e d ( p r i m i t i v e ) e x p o n e n t o fa ，d e n o t e db ye x p ( a ，k ) l e t b ea ni n t e g e rw i t h1s smt h e n f ( a ，) = m i n e x p d ( x ) ：x v ( d ) a n dl x i = ) a n d f ( a ，) = m a x e x p d ( _ x ) ：x v ( d ) a n dl x l = ) a r ec a l l e dt h ek - t hs e c o n dt y p ea n dt h ek - t ht h i r dt y p eo fg e n e r a l i z e de x p o n e n t sa r e s p e c t i v e l y w ea l s ow r i t ee x p ( d ，) ，f ( d ，k ) a n df ( d ，k ) f o re x p ( a ，) ，f ( a ，) a n d f ( a ，) ，a n dc a l lt h e mt h ek t hf i r s t ，s e c o n d ，a n dt h i r dt y p eo fg e n e r a l i z e d ( p r i m i t i v e ) e x p o n e n t so fd i fd = d ( a ) w i t ha 鼠 i ff i n i t e ，t h ek - t hf i r s tt y p eo fg e n e r a l i z e d e x p o n e n to fai st h es m a l l e s t p o w e ro fa f o rw h i c ht h e r ei sak na l l1 ss u b m a t r i x t h ek - t hs e c o n d t y p eo fg e n e r a l i z e de x p o n e n to fa i st h es m a l l e s tp o w e ro faf o rw h i c hs o m e k ns u b m a t r i xh a sn oz e r oc o l u m n a n dt h ek - t ht h i r dt y p eo fg e n e r a l i z e d e x p o n e n to fa i st h es m a l l e s tp o w e ro faf o rw h i c ha n y 女ns u b m a t r i xh a s n oz e r oc o l u m n c o n s i d e ram e m o r y l e s sc o m m u n i c a t i o ns y s t e m ，w h i c hi sr e p r e s e n t e db ya d i g r a p hd 【4 ，8 ，2 5 s u p p o s et h a ta tt i m et = 0 ，kv e r t i c e so fd e a c hh o l d s o n eb i to fi n f o r m a t i o n a tt i m et = 1e a c hv e r t e xw i t hs o m ei n f o r m a t i o n p a s s e st h ei n f o r m a t i o nt oe a c ho fi t sn e i g h b o r sa n dt h e nf o r g e t si t s i n f o r - m a t i o n b u ti tm a yr e c e i v ei n f o r m a t i o nf r o ma n o t h e rv e r t e x t h es y s t e m c o n t i n u e si nt h i sw a v ai fkv e r t i c e so fde a c hh o l d so n eb i to fi n f o r m a t i o nw i t hn ot w oo f t h ei n f o r m a t i o nb i t st h es a m ea tt i m et = 0 ，t h es h o r t e s tt i m et o d i s s e m i n a t ea l lt h ei n i t i a lkb i t so fi n f o r m a t i o ni se x p d ( ) bi ft h ei n i t i a lkb i t so fi n f o r m a t i o na r et h es a m e t h es h o r t e s tt i m ei t t a k e sf o ra l lv e r t i c e st ok n o wt h ei n i t i a lb i ti n f o r m a t i o ni s ，( d ，) 7 ei fw ec h o o s et h ei n i t i a lav e r t i c e sw i t ht h es a m ei n f o r m a t i o na tr a n d o m ，t h es h o r t e s tt i m ei tt a k e sf o ra l lv e r t i c e st ok n o wt h ei n i t i a lb i t i n f o r m a t i o ni sf ( d ，a ) l e te ( a ，) e x p ( a ，k ) ，f ( a ，) ，f ( a ，k ) ) b eaf u n c t i o no faa n dma b o o l e a nm a t r i xc l a s s s u p p o s ee ( a ，k ) 。f o ra m w ea r ei n t e r e s t e d t h ef o l l o w i n gp r o b l e m s ( i ) m a x i m u m v a l u ep r o b l e m ：d e t e r m i n et h em a x i m u mv a l u ee ( m ，k ) = m a x e ( a ，k ) ：a m ) ； ( i i ) e x t r e m em a t r i c e sp r o b l e m ：c h a r a c t e r i z et h em a t r i c e si ni ( m ，) = a m w i t he ( a ，k ) = e ( m ，) ； ( i i i ) i n d e xs e tp r o b l e m ：d e t e r m i n et h es e t 言( m ，女) = e ( a ，) ：4 m ) 2 1g e n e r a l i z e de x p o n e n t so fp r i m i t i v em a t r i c e s 2 1 1t h ef i r s tt y p eg e n e r a l i z e de x p o n e n t s s u p p o s e t h a ta b 。i sp r i m i t i v e l e td = d ( a ) ，sb et h eg i r t ho f d ，a n d b ea ni n t e g e rw i t h1 曼n s u p p o s ef u r t h e rt h a tti st h el a r g e s to u t d e g r e e o fv e r t i c e so ft h es h o r t e s tc y c l e g t h e n 3 1 ，4 0 ，e x p ( a ，k ) s ( n t ) + ， f r o mw h i c hi tf o l l o w st h a t 5 e x p ( a ，k ) s ( n 一2 ) + k a n o t h e ri n e q u a l i t y f r e q u e n t l yu s e di s 5 je x p ( a ，k ) 茎e x p ( a ，一1 ) + 1 s o m er e s u l t sa r el i s t e db e l o w 1 b r u a l d ia n dl i u 5 ： e x p ( p b 。，k ) = n 2 3 n + k + 2 ，e x p ( p & ，k ) = n 一2 + k 画币( p b 。，) a n di 昂( 尸& ，k ) a r ed e t e r m i n e db ys h a o e ta 1 【5 7 】：a g f f - p ( p b 。，k ) i f fa 一眠，a 6 面( p s n ，k ) i f fg ( a ) i si s o m o r p h i ct oa p a t hw i t hal o o pa t t a c h e dt oo n eo fi t se n dv e r t e x ( d e n o t e db y 磁) i f k 2 ，a n dg ( a ) i si s o m o r p h i ct o 磁，t h eg r a p h o b t a i n e db ya d d i n ga 8 l o o pt oa n o t h e re n dv e r t e xo f 焉o r ac y c l e ( w h e nni s o d d ) i fk = 1 s h a oe ta 1 57 a n dl i ua n dz h o u 【3 1 p r o v e dt h a tt h e r ee x i s tas y s t e mo f g a p si ne x p ( p b 。，) ，s h e n 【6 1 d e t e r m i n e d 筇( p b 。，1 ) a n dt h e nm i a o a n dz h a n g 【3 7 d e t e r m i n e d4 筇( p b 。，k ) f o r2 n l i a n ds h a o 1 8 ，5 3 p r o v e dt h a t 百吊( 尸& ，七) = 1 ，一，n 一南+ 2 ) f o r1 k s 孔一l 2 l e t s n ，r b et h ec l a s so fp r i m i t i v es y m m e t r i cm a t r i c e sw h o s ed i g r a p h h a so d dg i r t hr t h e nb r u a l d ia n ds h a o 【9 p r o v e d e x p ( ，胪n - l + ( k - 一2 r 曼k n ， l 丁k + l j 一1 ，r 一1 ) 1 r 一1 a i 两( & ，) 册g ( a ) i si s o m o r p h i ct og ”，w h i c hi s t h eg r a p ho b r a i n e db ya d d i n ga ne d g eb e t w e e na v e r t e xo fac y c l eo fl e n g t hra n da t o n e o f t h ee n dv e r t i c e so f a p a t ho f o r d e r 扎一r i f i f k 2 ，o r i s o m o r p h i e t og n 1 o rt h eg r a p ha d d i n gal o o pa tt h eo t h e re n dv e r t e xo ft h ep a t h i f = 1 e x p c 尸兄。，* ，= i n i 2 三- i 4 i n 三+ i 5 ：+ e ! 三i 三z 一2 i 面( 尸r ，k ) i sc h a t r a c t e r i z e di nz h o u 7 5 _ 4 l e td b et h ec l a s so fn e a r l yd e c o m p o s a b l em a t r i c e si nb n ( n o t e t h a td 品凡) l i u ( 2 0 】：e x p ( d n n ，k ) = n 一1 z