Tuesday, 1 January 2013

Homomorphism Vs. Isomorphism

  Homomorphism and Isomorphism are two confusing topics in Graph Theory. I have learned many definitions for both of them. But frankly none of them were very helpful. So I thought it might be a good idea to differentiate between Graph Homomorphism and Isomorphism.

I just want to mention a few points regarding Isomorphisms and Homomorphisms.
  • If a Graph M is Isomorphic to N then they are equivalent. They have equal number of edges and vertices with same structure. The two graphs given below are Isomorphic to each other.
  • The two graphs given above are also Homomorphic to each other. So we can conclude that all Isomorphisms are also Homomorphisms. But the converse is not true. All Homomorphisms are not Isomorphisms.
  • If M is Homomorphic to N and N is Homomorphic to M, Then they are also Isomorphic to each other. Thus they are equivalent.
  • Homomorphism is a structure preserving transformation. A Homomorphism simply maps adjacent vertices of the first graph to adjacent vertices of the second graph. The figure given below shows a graph G which is Homomorphic to a graph H.
  • In Graph H the vertex X represents the two vertices 1 and 2 of Graph G. The two vertices has combined but the edge relationship is preserved. But the two graphs are not Isomorphic since Graph H is not Homomorphic to Graph G.