细胞自动机是一种离散动力系统。它包含了由细胞单元的状态构成的配制以及作用在配制上的传递规则。下面我们总是假设G=(V,E)是一个有限无向的简单连通图。图上的每一个顶点可以看作细胞自动机上的一个细胞单元，细胞单元上状态的值或者是0或者是1。如果每一个细胞单元的状态都被赋予了一个值，则所有细胞单元状态值的集合被称为细胞自动机上的一个配制。自动机的演化由局部传递规则决定。如果X是时刻t的一个配制，Y是局部传递规则作用在X后于时刻t+1的配制，那么Y称为X的后继，X被称为Y的前驱。在配制进化领域里的一个基本问题就是研究对于一个给定的目标配制确定它的前驱是否存在的问题。这个问题被称作前驱存在问题。更进一步，如果给定一个界β，寻找基数最多为β的前驱配制问题被称为界定前驱存在问题。给定一个有趣的目标配制1，即目标配制是每一个细胞单元的状态值都为1，我们将以基于局部规则σ+及σ下的图上的细胞自动机作为对象展开研究。 对于σ+规则，当初始配制为0，目标配制为1时，相应的前驱存在问题也被称为σ+全一问题或者直接称为全一问题[27]。Peled提出了一个等价的问题被称为点灯问题[22]。类似的，对于σ规则，当初始配制为0，目标配制为1时，相应的前驱存在问题被称为σ全一问题。为方便起见，目标配置的前驱也被称为解。 近年来全一问题已经被广泛的研究，见Sutner[29，31]，Barua和Ramakishnan[2]以及Dodis和Winkler[11]。全一问题解的存在性问题已经被完全解决。用线形代数的方法，Sutner[28]证明了全一问题的解总是存在的，并给出了n×n的格子图上解的一些计数结果。Sutner曾提问是否可用图论的方法证明解的存在性问题[28]。Erikissonetal.[13]给出了解存在性的图论证明。进而，Chenetal.[6]给出了一个精巧的图论算法用来找到一般图上的解。如果我们也要求前驱配制中非零状态的细胞单元个数最少，相应的问题被简称为最小全一问题。这个问题已经被证明对于任意图是NP-完全问题[25]。最近，Broersma和Li又证明了对于二部图这个问题也是NP-完全的[3]。全一问题也可以被称为点点问题。由点点问题，我们很容易提出下面三个问题：点边问题，边点问题和边边问题。这些问题即使不与全一问题联系，从算法的角度都有其各自的研究意义。 与全一问题不同的是，σ全一问题对于一些图类可能并不存在解。并且最小σ全一问题对于二部图也已经被证明是NP-完全问题。所以对于任意给定的树图，特殊的二部图，确定其解存在问题及在解存在的条件下是否存在多项式时间算法寻找最小解的问题就成为了十分有趣的问题。进一步，如果我们要求从任意的配制开始在σ规则作用下到达全一的配制，相应的σ全一问题就被称为一般σ全一问题和一般最小σ全一问题。 本论文按照如下结构组织成文：第一章论述了σ+规则以及σ规则下的全一问题的历史背景以及为算法研究的方便，我们将以图论的语言对所研究的问题进行具体描绘。 第二章，我们研究树的最小全一问题。首先，对于树的任意一组解我们通过引进准全一问题的定义来给出解结构的解释。然后我们推导出解的计数公式。通过调用最小奇(偶)和问题的算法作为子过程，我们得到了最小全一问题的线性时间最优算法。由解的结构特性，我们还得到了线性时间算法用于求得单圈图的全一问题的解。 在第三章中，我们给出了线性时间算法求得单圈图以及双圈图上最小全一问题的解。这些算法都是以带有限制的树的最小全一问题算法为基础的。 在第四章中，我们研究新的全一问题及其相应的最小全一问题。对于点边问题，我们证明当且仅当二部图时解是存在的，并且只有可能存在两组解，因此存在线性时间算法确定最小解。对于边点问题，我们证明当且仅当图具有偶数个顶点时才存在解。我们通过多项式变换将最小边点问题转换成了最小完美匹配问题，从而得到了存在多项式时间算法解决最小边点问题的结论。对于边边问题的研究可以被转化成研究线图上的点点问题。 在第五章，我们得到了两个线性时间算法用于解决树上的一般σ全一问题。第一个算法用来解决在解存在的情况下解的计数问题。第二个算法用来解决最小σ全一问题。进而，我们稍加修改第二个算法就可推广成一般最小σ全一问题的最优算法。