Research On P System For Solving Two Kinds Of Graph Theory Problems

Membrane Computing(also called Membrane Systems or P Systems) was proposed in 1998 by Romanian professor Gheorghe P?un, after that, P systems developed rapidly, and it has been one of the fields of natural Computations. Due to the cell membrane is small volume but the large amount, and its biochemical reactions need very low energy consumption. So that, Mambrane Computing has a great degree of parallelism in implement calculations, it solve the complex problems landscapes with great facility based on it, and its computing power is more than the traditional electronic computers. Meanwhile, it brings a newly solving idea for other problems. And some researches show that, P sytems can solve many NP-complete problems in a polynomial time.The vertex cover problem and the degree-constrained spanning tree problem are the two of the classical NP-hard problems in graph theory. In the computational model of electronic computers, for solving these two kinds of problems, it either only obtain the partial value, or it will do nothing to solve the problems of large scale. Membrane computing as an emerging field of research, although it has a lot of advantages for solving those NP-hard problems, there is still little research on these two kinds of problems. No matter from the application field of the extended membrane computing, or from the practical application, the study of the NP-hard problems above has a certain theoretical research and practical applications. Thus, it designs two kinds of P systems to solve the vertex cover problem and the degree-constrained spanning tree problem through the research and analysis of these two kinds of problems in this paper. It expands the application range of P system in the field of graph theory, and it also provides a theoretical basis for the physical realization of the P systems.The research work done in this paper is summarized as follows:(1) According to the basic theories and features of the vertex cover problem, it designed a method for determining a vertex cover, and lays the foundation for the concrete realization of the problem.(2) According to the basic ideas and features of the degree-constrained spanning tree problem, it designed a method for determining a spanning tree, and lays the foundation for the concrete realization of the problem.(3) According to the research of the Membrane Computing Model, it designed a P system for fiding the all solutions of the vertex cover problem, and an instance is given to illustrate how it works, and designed a program of computer simulation to validate its feasibility.(4) According to the research of the Membrane Computing Model, it designed a P system for fiding the all solutions of the degree-constrained spanning tree problem, and an instance is given to illustrate how it works, and designed a program of computer simulation to validate its feasibility.Stated thus, it chooses the vertex cover problem and the degree-constrained spanning tree problem for the research on P systems. It improves the P system for the fields of NP difficult problem, provides reference for solving other NP hard problems, and provides solutions for future solutions to other research fields as well.