Grafos isomorfos

Dados dos grafos $G = (V, X)$ y $G^{'} = (V^{'}, X^{'})$ se dicen isomorfos si existe una función biyectiva $f : V \to V^{'}$ tal que para todo $v$ y $w$ en $V$ :

(v, w) \in X si y solo si (f (v), f (w)) \in X^{'}

A la función $f$ se la llama función de isomorfismo. Cuando $G$ y $G^{'}$ son isomorfos lo notaremos como $G ≃ G^{'}$ o, simplemente (por abuso de notación) $G = G^{'}$ .

Por ejemplo, para los grafos $G = (V, X)$ y $H = (V^{'}, X^{'})$ :

flowchart LR

name(Grafo G)

id1((1))
id2((2))
id3((3))
id4((4))

id1 --- id2
id2 --- id3
id3 --- id4
id4 --- id1

flowchart LR

name(Grafo H)

id1((5))
id2((6))
id3((7))
id4((8))

id3 --- id4
id4 --- id1
id2 --- id3
id1 --- id2

Si definimos $f : V \to V^{'}$ como $f (x^{'}) = x + 4$ , podemos ver que $f$ respeta las adyacencias y, por lo tanto, $G$ y $H$ son isomorfos.

Decidir si dos grafos son isomorfos en tiempo polinomial continua siendo un problema sin resolver en Ciencias de la Computación, conocido como el problema del isomorfismo de grafos.

Propiedades

Si dos grafos $G = (V, X)$ y $G^{'} = (V^{'}, X^{'})$ son isomorfos entonces:

Tienen el mismo número de vértices
Tienen el mismo número de aristas
Para todo $k$ , con $0 \leq k \leq n - 1$ , tienen el mismo número de vértices de grado $k$
Tienen el mismo número de componentes conexas
Para todo $k$ , con $0 \leq k \leq n - 1$ , tienen el mismo número de caminos simples de longitud $k$