Dos grafos son isomorfos cuando tienen la misma estructura, aunque sus vértices posean nombres diferentes y el dibujo cambie por completo. El desafío consiste en encontrar una correspondencia que preserve todas las adyacencias.
Un grafo no depende de la posición visual de sus nodos ni de las etiquetas elegidas. Dos diagramas aparentemente distintos pueden describir exactamente las mismas conexiones.
El isomorfismo permite reconocer cuándo dos representaciones son estructuralmente equivalentes.
Los grafos G = (V,E) y H = (W,F) son isomorfos si existe una función biyectiva f : V → W que conserva la adyacencia.
Se escribe G ≅ H. La doble implicación exige preservar tanto aristas como no aristas.
Cada vértice de G debe corresponder a exactamente uno de H y todos los vértices de H deben utilizarse.
Por ello, dos grafos con distinta cantidad de vértices nunca son isomorfos.
Mover vértices, rotar el dibujo o cruzar aristas no cambia el grafo. Tampoco importan nombres como A, B, C o 1, 2, 3.
Sí importan las conexiones, la dirección de las aristas, los pesos y otras propiedades si forman parte del tipo de grafo estudiado.
Un invariante es una propiedad que todo isomorfismo preserva. Algunos ejemplos son:
Los dos dibujos representan el mismo grafo. Revela la biyección paso a paso y observa cómo cada nueva correspondencia preserva grados y aristas entre vértices ya asociados.
Biyeción candidata
Aristas comprobadas
Acción actual
Si un invariante difiere, los grafos no son isomorfos. Comparar cantidades y grados es una primera prueba muy barata.
Dos grafos pueden compartir muchos invariantes y aun así poseer estructuras diferentes.
Ordenar los grados permite comparar rápidamente ambos grafos. Además, un vértice solo puede corresponder a otro del mismo grado.
Cuando un grado aparece una sola vez, esa pareja queda forzada. Cuando se repite, se necesitan propiedades más finas para distinguir candidatos.
Puede clasificarse cada vértice no solo por su grado, sino por los grados o clases de sus vecinos. Luego se repite el proceso hasta que las clases se estabilizan.
Este refinamiento reduce mucho las correspondencias posibles, aunque algunos grafos simétricos permanecen indistinguibles.
Dos grafos son isomorfos si es posible reordenar simultáneamente filas y columnas de una matriz de adyacencia para obtener la otra.
Permutar solo filas o solo columnas no representa un renombrado coherente de los vértices.
El método directo prueba todas las biyecciones posibles y comprueba si preservan adyacencias.
function preservaAristas(grafoA, grafoB, permutacion) {
const n = grafoA.length;
for (let u = 0; u < n; u++) {
for (let v = 0; v < n; v++) {
if (grafoA[u][v] !==
grafoB[permutacion[u]][permutacion[v]]) return false;
}
}
return true;
}Probar n! permutaciones resulta viable únicamente para grafos muy pequeños.
En lugar de construir una permutación completa, se asignan parejas progresivamente. Una rama se abandona en cuanto contradice grados o alguna adyacencia ya decidida.
function compatible(u, x, mapeo, A, B) {
if (grado(A, u) !== grado(B, x)) return false;
for (const [v, y] of mapeo) {
if (A[u][v] !== B[x][y]) return false;
}
return true;
}Conviene asignar primero el vértice con menos imágenes compatibles. Esta estrategia de variable más restringida detecta contradicciones antes.
También pueden priorizarse vértices de grado raro, pertenecientes a triángulos particulares o cercanos a vértices ya mapeados.
Un etiquetado canónico transforma cada grafo en una representación independiente de sus nombres originales.
Es útil para eliminar duplicados y usar grafos como claves, aunque calcular una forma canónica eficiente requiere técnicas especializadas.
Un automorfismo es un isomorfismo de un grafo consigo mismo. Representa una simetría estructural.
Un ciclo puede rotarse o reflejarse sin cambiar sus adyacencias. Estas simetrías explican por qué varias correspondencias distintas pueden ser igualmente válidas.
En un grafo dirigido deben conservarse origen y destino. En uno ponderado, además de la adyacencia deben coincidir los pesos correspondientes.
Si los vértices poseen tipos o etiquetas semánticas, una correspondencia válida normalmente debe preservarlos también.
La fuerza bruta cuesta O(n! · n²). Las podas por grados, vecindarios y componentes suelen reducir drásticamente el espacio de búsqueda.
Árboles y otras familias especiales admiten métodos eficientes. Los grafos muy simétricos suelen ser los más difíciles para una búsqueda elemental.
El isomorfismo separa la estructura de su representación. Los invariantes filtran candidatos y la búsqueda con poda intenta construir una biyección que preserve cada relación.
En el próximo tema estudiaremos grafos aleatorios, modelos donde las aristas aparecen según reglas probabilísticas.