膜计算(也被称为膜系统或P系统)是罗马尼亚Gheorghe.P?un教授于1998年从细胞中抽象出的新的计算模型,自被提出后,发展迅速,并成为自然计算中的一个分支。由于细胞内的化学反应可以并行执行,且反应所消耗的能量非常小,所以,P系统拥有极大并行性,用来解决一些复杂问题得心应手,从而获得远远超过传统电子计算机的计算能力,也为很多难点问题带来新的求解思路。已有研究证明,膜计算可以在多项式时间内解决很多NP-完全问题。顶点覆盖问题和度约束生成树问题是图论中两类经典的NP难问题,在电子计算机计算模型下,对于这两类问题的求解要么只能求出其个别值,要么对于大规模的问题求解根本束手无策。膜计算作为一个新兴的研究领域,虽然其对于求解NP难问题拥有很大的优势,但是仍然鲜有对这两类问题的研究成果发表。不论从扩展膜计算的应用领域上,还是从实际应用中,研究这两类NP难问题都有着一定的理论意义和应用价值。因此,本文通过对顶点覆盖问题和度约束生成树问题的分析,设计出求解这两类问题全部解的P系统,扩展P系统在图论领域的研究,也为P系统计算机的物理实现提供一定的理论基础。本文所完成的研究工作简述如下:(1)根据图论中顶点覆盖问题基础知识及其特点,设计出判定顶点覆盖的具体流程,为求解该问题的具体实现奠定基础。(2)根据图论中度约束生成树问题基础知识及其特点,设计出判定生成树的具体流程,为求解该问题的具体实现奠定基础。(3)通过膜计算模型的研究,设计了一个求解顶点覆盖问题全部解的P系统,并用实例及计算机仿真程序来验证该P系统的可行性。(4)通过膜计算模型的研究,设计了一个求解度约束生成树问题全部解的P系统,并用实例及计算机仿真程序来验证该P系统的可行性。综上所述,本文通过选择顶点覆盖问题和度约束生成树问题进行P系统研究,完善了P系统中对于NP难问题的研究,为其他NP难问题的求解提供参考,也为今后解决其他领域问题的提供解决思路。