（应用数学专业论文）计算机模拟与图上的离散动力系统.pdf

摘要 摘要 奉论文的主要研究对象是几类无向图上或有向图上的离散动力系统。首先 我们介绍无向图上的贯序动力系统( s d s ) 的概念，它由以下几个要素构成： ( 1 ) 一个有限的，用l ，2 ，n 顶点标号的无向图g ，每个顶点都有一个状 态，设这些状态属丁某个数域d ； ( 2 ) 对廊图中的每一个顶点o ，l isn ，都 有一个函数e g ：d ”一舻；( 3 ) n 阶置换群晶中的一个排列7 r 。函数只g 根 据第z 个顶点自身的状态和它邻点的状态来决定i 点被更新后的状态，而并不 改变其它顶点的状态。排列”表示图中各点被更新的前后顺序。把函数e g 按 照”的顺序复合起来，就得到了一个图g 上的贯序动力系统( s d s ) ： f ，g ，7 r 】= b ，g 最。g 异。，g ：d nh 矿。 对，其它几类离散动力系统：无向图上的并序动力系统( p d s ) ，有向图 上的贯序动力系统( s d s ) ，有向图上的线性贯序动力系统( l s d s ) ，无向图 上的随机并序动力系统( r p d s ) 和无向图上的字贯序动力系统( s d s w ) ， 其定义可以类似地给m 。 论文总共由五审构成。 第一章为介绍部分，陈述了课题的背景并给出了一些定义、符号及已知的 结果。 第二章研究了四种无向图上的离散动力系统：d b p d sf 0 r ，g 1 ，d 戽s d s 0 r ，g ，】，o 尼p d si 0 r ，g 1 和0 b s d s | 0 r ，g ，1 。对每一个研究对 象，部用一个等价的引理去表示它在状态向量上的作用。这种等价性在于每个 状态向量都和一个图的琐点了集一一对应。事实表明，这种方法在研究动力系 统的性质方面是实用的和有效的。这章的主要目的是用图的结构性质来刻画动 力系统本身所具有的属件。这市的主要结果有： 1 动力系统p d s 【d r ，g 】的宽度等于图g 的直径。 2 动力系统p d sf 0 r ，g 的宽度等于l 。 3 ，动力系统p d s 【o r ，g 】的每一个轨道( 即有限圈) 都是2 长的。 i i i 摘要 4 在动力系统p d s 【0 r ，g i 的像图中，状态( o ，0 ，、o ) 具有极大的入度 且此入度值等j 图g 的拧制集个数。 5 对r 仔意的排列，r r ，动力系统s d s 0 r ，g ，7 r 】的宽度不超过图g 的直 径；而且，存在一个排列口s ：使得s d s 【o j r ，g ，盯】的宽度等于图g 的 直径。 6 动力系统s d s 【0 r ，g ，7 r 1 的宽度等于1 a 7 ，动力系统s d s o j r ，g ，7 r 】的周期点和图g 的独立集之间是一一对应的。 第三章主要研究有向图上的线性贯序动力系统( l s d s ) 我们首先介绍 了一种矩阵方法，它可以处理一般的线十牛贯序动力系统，这里的“一般”是指 琐点状态属f 一般的代数，局部函数足任意的线性函数。接着，我们研究布尔 代数上的、以d 兄为局部函数的线性贯序动力系统的性质。这类动力系统被称 为有向图d 上的o 兄一s d s ，记作f d r ，d ，r 1 。钿尔知阵理论在讨论中起到了非常 关键的作用。最后对另一种有向图上的线件贯序动力系统，p a r - s d s ，也做 了一些讨论。这章的主要结果有： 8 卜面四个结论互相等价：( a ) d 中不包含有向圈。( b ) 存在整数m l 使得 o r ，d ，”】”( x ) = ( 0 ，0 ，o ) 对任意x 赡都成立。( c ) 像 图r 【0 r ，d ，丌】是连通的a ( d ) f j x 【d r ，d ，丌】= f ，x 0 r ，d ，7 r 】u p e r 0 r ， d ，7 r 】- ( o ，0 ，o ) 。 9 f 面血个结论互相等价：( a ) 动力系统f o j r ，d ，丌】是可逆的。( b ) 动力系 统【o 兄d ，7 r 】是恒等映射。( c ) 像图r 【0 r ，d ，r 】是顶点不交的有向圈的 并。( d ) 像图r 0 r ，d ，7 r l 是2 ”个环的并。( e ) 图d 是竹个环的并。 l o 对仃意的x ( o ，0 ，o ) ，存在整数m 1 使得 o | r ，d ，r 】”( x ) = ( 1 ，1 ，1 ) 当且仅当图d 是强连通的并且满足条件( ) 。 1 1 动力系统f 尸a r ，d 丌l 是可逆的当且仅当图d 的每个顶点都有自环。 在论文的第四章中，我们构造了一种无向图上的随机并序动力系统 ( r p d s ) 【兄o n ，g 1 。证明了由r p d s 帆，g l 诱导出的状态序列是一个齐次的 马尔可夫链。同时还得到了两个状态向量在r p d s 的作用下互达的充分必要条 件。返章的主婴结果有： i v 摘受 1 2 随机向量序列x ，【r 口n ，g 】( x ) ， r m ，g 】2 ( x ) ，【r 肌，g 3 ( x ) ，构成一个齐 次的马尔可夫链。 1 3 ，两个状态向量，= ( l ，1 2 ，l 。) 贬和，= o l ，如，矗) 叼在 由r p d s 兄，g 】诱导出的马尔可夫链中互达当且仅当存在整数使 得( j ，i ，) 和( z ，) 在图g 中部是适应的。 论文的最后一章讨论了s d s 的另一种推广形式。把s d s 【f ，g ，7 r 】中的排列7 r 用一个m 上的字f 来代替，就得到了s d s w 【f g ，科。我们研究了0 皿s d s w 的性质并得到了一些结果。这章的主要结果有： 1 4 动力系统【d 兄g ，引的宽度等于l 。 1 5 集合j p e r i o r ，g ，引uf j x i v 0 r ，6 r ，酬和g 的( 叫e f e m ) 一伪独立集 之日j 存在一一对应关系。 关键词：贯序动力系统( s d s ) ，像图，轨道，宽度，周期点，固定点，马尔可 夫链，适应，无圈定向，c 一伪独立集，随机图 v a b s t r a c t a b s t r a c t w bs t u d y8 0 m ec l a 船e so fd i 8 c r e t ed y l l 锄i c “s y s t e 脚0 ng r a p h sa i l dd i g r a p l l s f i r s t ，w ei n t r o d u c eas e q u e n t l a ld y n a 肌c a ls y s t e m ( s d s ) o nag r 印h ，w h i c hc o n - s i s t so ft h ef o l l o w i n gd a t a ：( 1 ) a 矗n l t el a b e l e dg r a p hgw i t hv e r t e x8 e t ，w h e r e e a c hv e r t e xh a 8a8 t a t ei n8 0 m ed o m a i nd ，( 2 ) av e r t e x1 a b e l e dm u l t i 一8 e to ff u n c - t l o n s ( 只，g ：d “h 皿“) ；，a n d ( 3 ) ap e r m u t a t i o n 丌岛t h ef u n c t i o n 只，gu p d a t 铭 t h es t a t eo fv e r t e ) 【ta saf u n c t i o no ft h es t a t 朗o fv e r t e x 。a n di t sg - n e i g h b o r 8 a n dk a v t h e 乱a t 0 fa uo t h e rv e r 七i c 朗矗x e d t h ep e r m u t a t i o n7 rr e p r e n t sa g v e r t e xo r d e ra c c o r d i n gt ow h i c ht h ef u n c t i o 璐只，ga r e 印p l i e d b yc o m p 呻 i n gt h ef u n c t i o l l s 只，gi nt h eo r d e r 百v e nb y7 rw eo b t a i na q u e n t i a ld y i l a m i c a l s y s t e m ( s d s ) o ng ： 【f g ，7 r 】= 最，g 吃，g f k ，g ：护_ _ d “ t h ed e 丘n l t i o i l so fo t h e rc 1 船s e 8o fd i s c r e t ed y n a m i c 础8 y s t e m s ：p a r “i e ld y - n 锄i c a ls y s t e i i l s ( p d s ) o ng r a p l l s ，s e q u e n t i a ld y n a m i c a ls y s t e m s ( s d s ) 0 nd i - g r a p h s ，l i n e a rs e q u e n t i a ld y n a i i l i c a ls y s t e i 璐( l s d s ) o nd i g r a p h 8 ，r a l l d o mp a r a u e l d y n 啪l c a ls ) 8 t e m 8 ( r p d s ) o n 铲a p l l 8a i m8 e q u e n t i a 王d y n a m i c “g y 8 t e i 璐i nw o r d ( s d s w ) o ng r 印h s ，c a nb e 百v e na n a l o g o l l s l y t h i st h e s i sh a sf i v ec h a p t e r s c h 印t e r1i st h ei n t r o d u c t i o n ，i nw h i c hw e 百v et h eb a c 始r o u n di n f o r m a t i o n a n dn e c e s s a r yd e 矗n i t i o i l sa 王l d1 i b t8 0 m ek n o w nt h e o r e m s i nc h a p t e r2 ，w ea r ec o n c e n t r a t e do nf o u rl 【i n d so fd y n 锄i c a ls 1 ，s t e 瑚o n 酽a p h s ：0 r p d s o | r ，g 】，d 尼s d s 0 j r ，g ，叫，0 尼p d s 【d r ，g 】a n d d 皿 s d s 【d 尼g ，丌】_ f 0 re a c ho ft h 鹤e8 y s t e 脚，w ep 瑚e n t 缸e v a l u a t i o nl e m m a o nt h eu p d a t eo ft h eg l o b a l8 t a t ev e c t o r 8 t h es t a t ev e c t o r 8a r er e p r e 靶n t e db y t h es u b s e t so ft h ev e r t e x8 e to ft h ed e p e n d e n c yg r a p h s u c he v a i u a t i o n8 c _ h e r n 朗 p r o v i d eap o w e r f u lt o o li ns t u d y l n gt h ep r o p e r t i 朗o ft h ed y n 删c a l8 y b t e 脚w b d e m o n s t r a t et h a tm a n yp r o p e r t i e so ft h ed y n a m i c a ls y s t e 瑚c a nb ec h a r a c t e r i d b yt h ed e p e n d e n c yg r 印1 1 8 t h ef o l l o w i n gr e s u l t sa r eo b t a i n e d ： a b s t r a c t 1 t h e 而d t ho f p d s 【d r ，g 】i se q u a l t o t h ed i 锄e t e ro f g 2 t h ew i d t ho f p d s 【0 r ，g 】i 8e q u a lt ol 3 a n yo r b i t ( i i m i tc y c l e ) o fp d s 【0 尺，g lh 1 e n 或h2 4 t h em a x i m a li n d e g r e ei nt h ef u n c t i o n “d i 口a p ho fp d s 【0 r ，g i 8e q u 越 t ot h en u m b e ro fd o m i n a t l n g t 8o fg ，w h i c hi sr e a c h e db yt h es t a t ev e c t o r ( 0 ，0 ，0 ) 5 t h ew i d t ho fs d s 【o r ，g ，卅d o 铭n o te x c e e dt h ed i 锄e t e ro fgf o ra n y 丌r 凡i o r e o v e r ，t h e r ee x i s t sap e r m u t a t i o n 盯& 8 u c ht h a tt h ew i d t h o f s d sp r ，g 盯】i se i a l t o t h ed i a m e t e ro f g 6 t h e 而d t ho f s d s 【0 r ，g ，卅i se q u a lt o1 7 t h e r el sab 巧e c t i o nb e t w 咖t h ep e r i o d i cp o i n t 8o fs d s 【0 r ，g ，r 】a n d t h ei n d e p e n d e n t8 e t so fg c h a p t e r3c o n c e n t r a t 朗o nt h ei i n e a r8 e q u e n t i a ld y n a m i c a l8 y s t e m 8 ( l s d s ) o nd i g r a p l l s 、v bi n t r o d u c et h em a t r i xm e t h o df o rag e n e r a ll s d s ，f o rw h i c ht h e a l g e b r 诲g e n e r a la n dt h el o c a if u n c t i o n sa 糟a r b i t r 钳yl h e a r c t i o 璐t h e nw e c o n s l d e rt h el s d so v e rt h eb 0 0 1 e a na l 聆b r a ，w i t ht h e1 0 c a lf u n c t i o i l 8 “d 彤w b c a l l i t t h e d 岳s d so n t h ed l g r a p h da l l dd e n o t e i tb y 【p r ，d ，7 r 】，w h e r e d i 8a d i g r a p hw i t ht h ev e r t e xs e tm t h et h e o r yo fb 0 0 l e a nm a t r i c 皤p l a y 8ak e yr o k i nt h ea n a l y s i s i nt h ee n do fc h a p t e r3 ，a n o t h e rk l n do f8 p e c i a ll s d s ，p a r s d s o nd l g r a p 量l s ，i 8a l s oc o n s i d e r e d t h ef o l l o w i i l gr 髑u l t 8a r eo b t a i n e d ： 8 t h ef o l l o i n gf o u rs t a t e m e n t sa r ee q u i v a l e n t ：( a ) di 8a c y c c ；( b ) t h e r e 锵 i s t sa n i n t e g e r m 1s u c h t h a t d 尼d ，7 r p ( x ) = ( o ，o ，o ) f o ra n y x 赡；( c ) r d r ，d ，丌】i sc o n n e c t e d ；( d ) f j x 【0 r ，d ，丌】= f ，x 【d r ，d ，7 r 】u p e r 【o r ，d ，7 r 】= ( o ，o ，一，o ) 9 t l l ef o u o w i n g 丘v es t a t e m e n t sa r ee q u l v 越e n t ：( a ) 【d r ，d ，丌】1 8i n v e r t i b l e ； ( b ) 【o r ，口，丌】塔t h el d e n t l t ym 印p l n g ( c ) r o 兄，d ，7 r mt h eu l l i o no fs o m e v c r t c x - d l 旬o l l l td l r t c dc y c l 锱，( d ) r 【d r ，d ，7 r i st h eu i l i o no f2 “l o o p s ；( e ) di st h eu n i o no f nl o o p 8 v i i a b s t r a c t 1 0f o ra n y8 t a t ev e c t o r x ( 0 ，0 ， t h a ti o r ，d ，7 r 】”( x ) = ( 1 ，l ， w i t ht h ec o n d i t i o n ( ) 一，0 ) ，t h e r ee x i 8 t smi n t e g e rm l8 u c h ，1 ) i fa n do n l yi fd i 8s t 姗西yc o l l i l e c t e d 1 1 p a r d 丌 i b i n v e r t i b l e i fa n do n l y i fe v e r yv e r t e xo f dh 舶a 1 0 0 p i nc h a p t e r4 ，w ec o i l s t r u c tbr a n d o mp a r a l l e ld y n a i n i c a ls ) 瑁t 锄( r p d s ) 【兄o n ，g 】o nag r 8 p hg w b8 h o wt h a tt h ei m a g e8 e q u e n c ei n d u c e db yi t e r a t i n gt h e f u n c t i o nr p d s 【r o 扎，g i 88h o m o g e n e o u sm a r l c h a i n m o r e o v e r ，w ep r e s e n t ai l e c 鹤s a r ya 1 1 ds u m c i e mc o n d i t i o nf o rw h l c ht w os t a t ev e c t o r sc a nc o m m u n i c a t e w l t he a c ho t h e r t h ef o l l d w i n gr e s u l t sa r eo b t a l n e d ： 1 2 t h er a n d o mv e c t o rs e q u e n c ex ，【兄口n ，g 1 ( x ) ，【r 肌，g 】2 ( x ) ， r 帆，g 3 ( x ) ， i sah o m o g e n e o u sm 村k o vc h a i n 1 3 t w 08 t a t e v e c t o r 8 ，= ( t 1 ，幻，) 嵫a n d j = 0 1 ，j 2 ，矗) 赡c a n c o m m l l n l c a t e i n t h e m a r hc h a i n i n d u c e db ya r p d s 胁他，g 】i f a n do n l y i ft h e r ee x l s t sa ni n t e g e r 七8 u c ht h a tb o t h ( ，) a n d ( 正j ) 射ea d a p t i v ei n t h e 岔a p h g i nc h 印t e r5 ，w ed l s c u 鹦a n o t h e rg e n e r a l i z a t i o no fs d s 鼬p l a c i n gt h ep e r 伽t a t i o n7 r l n 8 s d s g ，丌】矾t haw o r d fo n ，w eg e ta q u e n t i a ld y l l 锄i c a l s y s t e m i nw o r d ( s d s w ) 只g ，“w j8 t u d y s d s w 暇g ，科a n dp r e n t a n u 瑚b e r o fp r o p e r c i e 8 t h ef o l l o w i n gr e s u i t 8a r eo b t a i n e d ： 1 4 t h ew i d t ho f v d r - s d s w 【0 r ，g ，刳i se q u a lt o1 1 5 t h e r ei 8ab 巧e c t i o nb e o w e e np e r 【0 r ，g ，翻uf ，x 【0 r ，g ，刳a i l dt h e ( 【n 】剧e m ) 一p s e u di n d e p e n d e n t8 e t 8o fg k e yw o r d s ：s e q u e n t i a ld y n a m i c a ls y s t e m ( s d s ) ，f u n c t i o n md i g r a p h ，o r b i t ，w i d t h ， p e r m d i cp o i n t ，缸e dp o i n t ，m a r 妣rc h a i n ，a d a p t i v e ，a c ”l i co r i e n t a t i o n ，d p s e u d i n d e p e n d e n ts e t ，r a n d o mg r a p h a m ss u b j e c tc l 硒s i 矗c a t i o n ( 2 0 0 0 ) ：3 7 8 9 9 ，3 7 n 9 9 ，6 0 j 1 0 ，6 8 q l o ，6 8 q 8 0 a b b r e v i a t l o n f u u n a m e a b b r e v i a t i o n a b b r e v i a t i o n p a g en u m b e r $ $ 十 $ $ $ $ 车 女奉 s e q u e n t i “d y n a m i c a ls y s t e m p a r a l l e ld y n a m i c a l8 y s t e m 1 i n e a r q u e n t md y n 锄i c a ls y 8 t e m r a n d o mp a r a l l e ld y n a l i c a ls y 8 t e m s e q u e n t i “d y n a m i c 8 l8 y s t e mi nw o r d d 尺( 。1 ，。) = z 1v v 2 k 0 r ( z 1 ，z ) = 瓦v _ _ - 两i s d s p d s l s d s r p d s s d s w o rf u n c t i o n n o rf u n c t i o n a d 扣1 ，z 女) = z 1 z a n d f u n c t i o n a d ( z l ，r ，z k ) = 五丽_ 罚i | p a r 洳1 ，一，z ) = z 1 + 一+ z k n a n df i l n c t i o n p a rf i m c t i o n p a g e4 p a g e l 0 p a g e2 5 p a g e4 7 p a g e5 8 p a g e6 p a g e6 p a g e6 p a g e6 p a g e6 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：鄯洁 碱年牛月日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月，日 各密级的最长保密年限及书写格式规定如下： 内部5 年( 最长5 年，可少于5 年) 秘密1 0 年( 最长1 0 年，可少于1 0 年) 机密2 0 年( 最k2 0 年，可少于2 0 年) 一。，+ ，一。- 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 郑洁 冽年午月 日 c h 印t e r1 i n t r o d u c t i o n c h a p t e r1 i n t r o d u c t i o n 1 1 b a c k g r o u n d c o m p u t e rs i m u i a t i o n sa r e 璐e dm o r ea n dm o r e 丘e q u e n t l yi nt h em o d e m t e c h n o l o g l c 8 ls o c l e t y t h e yh a eb e m eau s e f mp a no fm o d e l i i 堰m a n yn a t u r a l s y 8 t e 脚mp h y 8 i c 8 ，c h e m j 8 t r y 甜l db i o l o g ya n dh u m a n8 y s t e 瑚i ne c o n o 血c sa n d 8 0 c i a ls c l e n c e i ts e e 脚l i m c u i tt og i v eag 蛐e r a | d e 6 n i t i o nf o rac d 仃l p “t e rs m “口t n h o w e v e r ，m a n ye x a m p l e s8 h o wt h eg e n e r i cs t r u c t l i r eo fc o m p u t e r8 i m l l l a t i o 珊 o n e t y p i c a l l y 丘n d st h a ti nac o m p u t e r8 i m l a t i o nt h e r ei 8a8 e t ( 丘n i t eo ri 血n i t e ) o f a g e n t so re n c i t i e 8w i t hc e r t a i np r o p e r t l e so rs t a t e sa tag i v e nt i m e t h ee n t i t i 朗 a r e ，r o u g h l y ，t h em o s tr e 丘n e dg r a n u l a r i t y o re q u i v 蛆e n t l y ，t h el o w e 8 tl e v e lo f 盼 g r e g a t l o n ，o ft h e8 i m u l a t e ds ”t e ld e c o m p o s i t i o n f o re ) 【锄p l e ，卸e n t i t yc o u l d b eap a r t l c ki na8 i m u l a t i o no fan u i d ，av e h i c l ema t r a n s p o r t a t i o ns i m u l a t i o n ， o rat r a d e ri nas i m u l a t i o no fam a r l ( e t a n yg e n e r a lt h e o r ym 璐tb ei n s e n s i _ t l v et ow h e t h e rt h ee n t i t i e 8a r ee x p n c i t l yo ri m p l i c i t l ye n c o d e d ，8 dt 0a n yo t h e r s p e c m cr e p r e 8 e n t a t i o n a ld e t a n sr e l a t e dt ot h ee n t i t i 髑t h e 1 s e l v 鹤t h ee n t i t i 鹤 c a nr e t r i e v ei n f o r m a t i o nf r o mo t h e re n t i t i 鹤，璐u a l l yo i l l yf 如mt h 0 8 ei nt h e i r 嗍 v l c l n l t y ，t h ee n t i t i 档t h e nu p d a t et h e i rs t a t e 8b a s e d0 nt h e8 t a t 髑0 ft h e m s e l v e 8 a n dt h ei n f o r m a t i o nt h e yr e t r i e v e t h e r e 祈nb es o m eh n do f8 c h e d u l i n gt h a t t a l 【e sc a r eo ft h eu p d a t eo r d e r t h e r el sac o m p e l h n gn e e df o rb a s i ct h e o r e t i c 出f o u n d a t i o 璐f o rc o m p u t e r 1 c h a p t e r1 i n t r o d u c t i o n s i m u l a t i o n s ，w h e t h e rt h ei s 8 u ei nq u e 8 t l o ni sr e l a t e dt ot h ea n a l y s i so fac o m p l e x 8 y s t e ml l s i n gc o m p u t e rs i m u l a t i o i l 8 ，c o m p u t a t i o n a l l ye m c i e n t8 i m u l a t i o nd e s i g n ， o rt h ed e 矗n i t l v ev a l i d a t l o no fa8 i m u l a t i o n i i l1 9 9 8 ，b a r r e t ta n dr e i d y 8f 7 ，8 ，9 ， 1 0 ，3 6 ，3 7 ，3 8 】b e g a na8 e r i 髑o fs t u d i e 8t oe 8 t a b l i s ham a t h e m a t i c a lf o u n d a t i o n f o rat h e o r yo fc o m p u t e rs i m u l a 乞l o n 8 v i e we a c he n t i t y 鹅av e r t e xi naf 印h ， w h e r et w ov e r t i c e sa r ea d j a c e n ti ft h ec o r r e s p o n d i n gt w oe n t i t i e 8c a n m r n u i l i c a t e i n f o r m a t i o nw l t he a c ho t h e r a s 8 0 c i a t ea8 t a t et oe a c hv e r t e xo re n t i t vw h i c hc a i l b eu p d a t e da st h es y s t e me v o l 、髑f i 】【a no r d e ro nt h ev e r t i c 鼯t h a tr e p r e s e n t 8 t h eu d d a t eo r d e ro ft h ee n t i t i e 8 t h i st h e s l sc o n t i n u e sa i l dd e v e l o p st h e i rr 髑u l t s t h ee m p h a s i s0 ft h i st h e 幽 l so nh o wt oo b t a i ni m p o r t 缸ti n f o r m a t i o na b o u ta 8 i m u l a t i o na n di t 8g l o b a l b e h a v l o rb a s e do nl o c a lk n o w l e d g e ，w i t h o u ta c t u a l l yp e r f o r m i n gc o m p u t e rr 哪 o u r8 t t e n t l o ni 88 t i l if o c i l s e dt ow h a tw ec a l l8 i m d ks i m u l a t i o 瑚：曲：n u l a t i o 璐 i nw h l c ht h el o c a lm a p p l n 9 8t h e m 8 e l v 郎d on o tc h a n g ed u r i n gt h ec o u r 8 eo ft h e s i m u i a t i o n s l a t e rw ee ) 【p e c tt oe 妣e n do u ri n v 鹤t 培a t i o nt ot h eb r o a d e rc l a s s 朗 o f8 y s t e n l s 1 2d e f i n i t i o n sa n dn o t a t i o n s m o s ts y m b o l sf r e q u e n t l yl l s e di nt h et h e s i sa r el i s ti n7 工曲l e1 rt h e8 y m b o l s n o t 磬v e nh e r e ，c a l lb ef o u n de i t h e ri nt h e i rc o r r e s p o n d i n gc h a p t e 瑙祈t hf u l l d e t a l l so ri nr e f e r e n c 国【1 3 ，1 7 ，2 5 】_ f 1 r s t ，w er e 、，i e wt h eb a s i cd e 丘n i t i o nf o rs e q u e n t i a ld y l l 锄i c a l8 y s t e i i l 8 ( s d s ) ， w h l c hw 嬲i n t r o d u c e db yb a r r e t ta i l dr 启i d y 8 【7 ，3 6 】i n1 9 9 8 o t h e rc o r r e l a t i v e c o n c e p t sd i s c 嘲e di nt h et h e 凼，f o re x 啪p i e ，p a r 以1 e ld y n a m i c a l8 y 8 t e 脚( p d s ) ， h n e a r8 e q u e n t i 村d y n a n l i c a l8 y s t e 脚( l s d s ) ，r a n d o mp a r a l l e ld y n 眦i c a ls y s t e 瑚 ( r p d s ) ，s e q u e n t i a ld y n 啪i c a ls y 8 t e i n 8i nw o r d s ( s d s w ) ，埘1 lb eg i v e ni nc h 印t e r 2 ，3 ，4a n d5 ，r e s p e c t i v e l yt h e ya r ev a r i o l l sg e n e r a l i z a t i o n so fs d s as e q u e n t i a ld y n a m i c a l8 y s t 咖( s d s ) i ga s s u m e dt ob eb u i l to nag r a p h g = ( ve ) ，w h i c hi sc a l l e dt h ed e p e n d e n c 鲈卿 t h eg r 印hgh 鹪t h ev e r t e x s e ty = mf 0 re a c hv e r t e xl ，1s f 扎，t h e r ei s88 t a t e 如i n8 0 m ed o m a i nd c h 印t e r1 i n t r o d u c t i o n t a b l e1 ：n e q u e n t l yu s e ds y i n b o l s n o t a n o n i n t e r p r e t a t i o n d ag e n e r “d o m a i n 2 t h eb l n a 。y 矗e l d o 1 昭 t h e8 e to f0 一lv e c t o r so fd i m e n s l o n 咒 ( a ，e ，0 ) a na l g e b r aw i t ht h ea d d i t l o noa i l dm u l t l p l i c a t i o n 固 g = ( k e ) ag r a p hw l t hv e r t e ) 【s e ty = ha n de d g e8 e te o ( g ) t h e 衄m b e ro fa c y c l i co n e n t a t l o 璐o fg d = ( k a )a d i g r a p h w i t hv e r t e xs e t y = n a n da r c8 e t a 习n t h es e to f 甜ld i g r 印h 8w i t h 凡v e r t i c e 8l a b e l e d 嬲l ，2 ，佗 a 曲【d 】 t h ea d j a c e n c ym a t r i 】 o ft h ed i g r a p hd a 【d 】 t h ea r cs e to f t h ed i g r a p h d 鼠 t h es e to fa l lp e m u t a t i o l l 8o nl ，2 ，住 n 。6 i nt h ep e r m u t a t i o n7 r ，6i 8o nt h el e f to f