计算机模拟与图上的离散动力系统

论文摘要

离散动力系统是一种以离散时间为度量的动态系统。一般而言，控制整个系统行为的是一个微分方程，或者是一个确定型的带返回值的函数。确切地说，在第n+1个时刻，系统中某个变量的取值依赖于某个函数，这个函数根据第n个时刻系统中各个变量的取值来决定它在第n+1个时刻的取值。概而言之，一个离散动力系统完全可以用一个迭代函数来刻画和描述。 在这篇论文中，我们的主要研究对象是一类特殊的离散动力系统，它的最初模型由以下几个方面构成：（1）一个有限的，用1，2，…，n来进行顶点标号的无向图G，并且每个顶点都有一个状态，设这些状态属于某个数域D。（2）一组可重的函数，Fi，G：Dn（?）Dn，1≤i≤n，其中下标i表示它是对应于顶点i的函数。（3）n阶置换群Sn中的一个排列π。函数Fi，G根据第i个顶点现有的状态和它邻点的状态来决定i点被更新后的状态，它并不改变其它顶点的状态。排列π表示图G中各点被更新的前后顺序，依据π，Fi，G依次作用于某状态向量。我们把函数Fi，G按照π的顺序复合起来，就得到了一个图G上的贯序动力系统（SDS）： 在本文中，约定上面的复合形式是从左向右依次作用。 本论文总共由五章构成。第一章为介绍部分，我们介绍了论文的背景及一些相关的定义和符号。除此之外，其他人在这个课题上得到的一些重要结果和这篇论文的主要内容也被陈列出来。第二章到第五章为论文的主体部分，在这部分中，我们详尽地阐述了本篇论文的主要结果，包括证明过程及相关的分析。第二章和第三章的主要研究对象分别是无向图上的几种特殊的离散动力系统和有向图上的线性贯序动力系统。第三章是第二章的推广和延伸。在第四章中，我们首次介绍随机的并序动力系统。由它诱导而成的状态序列具有马尔科夫性这一结论被严格证明。本文的最后讨论了SDS的另一种演变形式。也就是说，把一般的SDS中的排列丌用一个字ξ来代替，这就得到了一个字上的贯序动力系统（SDSW）。事实表明，研究SDSW远比研究SDS要困难得多。 下面进行深层次的说明。在第二章中，我们聚焦四种图上的离散动力系统：OR-PDS，OR-SDS，NOR-PDS和NOR-SDS。对每一种系统，都用一个

论文目录

• Abstract （in Chinese）
• Abstract （in English）
• 1 Introduction
• 1.1 Background
• 1.2 Definitions and notations
• 1.3 Overview of results
• 2 Parallel Dynamical Systems （PDS） and Sequential Dynamical Systems （SDS） with Boolean Local Functions on Graphs
• 2.1 Introduction
• 2.2 OR-PDS and OR-SDS
• 2.3 NOR-PDS
• 2.4 NOR-SDS
• 3 Linear Sequential Dynamical Systems （LSDS） on Digraphs
• 3.1 Introduction
• 3.2 Matrix method
• 3.3 OR-SDS on digraphs
• 3.4 PAR-SDS on digraphs
• 4 Random Parallel Dynamical Systems （RPDS） on Graphs
• 4.1 A new model of random parallel dynamical systems
• 4.2 Markov property
• 4.3 A necessary and sufficient condition for "communicate"
• 5 Sequential Dynamical Systems in Words （SDSW） on Graphs
• 5.1 Introduction
• 5.2 Counting different SDSW
• 5.3 NOR-SDSW
• 5.4 SDSW on random graphs
• Acknowledge
• Biblography
• Resume