图动态系统

在数学中，图动态系统的概念可以用来捕捉在图或网络上发生的广泛过程。对GDS的数学和计算分析的一个主要主题是将其结构属性（如网络连通性）和由此产生的全局动态联系起来。关于GDS的工作考虑了有限图和有限状态空间。因此，研究通常涉及图论、组合学、代数和动力系统等方面的技术，而不是微分几何。原则上，人们可以定义和研究无限图上的GDS（例如蜂窝自动机或概率蜂窝自动机）。Zk{displaystylemathbb{Z}}{k}}。{k}}或包含一些随机性时的相互作用的粒子系统），以及具有无限状态空间的GDS

一个图动态系统是由以下部分构成的。一个有限图Y，其顶点集v[Y]={1,2,...,n}。,n}.根据上下文，图可以是有向的，也可以是无向的。系统状态是n个元组x=(x1,x2,...,xn)，x[v]是由与Y中v的1-邻居中的顶点相关的状态组成的元组（按某种固定顺序）。每个顶点v有一个顶点函数fv。顶点函数根据与v在Y中的1-邻域相关的状态，将顶点v在时间t的状态映射到时间t+1的顶点状态。一个更新方案，指定了各个顶点状态的映射机制，以便诱导一个具有映射F:Kn→Kn的离散动态系统。相空间的结构受图Y的属性、顶点函数(fi)i和更新方案的制约。该领域的研究试图根据系统组成的结构来推断相空间的属性。该分析具有从局部到整体的特点。广义蜂窝自动机（GCA）例如，如果更新方案包括同步应用顶点函数，就可以得到广义蜂窝自动机（CA）类。在这种情况下，全局映射F：Kn→Kn是由以下公式给出的{displaystyleF(x)_{v}=f_{v}(x[v]);.}这一类被称为广义的细胞自动机，因为经典的或标准的细胞自动机通常是在规则的图形或网格上定义和研究的，顶点函数通常被假定为是相同的。例子。让Y是顶点{1,2,3,4}上的圆图，边为{1,2},{2,3},{3,4}和{1,4}，表示Circ4。让K={0,1}为每个顶点的状态空间，并使用函数nor3:K3→K，定义为nor3(x,y,z)=(1+x)(1+y)(1+z)，对所有顶点函数进行算术模数2。然后，例如系统状态（0,1,0,0）通过同步更新被映射到（0,0,0,1）。

所有的转换都显示在下面的相空间中。顺序动态系统（SDS）如果顶点函数按字w=（w1，w2，...，wm）或permutation指定的顺序异步应用更新序列是一个置换，我们经常说置换SDS来强调这一点。使用更新序列（1,2,3,4），那么系统状态（0，1，0，0）被映射到（0，0，1，0）。这个序列动态系统的所有系统状态转换都显示在下面的相空间中。

从应用的角度来看，考虑GDS的一个或多个组成部分包含随机的情况是很有趣的。