Why we do isomorphism, automorphism and homomorphism?

Problem Detail: 

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 ?

Asked By : Xara

Answered By : Jernej

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

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

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7690