Isomorphism

Understanding Isomorphisms

  • Isomorphism in graphs refers to a one-to-one correspondence (bijective function) between the vertices of two or more graphs, such that the structure of the graphs is preserved.
  • The term comes from the Greek words ‘iso’, which means ‘equal’ or ‘identical’, and ‘morphism’, which denotes ‘form’ or ‘shape’. Thus, an isomorphism demonstrates that two graphs are ‘identical in form’.
  • Two graphs that are isomorphic are often called ‘isomorphic graphs’.
  • A graph is said to be self-isomorphic if it is isomorphic to a transformation of itself.

Identifying Isomorphisms

  • To recognise if two graphs are isomorphic, we look to see if there is a bijective function between their vertex sets, such that the adjacency relation is preserved.
  • A bijection is a function that is both injective (one-to-one) and surjective (onto). This means that every vertex in the first graph is paired with exactly one vertex in the second, and vice versa.
  • An isomorphism between two graphs must preserve edges (if two vertices are connected by an edge in one graph, their images under the isomorphism must be connected by an edge in the other graph), non-edges (if two vertices are unconnected in one graph, their images under the isomorphism must be unconnected in the other graph), and degrees (the degree of a vertex must be the same as the degree of its image under the isomorphism).
  • Two graphs that are isomorphic necessarily share the same graph properties, such as being cyclic, connected, eulerian, or hamiltonian.

Isomorphism in Graph Theory Applications

  • Applying the concept of isomorphism allows us to classify graphs and study their properties.
  • Also, understanding the principles of isomorphism can aid in solving various graph theory problems.
  • The problem of determining whether two general graphs are isomorphic is computationally difficult and is classified as an NP-complete problem.
  • Despite this complexity, the question of isomorphism turns out to be easier to answer for specific types of graphs. For instance, deciding whether two trees are isomorphic can be resolved in polynomial time.