本论文的主要研究对象是几类无向图上或有向图上的离散动力系统。首先我们介绍无向图上的贯序动力系统(SDS)的概念，它由以下几个要素构成：(1)一个有限的，用1,2,……,n顶点标号的无向图G，每个顶点都有一个状态，设这些状态属于某个数域D；(2)对应图中的每一个顶点i,1≤i≤n,都有一个函数E,G：Dn→Dn；(3)n阶置换群Sn中的一个排列π。函数Fi,G根据第i个顶点自身的状态和它邻点的状态来决定i点被更新后的状态，而并不改变其它顶点的状态。排列π表示图中各点被更新的前后顺序。把函数Fi,G按照π的顺序复合起来，就得到了一个图G上的贯序动力系统(SDS)： [F,G,π]=Fπ1,GFπ2,G…Fπn,G：Dn→Dn。 对于其它几类离散动力系统：无向图上的并序动力系统(PDS)，有向图上的贯序动力系统(SDS)，有向图上的线性贯序动力系统(LSDS)，无向图上的随机并序动力系统(RPDS)和无向图上的字贯序动力系统(SDSW)，其定义可以类似地给出。 论文总共由五章构成。 第一章为介绍部分，陈述了课题的背景并给出了一些定义、符号及已知的结果。 第二章研究了四种无向图上的离散动力系统：OR-PDS[OR,G]，OR-SDS[OR,G,π]，NOR-PDS[NOR,G]和NOR-SDS[NOR,G,π]。对每一个研究对象，都用一个等价的引理去表示它在状态向量上的作用。这种等价性在于每个状态向量都和一个图的顶点子集一一对应。事实表明，这种方法在研究动力系统的性质方面是实用的和有效的。这章的主要目的是用图的结构性质来刻画动力系统本身所具有的属性。这章的主要结果有： 1.动力系统PDS[OR,G]的宽度等于图G的直径。 2.动力系统PDS[NOR,G]的宽度等于1。 3.动力系统PDS[NOR,G]的每一个轨道(即有限圈)都是2长的。 4.在动力系统PDS[NOR,G]的像图中，状态(0,0,…,0)具有极大的入度，且此入度值等于图G的控制集个数。 5.对于任意的排列π∈Sn，动力系统SDS[OR,G,π]的宽度不超过图G的直径；而且，存在一个排列σ∈Sn使得SDS[OR,G,σ]的宽度等于图G的直径。 6.动力系统SDS[NOR,G,π]的宽度等于1。 7.动力系统SDS[NOR,G,π]的周期点和图G的独立集之间是一一对应的。第三章主要研究有向图上的线性贯序动力系统(LSDS)。我们首先介绍了一种矩阵方法，它可以处理一般的线性贯序动力系统，这里的“一般”是指顶点状态属于一般的代数，局部函数是任意的线性函数。接着，我们研究布尔代数上的、以OR为局部函数的线性贯序动力系统的性质。这类动力系统被称为有向图D上的OR-SDS，记作[OR,D,π]。布尔矩阵理论在讨论中起到了非常关键的作用。最后对另一种有向图上的线性贯序动力系统，PAR-SDS，也做了一些讨论。这章的主要结果有： 8.下面四个结论互相等价：(a)D中不包含有向圈。(b)存在整数m≥1使得[OR,D,π]m(X)=(0,0,…,0)对任意X∈Fn2都成立。(c)像图Γ[OR,D,π]是连通的。(d)FIX[OR,D,π]=FIX[OR,D,π]∪PER[OR,D,π]={(0,0,…,0))。 9.下面五个结论互相等价：(a)动力系统[OR,D,π]是可逆的。(b)动力系统[OR,D,π]是恒等映射。(c)像图Γ[OR,D,π]是顶点不交的有向圈的并。(d)像图Γ[OR,D,π]是2n个环的并。(e)图D是n个环的并。 10.对任意的X≠(0,0,…,0)，存在整数m≥1使得[OR,D,π]m(X)=(1,1,…,1)当且仅当图D是强连通的并且满足条件(◇)。 11.动力系统[PAR,D,π]是可逆的当且仅当图D的每个顶点都有自环。在论文的第四章中，我们构造了一种无向图上的随机并序动力系统(RPDS)[Ran,G]。证明了由RPDS[Ran,G]诱导出的状态序列是一个齐次的马尔可夫链。同时还得到了两个状态向量在RPDS的作用下互达的充分必要条件。这章的主要结果有： 12.随机向量序列X,[Ran,G](X),[Ran,G]2(X),[Ran,G]3(X),…构成一个齐次的马尔可夫链。 13.两个状态向量I=(i1,i2,…,in)∈Fn2和J=(j1,j2,…,jn)∈Fn2在由RPDS[Ran,G]诱导出的马尔可夫链中互达当且仅当存在整数k使得(I,J)和(J,I)在图Gk中都是适应的。 论文的最后一章讨论了SDS的另一种推广形式。把SDS[F.G,π]中的排列π用一个[n]上的字ξ来代替，就得到了SDSW[FG,ξ]。我们研究了NOR-SDSW的性质并得到了一些结果。这章的主要结果有： 14.动力系统[NOR,G,ξ]的宽度等于1。 15.集合PER[NOR,G,ξ]∪FIX[NOR,G,ξ]和G的([n]Elem[ξ])-伪独立集之间存在——对应关系。