What's the difference between the automorphism and isomorphism of graph?
What's the difference between the automorphism and isomorphism of graph?
In graph theory, an isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$, $ f \colon V(G) \to V(H) \,\!$ such that any two vertices $u$ and $v$ of $G$ are adjacent in $G$ if and only if $ƒ(u)$ and $ƒ(v)$ are adjacent in $H$.
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.
Could you give a example to explain the difference of the automorphism and isomorphism from the graph $G$ to $G$ itself? Since not all the isomorphism from the graph $G$ to $G$ itself is automorphism.
I have this question when I read this post, please find the key word An isomorphism is a bijective structure-preserving map...and there is a paragraph says that
The graph representation also bring convenience to counting the number of isomorphisms (the pre-factor). For example, for a graph $g$ with $V$ vertices, $E$ edges from some scalar theory, permutation of vertices is equivalent to relabeling of vertices, hence does not change the graph structure. The same goes to permutation of edges. Therefore, the number of graphs isomorphic to $g$ is $V!⋅E!$.
Maybe the isomorphism here does not demand to preserve the vertex-edge realtion, only demand to preserve the structure.
Solution 1:
By definition, an automorphism is an isomorphism from $G$ to $G$, while an isomorphism can have different target and domain.
In general (in any category), an automorphism is defined as an isomorphism $f:G \to G$.
Solution 2:
As an example, consider the graphs $G$ and $G'$ on 4 vertices, labelled 1, 2, 3 and 4, where $G$ has edge set $\{\{1,2\},\{1,3\},\{2,3\},\{3,4\}\}$ and $G'$ has edge set $\{\{1,4\},\{2,3\},\{2,4\},\{3,4\}\}$. Sketch both of these graphs !
Then the permutation $\alpha = (1, 2, 3, 4)$ (in disjoint cycle notation) is an isomorphism from $G$ to $G'$. Why ? Because, applying $\alpha$ to the vertex labels in the edge set of $G$ we obtain the edge set of $G'$. Check this ! Since an isomorphism from $G$ to $G'$ exists, $G$ and $G'$ are isomorphic. However, since their edge sets are different, $G$ and $G'$ are not equal.
The permutation $\beta = (1, 2)$ is an isomorphism from $G$ to $G$ itself, that is, an automorphism of $G$, also known as a symmetry of $G$. Check this, as above !
Solution 3:
An automorphism of a graph $\Gamma$ is an isomorphism from $\Gamma$ to itself.