En la teoría de grafos , una rama de las matemáticas, la canonización de grafos es el problema de encontrar una forma canónica de un gráfico G dado . Una forma canónica es un gráfico marcado Canon ( G ) que es isomorfo a G , de manera que cada gráfico que es isomorfo a G tiene la misma forma canónica como G . Así, a partir de una solución al problema de canonización de grafos, también se podría resolver el problema del isomorfismo de grafos : para probar si dos grafos G y H son isomorfos, calcule sus formas canónicas Canon ( G) y Canon ( H ), y compruebe si estas dos formas canónicas son idénticas.
La forma canónica de un gráfico es un ejemplo de un invariante de gráfico completo : cada dos gráficos isomorfos tienen la misma forma canónica, y cada dos gráficos no isomorfos tienen diferentes formas canónicas. [1] [2] A la inversa, cada invariante completo de gráficos puede usarse para construir una forma canónica. [3] El conjunto de vértices de un n gráfico -vertex pueden ser identificados con los números enteros de 1 a n , y el uso de una identificación tal una forma canónica de un gráfico también puede ser descrito como una permutación de sus vértices. Las formas canónicas de un gráfico también se denominan etiquetas canónicas , [4]y la canonización de gráficos también se conoce a veces como canonicalización de gráficos .
Claramente, el problema de canonización de grafos es al menos tan difícil computacionalmente como el problema de isomorfismo de grafos . De hecho, el isomorfismo de grafos es incluso AC 0 , reducible a la canonización de grafos. Sin embargo, sigue siendo una cuestión abierta si los dos problemas son equivalentes en tiempo polinomial . [2]
Si bien la existencia de algoritmos polinomiales (deterministas) para el isomorfismo de grafos es todavía un problema abierto en la teoría de la complejidad computacional , en 1977 László Babai informó que con probabilidad de al menos 1 - exp (−O ( n )), un algoritmo de clasificación de vértice simple produce un etiquetado canónico de un gráfico elegido uniformemente al azar del conjunto de todos los gráficos n -vértices después de solo dos pasos de refinamiento. Pequeñas modificaciones y un paso adicional de búsqueda en profundidad producen un etiquetado canónico de tales gráficos aleatorios elegidos de manera uniforme en el tiempo lineal esperado. Este resultado arroja algo de luz sobre el hecho de por qué muchos algoritmos de isomorfismo de gráficos informados se comportan bien en la práctica. [5] [6]Este fue un avance importante en la teoría de la complejidad probabilística que se hizo ampliamente conocida en su forma de manuscrito y que todavía se citaba como un "manuscrito inédito" mucho después de que se informara en un simposio.
Una forma canónica comúnmente conocida es el gráfico lexicográficamente más pequeño dentro de la clase de isomorfismo , que es el gráfico de la clase con la matriz de adyacencia lexicográficamente más pequeña considerada como una cadena lineal. Sin embargo, el cálculo del gráfico lexicográficamente más pequeño es NP-difícil . [1]
Para los árboles, Read (1972) presenta un algoritmo de canonización polinomial conciso que requiere un espacio O (n ) . [7] Empiece por etiquetar cada vértice con la cadena 01. Iterativamente para cada x que no sea de hoja, elimine el 0 inicial y el 1 final de la etiqueta x; luego ordene la etiqueta de x junto con las etiquetas de todas las hojas adyacentes en orden lexicográfico. Concatenar estas etiquetas ordenadas, volver a agregar un 0 inicial y un 1 final, convertirla en la nueva etiqueta de x y eliminar las hojas adyacentes. Si quedan dos vértices, concatenar sus etiquetas en orden lexicográfico.