Isomorphism of graph.
Definition : Two graphs G and H are isomorphic, denoted by G ≅ H, if there exists a bijection α:Vg➝Vh such that : uv ∈ Eg ⇔ α(u)α(v) ∈ Eh ; for all u,v ∈ G Hence G and H are isomorphic if the vertices of H are remaining of those of G.Two isomorphic graphs enjoy the same graph-theoretical properties and they are often identified.In particular,all isomorphic graphs have the same plane figures (excepting the identities of the vertices). This shows in the figures, where we tend to replace the vertices by small circles and talk of 'the graph' although there are, in fact, infinitely many such graphs. Example 1 : The following graphs are isomorphic . Indeed, the required isomorphism is given by v1 ↦1, v2 ↦ 3,v3 ↦ 4,v4 ↦2, v5 ↦5. Isomorphism Problem : Does there exist an efficient algorithm to check whether any two given graphs are isomorphic or not? The following table lis