DNA Computing of Bipartite Graphs for Maximum Matching

Let M be a matching in a graph G. It is defined that an M-augmenting path must obtain one element of M. In this paper, it is obtained that a matching M in a graph G is a maximum matching if and only if G contains no M-augmenting path and M is a maximal matching in G. It supplies a theoretical basis to DNA computing. A detailed discussion is given of DNA algorithms for the solutions of the maximal matching problem and maximum matching one in a bipartite graph.