Menu
In one of the projects I've worked on, the subject of isomorphism versus monomorphism came up.
A little background: I'm no expert on graph theory and have no formal training in it. But this topic is very important in chemistry, where chemists expect a particular kind of subgraph matching to take place in the structure search systems they use.
If a target graph A has n nodes and m edges, then a chemist would accept subgraph matches in which a query graph B had n nodes and m-1 edges. The only requirement would be that every edge in B should be present in A. For example, a linear chain of 6 nodes should match a cycle of 6 nodes.
Is this kind of matching isomorphism or monomorphism? Maybe something else altogether?
597
A homomorphism is an isomorphism if it is a bijective mapping. Homomorphism always preserves edges and connectedness of a graph. The compositions of homomorphisms are also homomorphisms. To find out if there exists any homomorphic graph of another graph is a NPcomplete problem.
Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a permutation of such that is in the set of graph edges iff is in the set of graph edges .
1. First, observe that subgroup isomorphism is in NP, because if we are given a specification of the subgraph of G and the mapping between its vertices and the vertices of H, we can verify in polynomial time that H is indeed isomorphic to the specified subgraph of G.
Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time.
Let G1, G2 be graphs composed of sets of vertices and edges V1, V2 and E1, E2 respectively.
G2 is isomorphic to a subgraph of G1 iff there exists a one-one mapping between each vertex of V2 and a vertex in V1, and between each edge in E2 and some edge in E1. So to be isomorphic, you need to have an exact match, including if the graph includes more than one edge between nodes.
G2 is monomorphic iff there's such a mapping between vertices, and there exists an edge between all vertices in V2 for which there is a corresponding edge in V1. But so long as at least one edge exists, that's sufficient.
Here's a nice package description from comp.lang.python.
147
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
