Why we do isomorphism, automorphism and homomorphism?

Question

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 ?

Answer 1

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

Answer 2

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.