Definition:Isomorphism (Graph Theory)
Jump to navigation
Jump to search
This page is about Isomorphism in the context of Graph Theory. For other uses, see Isomorphism.
Definition
Let $G = \struct {\map V G, \map E G}$ and $H = \struct {\map V H, \map E H}$ be graphs.
Let there exist a bijection $F: \map V G \to \map V H$ such that:
- for each edge $\set {u, v} \in \map E G$, there exists an edge $\set {\map F u, \map F v} \in \map E H$.
That is, that:
- $F: \map V G \to \map V H$ is a homomorphism, and
- $F^{-1}: \map V H \to \map V G$ is a homomorphism.
Then $G$ and $H$ are isomorphic, and this is denoted $G \cong H$.
The function $F$ is called an isomorphism from $G$ to $H$.
Also see
Linguistic Note
The word isomorphism derives from the Greek morphe (μορφή) meaning form or structure, with the prefix iso- meaning equal.
Thus isomorphism means equal structure.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.2$: Isomorphic Graphs
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): isomorphic graphs