maximum common graph

Maximal common subgraph (MCS) and simply connected common subgraph (SCCS): A subgraph of graph G is a new graph obtained from G by deleting some edges and vertices. A common subgraph of G₁ and G₂, CS(G₁, G₂), is a graph which is isomorphic to a subgraph of both G₁ and G₂. The maximal common subgraph of G₁ and G₂, MCS(G₁, G₂), is the CS(G₁, G₂) whose cardinality is not smaller than that of any other CS(G₁, G₂). A simply connected common subgraph, SCCS(G₁, G₂), is a CS(G₁, G₂) within which each vertex is connected to at least one other vertex. The MCS(G₁, G₂) must be a set of SCCS(G₁, G₂)'s.