Isomorfismo de grafos: cuándo dos grafos son el mismo

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Qué significa que dos grafos sean el mismo

Dos grafos son isomorfos cuando son el mismo grafo con nombres distintos en los vértices. Formalmente, G y H son isomorfos, lo que se escribe G ≅ H, si existe una biyección f de los vértices de G en los vértices de H tal que u y v son adyacentes en G exactamente cuando f(u) y f(v) son adyacentes en H. Una biyección f con esta propiedad es un isomorfismo. Las dos direcciones importan: las aristas deben ir a aristas, y las no aristas deben ir a no aristas.

El isomorfismo ignora todo lo que no es estructura. Los nombres de los vértices no cuentan, y el dibujo tampoco: dónde están los vértices en la página, cuánto miden las aristas, si se cruzan. Dos dibujos que no se parecen en nada pueden mostrar el mismo grafo, y eso es justo lo que hace interesante la pregunta. La guía de vértices y aristas presenta la idea en una frase; este artículo trata de cómo decidirla.

El ejemplo que seguiremos es el prisma triangular de la guía de grafos planos, al que llamamos G aquí, y un segundo grafo H dibujado como un hexágono con tres cuerdas:

G = {AB, BC, CA, DE, EF, FD, AD, BE, CF}          dos triángulos y tres travesaños
H = {12, 23, 34, 45, 56, 61, 13, 25, 46}          hexágono 1..6 más las cuerdas 13, 25, 46

f:  A→1   B→2   C→3   D→6   E→5   F→4

Comprueba cualquier arista de G y verás que su imagen es una arista de H: AD va a 16, DF va a 64, BE va a 25. Ambos grafos tienen nueve aristas y f lleva las nueve sobre las nueve, así que también envía no aristas a no aristas. G y H son el mismo grafo. Ser isomorfos es una relación de equivalencia, así que los grafos se reparten en clases de isomorfismo, que es lo que se suele entender por «las formas» de los grafos con un número dado de vértices.

2. Un grafo que parece el mismo y no lo es

Ahora toma un tercer grafo K: el mismo hexágono, pero con los tres diámetros largos 14, 25 y 36 como cuerdas. Tiene 6 vértices y 9 aristas, todos los vértices tienen grado 3 y está dibujado con el mismo estilo que H. No es isomorfo a G.

La prueba más rápida busca triángulos. G tiene dos, ABC y DEF, y un isomorfismo debe enviar triángulos a triángulos. K no tiene ninguno: sus vértices se dividen en impares y pares, y cada arista une un vértice impar con uno par, así que K es bipartito y no contiene ningún ciclo de longitud impar, como explica la guía de grafos bipartitos. De hecho, K es el grafo bipartito completo K3,3, el mismo grafo que hace imposible el acertijo de los tres servicios. Dos grafos que coinciden en todos los recuentos evidentes pueden ser distintos, y buena parte de la materia consiste en encontrar el recuento que los distingue.

3. Invariantes: demostrar que dos grafos son distintos

Un invariante de grafos es cualquier cantidad que los grafos isomorfos comparten siempre: el número de vértices y de aristas, la sucesión de grados, el número de triángulos, si el grafo es conexo o bipartito, su cintura, su número cromático, los valores propios de su matriz de adyacencia y muchas más. Los invariantes funcionan en una sola dirección.

Si dos grafos difieren en algún invariante, no son isomorfos. Si coinciden en todos los invariantes que has calculado, no has aprendido nada seguro.

Todo invariante sencillo tiene puntos ciegos. La sucesión de grados no ve la diferencia entre el prisma y K3,3. Ni siquiera la lista completa de valores propios, que parece una huella dactilar, lo es: la estrella K1,4 y el ciclo de 4 vértices más un vértice aislado tienen ambos los valores propios 2, 0, 0, 0, −2 y son claramente grafos distintos: forman el par coespectral más pequeño de este tipo, atribuido a Collatz y Sinogowitz en 1957. Un invariante que separara todo par de grafos no isomorfos y se pudiera calcular rápido resolvería todo el problema, y no se conoce ninguno.

4. ¿Cuántos grafos distintos hay?

Sobre n vértices etiquetados hay C(n, 2) aristas posibles, cada una presente o ausente, así que hay 2C(n, 2) grafos etiquetados. La mayoría se obtienen unos de otros reetiquetando los vértices. El número de formas realmente distintas, las clases de isomorfismo, crece mucho más despacio:

from itertools import combinations, permutations

def count_graphs(n):
    """Grafos etiquetados con n vértices, y en cuántas formas distintas se reparten."""
    pairs = list(combinations(range(n), 2))
    index = {p: i for i, p in enumerate(pairs)}
    seen, shapes = set(), 0
    for mask in range(1 << len(pairs)):
        if mask in seen:
            continue
        shapes += 1                           # una clase de isomorfismo nueva: marca todos sus reetiquetados
        edges = [p for i, p in enumerate(pairs) if mask >> i & 1]
        for perm in permutations(range(n)):
            m = 0
            for u, v in edges:
                a, b = sorted((perm[u], perm[v]))
                m |= 1 << index[(a, b)]
            seen.add(m)
    return 1 << len(pairs), shapes

for n in range(1, 6):
    print(n, count_graphs(n))
# 1 (1, 1)
# 2 (2, 2)
# 3 (8, 4)
# 4 (64, 11)
# 5 (1024, 34)

El recuento por fuerza bruta se detiene en cinco vértices porque prueba todos los reetiquetados de cada grafo. La sucesión continúa con 156 para seis vértices, 1044 para siete y 12.346 para ocho. No hay una fórmula cerrada sencilla; la herramienta estándar es la teoría de enumeración de Pólya, de 1937, que cuenta objetos salvo simetrías. La distancia entre las dos columnas es la razón misma de que el test de isomorfismo importe: un programa que enumera grafos, moléculas o circuitos tiene que reconocer cuándo dos de sus salidas son el mismo objeto disfrazado.

5. Comprobar mediante búsqueda

La definición sugiere un algoritmo: probar cada biyección y comprobarla. Con n vértices hay n! biyecciones, 720 para el ejemplo de seis vértices pero unas 2,4 × 1018 para veinte vértices, así que el método ingenuo no sirve más allá de tamaños de juguete. Dos ideas hacen que la búsqueda sea práctica en grafos pequeños y medianos. Primero, rechazar de inmediato cuando difiere un invariante barato como la sucesión de grados. Segundo, construir la correspondencia vértice a vértice, probar solo imágenes del mismo grado y retroceder en cuanto una arista o una no arista no coincida.

def graph(edges):
    adj = {}
    for e in edges:
        u, v = e.split('-')
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def isomorphisms(G, H):
    """Genera cada biyección f: V(G) -> V(H) tal que uv es arista exactamente cuando f(u)f(v) lo es."""
    if len(G) != len(H) or sorted(map(len, G.values())) != sorted(map(len, H.values())):
        return                                # un invariante barato ya dice que no
    order = sorted(G, key=lambda v: -len(G[v]))
    def extend(f, used):
        if len(f) == len(order):
            yield dict(f)
            return
        u = order[len(f)]
        for x in H:
            if x in used or len(H[x]) != len(G[u]):
                continue                      # los grados deben coincidir
            if all((w in G[u]) == (f[w] in H[x]) for w in f):
                f[u] = x                      # coherente con todos los vértices asignados hasta ahora
                yield from extend(f, used | {x})
                del f[u]
    yield from extend({}, set())

G = graph(['A-B', 'B-C', 'C-A', 'D-E', 'E-F', 'F-D', 'A-D', 'B-E', 'C-F'])   # el prisma
H = graph(['1-2', '2-3', '3-4', '4-5', '5-6', '6-1', '1-3', '2-5', '4-6'])   # hexágono + 3 cuerdas
K = graph(['1-2', '2-3', '3-4', '4-5', '5-6', '6-1', '1-4', '2-5', '3-6'])   # hexágono + 3 diámetros

print(next(isomorphisms(G, H)))
# {'A': '1', 'B': '2', 'C': '3', 'D': '6', 'E': '5', 'F': '4'}
print(sum(1 for _ in isomorphisms(G, H)))     # tantos como simetrías tiene G
# 12
print(next(isomorphisms(G, K), None))         # mismos grados, ningún isomorfismo
# None

La primera línea de la salida es la correspondencia de la sección 1. La segunda muestra que hay exactamente 12 isomorfismos distintos de G a H, y la sección 7 explica por qué ese número no es casualidad. La tercera confirma que no existe ninguna correspondencia del prisma a K3,3, aunque la comprobación de grados se superó. La función se comprobó frente a networkx con 3000 pares aleatorios de grafos, la mitad de ellos copias reetiquetadas unos de otros, verificando arista por arista cada correspondencia que devolvía. El retroceso sigue siendo exponencial en el peor caso: los grafos en los que todos los vértices parecen iguales anulan la poda por grados, y ahí entra la siguiente idea.

6. El refinamiento de colores y su punto ciego

El refinamiento de colores, también llamado algoritmo de Weisfeiler–Leman unidimensional por el artículo de Weisfeiler y Leman de 1968, asigna a cada vértice un color y va refinando los colores a partir de los vecindarios. Empieza con un mismo color para todos. En cada ronda, da a dos vértices el mismo color nuevo solo si tenían el mismo color anterior y sus vecinos llevan el mismo multiconjunto de colores anteriores. Para cuando ninguna clase de color se divide. Ejecútalo sobre los dos grafos a la vez: si los recuentos finales de colores difieren, los grafos no son isomorfos.

from collections import Counter

def colour_refinement(adj, rounds=None):
    """1-WL: recolorea repetidamente cada vértice según su color más el multiconjunto de colores de sus vecinos."""
    colour = {v: 0 for v in adj}
    for _ in range(rounds or len(adj)):
        signature = {v: (colour[v], tuple(sorted(colour[w] for w in adj[v]))) for v in adj}
        palette = {s: i for i, s in enumerate(sorted(set(signature.values())))}
        new = {v: palette[signature[v]] for v in adj}
        if len(set(new.values())) == len(set(colour.values())):
            break                             # estable: ninguna clase de color se dividió
        colour = new
    return colour

def joint(G, H):
    """True si el refinamiento no distingue G de H. Se refinan juntos para que los colores coincidan."""
    union = {('g', v): {('g', w) for w in G[v]} for v in G}
    union.update({('h', v): {('h', w) for w in H[v]} for v in H})
    c = colour_refinement(union)
    return (sorted(Counter(c[k] for k in union if k[0] == 'g').items()) ==
            sorted(Counter(c[k] for k in union if k[0] == 'h').items()))

def graph(edges):
    adj = {}
    for e in edges:
        u, v = e.split('-')
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

T1 = graph(['a-b', 'b-c', 'c-d', 'b-e', 'e-f'])       # centro b, ramas de longitud 2, 2 y 1
T2 = graph(['a-b', 'b-c', 'c-d', 'd-e', 'b-f'])       # centro b, ramas de longitud 3, 1 y 1
prism = graph(['A-B', 'B-C', 'C-A', 'D-E', 'E-F', 'F-D', 'A-D', 'B-E', 'C-F'])
k33 = graph(['1-2', '2-3', '3-4', '4-5', '5-6', '6-1', '1-4', '2-5', '3-6'])

print(joint(T1, T2))      # misma sucesión de grados, pero el refinamiento los distingue
# False
print(joint(prism, k33))  # ambos 3-regulares: el refinamiento no los distingue
# True

Los dos árboles del ejemplo tienen la misma sucesión de grados, (3, 2, 2, 1, 1, 1), así que la comprobación de grados no puede separarlos. El refinamiento sí: tras unas pocas rondas, una hoja junto al centro y una hoja al final de una rama larga reciben colores distintos, y los recuentos de colores de los dos árboles dejan de coincidir. En general, el refinamiento es potente. Babai, Erdős y Selkow demostraron en 1980 que un refinamiento sencillo basado en los grados identifica casi todos los grafos, así que en un grafo aleatorio el isomorfismo es fácil.

El punto ciego es la regularidad. En un grafo k-regular todos los vértices empiezan con el mismo color y tienen k vecinos de ese color, así que la primera ronda no cambia nada y el algoritmo se detiene enseguida. Dos grafos regulares cualesquiera con el mismo número de vértices y el mismo grado le parecen idénticos, y por eso el prisma y K3,3 superan juntos esta prueba. El mismo límite alcanza al aprendizaje automático: Xu y sus colegas demostraron en 2019 que las redes neuronales de grafos de paso de mensajes solo pueden distinguir dos grafos si el refinamiento de colores puede hacerlo, y por eso la guía de redes neuronales de grafos toma el test de Weisfeiler–Leman como vara de medir. Las versiones más fuertes refinan colores de pares o tríos de vértices en lugar de vértices sueltos; ven más, pero cuestan más.

7. Automorfismos: las simetrías propias de un grafo

Un isomorfismo de un grafo en sí mismo es un automorfismo, una simetría del grafo. Los automorfismos de un grafo forman un grupo, y su tamaño mide lo simétrico que es el grafo. El prisma tiene 12: girar o reflejar los dos triángulos a la vez, lo que da 6 simetrías, y opcionalmente intercambiar los dos triángulos. K3,3 tiene 72, ya que cada lado se puede permutar de 6 maneras y los dos lados se pueden intercambiar, y el grafo de Petersen tiene 120.

Esto explica el 12 de la sección 5. Si f es un isomorfismo de G a H, cualquier otro es f compuesto con un automorfismo de G, así que entre dos grafos isomorfos hay siempre exactamente tantos isomorfismos como automorfismos tiene cualquiera de los dos. Una búsqueda que solo quiere una respuesta pierde tiempo explorando copias simétricas de la misma correspondencia, y los mejores algoritmos prácticos usan los automorfismos que descubren para podar la búsqueda.

Dos resultados clásicos muestran hasta dónde puede llegar la simetría en cada dirección. Frucht demostró en 1939 que todo grupo finito es el grupo de automorfismos de algún grafo, así que la simetría puede adoptar cualquier forma. Y Erdős y Rényi demostraron en 1963 que casi todos los grafos son asimétricos, sin ningún automorfismo salvo la identidad. Aquí los grafos pequeños engañan: ningún grafo de entre dos y cinco vértices es asimétrico, los grafos asimétricos más pequeños tienen seis vértices y hay ocho, y entre los 1044 grafos de siete vértices solo 152 son asimétricos. El «casi todos» solo se impone a medida que n crece.

8. Formas canónicas: un nombre por forma

Comparar grafos por parejas no escala cuando una base de datos guarda millones. La alternativa es una forma canónica: una regla de reetiquetado que envía cada grafo a un representante fijo de su clase de isomorfismo, de modo que dos grafos son isomorfos exactamente cuando sus formas canónicas son idénticas. Una vez que cada grafo tiene su forma canónica, el isomorfismo se convierte en igualdad de cadenas, y una base de datos puede indexar grafos, calcular su hash y eliminar duplicados como con cualquier otra clave.

La forma canónica más sencilla toma, de entre todos los n! reetiquetados, aquel cuya matriz de adyacencia, leída como cadena de bits, es la menor. Es correcta y demasiado lenta. Las herramientas prácticas calculan formas canónicas con individualización y refinamiento: ejecutan el refinamiento de colores y, cuando se atasca en una clase de vértices indistinguibles, destacan uno de ellos con un color nuevo y vuelven a refinar, explorando un árbol de búsqueda de tales elecciones y podándolo con los automorfismos que encuentran por el camino. El programa nauty de McKay, descrito en 1981, y Traces, presentado junto con nauty por McKay y Piperno en 2014, funcionan así y manejan en la práctica grafos con muchos miles de vértices.

9. ¿Cuán difícil es el isomorfismo de grafos?

El isomorfismo de grafos ocupa un lugar inusual en la teoría de la complejidad. Está en NP, porque una correspondencia propuesta se puede comprobar en tiempo polinómico. No se sabe si se puede resolver en tiempo polinómico. Y es poco probable que sea NP-completo: Boppana, Håstad y Zachos demostraron en 1987 que, si lo fuera, la jerarquía polinómica colapsaría a su segundo nivel, algo que la mayoría de los investigadores considera inverosímil. Es uno de los muy pocos problemas naturales que se cree que están estrictamente entre los fáciles y los NP-completos.

El mejor algoritmo general es el de Babai. Lo anunció en noviembre de 2015 y lo publicó en STOC en 2016: el isomorfismo de grafos se puede decidir en tiempo cuasipolinómico, exp((log n)O(1)), que no es polinómico pero sí enormemente mejor que exponencial. En enero de 2017 Helfgott encontró un error en un paso, Babai retiró la afirmación de tiempo cuasipolinómico y en pocos días anunció una corrección, que Helfgott confirmó. Para clases especiales se sabe mucho más:

• Los árboles admiten un test en tiempo lineal con el algoritmo de Aho, Hopcroft y Ullman, que construye un código canónico para cada árbol desde las hojas hacia arriba, la técnica que se trata en árboles en teoría de grafos.
• Los grafos planos admiten un test en tiempo lineal, como demostraron Hopcroft y Wong en 1974.
• Los grafos de grado acotado admiten un test en tiempo polinómico, un resultado de Luks de 1982 que se convirtió en una pieza clave del algoritmo de Babai.

10. El isomorfismo de subgrafos es un problema distinto

Un pariente cercano pregunta si un grafo aparece dentro de otro: ¿existe un subgrafo de H que sea isomorfo a G? Este problema de isomorfismo de subgrafos es mucho más difícil. El artículo de Cook de 1971, el que fundó la teoría de la NP-completitud, ya demostró que es tan difícil como la satisfacibilidad, NP-completo en términos actuales. Contiene el problema del clique como caso particular: preguntar si un grafo contiene Kk es preguntar si Kk es un subgrafo suyo.

Los dos problemas son fáciles de confundir porque comparten nombre y estilo algorítmico. Los buscadores prácticos de subgrafos, como el algoritmo de Ullmann de 1976 y VF2, de Cordella y sus colegas en 2004, usan la misma idea de retroceso con poda que la sección 5, pero buscan un patrón, no una correspondencia perfecta, y no se espera ninguna cota cuasipolinómica para ellos. Cuando alguien dice que un problema es «un problema de isomorfismo de grafos», vale la pena preguntar a cuál de los dos se refiere.

11. Dónde se usa el test de isomorfismo

• Química. Los enlaces de una molécula forman un grafo, y las bases de datos químicas usan formas canónicas para guardar cada estructura una sola vez y encontrar un compuesto al instante. El isomorfismo de grafos es necesario pero no suficiente para la identidad química: los estereoisómeros comparten el mismo grafo de enlaces y difieren en su disposición en el espacio.
• Verificación de circuitos. Comprobar que el diseño físico de un chip implementa su esquema, lo que se conoce como layout versus schematic, incluye emparejar la red de transistores extraída del diseño con la prevista.
• Enumeración y bases de datos. Generar todos los grafos, todas las moléculas o todos los diseños de un tamaño dado exige descartar duplicados, lo que supone calcular una forma canónica para cada candidato.
• Aprendizaje automático sobre grafos. La conexión con Weisfeiler–Leman de la sección 6 sirve tanto para medir lo que pueden expresar las redes neuronales de grafos como de referencia rápida para comparar grafos.
• Simetría en optimización. Los automorfismos de la estructura de un problema implican muchas soluciones equivalentes; detectarlos permite a un solucionador saltarse las copias.

12. Errores comunes

13. Glosario

15. Referencias

Las definiciones, teoremas y atribuciones anteriores proceden de estas fuentes, ordenadas cronológicamente.

1. Pólya, G. (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen." Acta Mathematica 68, 145 a 254. Contar objetos salvo simetrías.
2. Frucht, R. (1939). "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Compositio Mathematica 6, 239 a 250.
3. Collatz, L. y Sinogowitz, U. (1957). "Spektren endlicher Grafen." Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 21, 63 a 77. Grafos coespectrales.
4. Erdős, P. y Rényi, A. (1963). "Asymmetric Graphs." Acta Mathematica Academiae Scientiarum Hungaricae 14, 295 a 315.
5. Weisfeiler, B. y Leman, A. (1968). "The Reduction of a Graph to Canonical Form and the Algebra Which Appears Therein." Nauchno-Technicheskaya Informatsia, serie 2, n.º 9, 12 a 16.
6. Cook, S. A. (1971). "The Complexity of Theorem-Proving Procedures." Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151 a 158. El isomorfismo de subgrafos, tan difícil como la satisfacibilidad.
7. Aho, A. V., Hopcroft, J. E. y Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Reading, Massachusetts: Addison-Wesley. Isomorfismo de árboles en tiempo lineal.
8. Hopcroft, J. E. y Wong, J. K. (1974). "Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report)." Proceedings of the 6th Annual ACM Symposium on Theory of Computing, 172 a 184.
9. Ullmann, J. R. (1976). "An Algorithm for Subgraph Isomorphism." Journal of the ACM 23(1), 31 a 42.
10. Babai, L., Erdős, P. y Selkow, S. M. (1980). "Random Graph Isomorphism." SIAM Journal on Computing 9(3), 628 a 635.
11. McKay, B. D. (1981). "Practical Graph Isomorphism." Congressus Numerantium 30, 45 a 87.
12. Luks, E. M. (1982). "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time." Journal of Computer and System Sciences 25(1), 42 a 65.
13. Boppana, R. B., Håstad, J. y Zachos, S. (1987). "Does co-NP Have Short Interactive Proofs?" Information Processing Letters 25(2), 127 a 132.
14. Cordella, L. P., Foggia, P., Sansone, C. y Vento, M. (2004). "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs." IEEE Transactions on Pattern Analysis and Machine Intelligence 26(10), 1367 a 1372.
15. McKay, B. D. y Piperno, A. (2014). "Practical Graph Isomorphism, II." Journal of Symbolic Computation 60, 94 a 112.
16. Babai, L. (2016). "Graph Isomorphism in Quasipolynomial Time." Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 684 a 697.
17. Diestel, R. (2017). Graph Theory, 5.ª edición. Graduate Texts in Mathematics 173. Berlín: Springer.
18. Xu, K., Hu, W., Leskovec, J. y Jegelka, S. (2019). "How Powerful are Graph Neural Networks?" International Conference on Learning Representations.