Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

What are the key differences between these three terms isomorphism, automorphism and homomorphism in simple layman language and why we do isomorphism, automorphism and homomorphism ?

share|improve this question
add comment

2 Answers

up vote 16 down vote accepted

Isomorphism formalizes the notion of equal graphs. For example on this figure you see three isomorphic graphs enter image description here

More formally, an isomorphism of graphs $G_1$ and $G_2$ is a bijection $f:V(G_1) \mapsto V(G_2)$ that preserves adjacency. That is to say:

$$u \sim_{G_1} v \iff f(u) \sim_{G_2} f(v)$$

It is not hard to find such a bijection for every pair of graphs on the picture.

Now if $G_1 = G_2$ then the obtained mapping becomes an automorphism - a isomorphism from the graph to itself.

You might ask what is the intuitive notion of graph automorphism and the answer is that it gives you some kind of information of which vertices are "equivalent" in a graph. In other words if there is an automorphism of $f$ of graph $G$ such that the vertex $v$ is mapped to vertex $u$ then in a way the neighbourhood of $u$ and $v$ "looks" the same.

This in turn leads to the notion of graph symmetries. A graph $G$ is said to be vertex-transitive if for every pair of vertices $u,v \in V(G)$ there is an automorphism $f:V(G) \mapsto V(G)$ such that $f(u) = v.$ An example of a vertex-transitive graph is the Petersen graph enter image description here

and as you can see the graphs "looks" pretty symmetric. That is precisely because it has "many" automorphisms of the described type.

Graph homomorphisms are usually not studied by layman and are more or less of theoretical purposes. For example they are closely related to the notion of vertex-colourings. See also Hadwiger Conjecture

share|improve this answer
    
...homomorphisms are usually not studied by layman... hilarious!+1 –  Pratik Deoghare Jan 2 '13 at 11:14
add comment

In the context of graph theory, a homomorphism $h:G\rightarrow G'$ is a mapping between two graphs that maps adjacent vertices in $G=(V,E)$ to adjacent vertices in $G'=(V',E')$. In other words, for every edge $e=(u,v) \in E$, the edge $(h(u),h(v))\in E'$. Graph homomorphism imply many properties, including results in graph colouring.

Now a graph isomorphism is a bijective homomorphism, meaning it's inverse is also a homomorphism. If two graphs are isomorphic, then they're essentially the same graph, just with a relabelling of the vertices. The problem of determining if two graphs are isomorphic to one-another is an important problem in complexity theory.

Finally an automorphism is isomorphism from a graph to itself.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.