G is the maximum common subgraph (MCS) of two graph G? and G?, whenever G is the subgraph of G? and G? and there is no common subgraph in G? and G? that the number of its vertices is more than G. According to this definition, MCS is not necessary to compare the objects and determine the degree and composition of the similarity between them. ]f the objects and their relations are represented by graphs, one of the best method to determine the similarity between them is finding the maximum common subgraph of their corresponding graphs. For example, in studying the chemical structure, the maximum common subgraph problem in the graphs that model the chemical molecules is used for finding the maximum common structure in the molecules. ]t is noteworthy that MCS problem is a generalization of the induced subgraph isomorphism problem.
