En 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 grafo dado G. Una forma canónica es un gráfico etiquetado Canon( G ) que es isomorfo a G , de modo que cada gráfico que es isomorfo a G tiene la misma forma canónica que G . Por lo tanto, 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, calcular sus formas canónicas Canon( G ) y Canon( H ), y probar si estas dos formas canónicas son idénticas.
La forma canónica de un gráfico es un ejemplo de invariante de gráfico completo : cada dos gráficos isomórficos tienen la misma forma canónica y cada dos gráficos no isomórficos tienen formas canónicas diferentes. [1] [2] Por el contrario, cada invariante completo de gráficos puede usarse para construir una forma canónica. [3] El conjunto de vértices de un gráfico de n -vértices se puede identificar con los números enteros del 1 al n , y utilizando dicha identificación, una forma canónica de un gráfico también se puede describir 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 .
¿Es el tiempo polinómico de canonización de gráficos equivalente al problema de isomorfismo de gráficos?
El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomórficos . Claramente, el problema de canonización de grafos es al menos tan difícil desde el punto de vista computacional 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, todavía es 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 sigue siendo un problema abierto en la teoría de la complejidad computacional , en 1977 László Babai informó que con una probabilidad de al menos 1 − exp(−O( n )), un algoritmo simple de clasificación de vértices produce un etiquetado canónico de un gráfico elegido uniformemente al azar del conjunto de todos los gráficos de n -vértices después de solo dos pasos de refinamiento. Pequeñas modificaciones y un paso de búsqueda adicional en profundidad producen un etiquetado canónico de dichos gráficos aleatorios elegidos uniformemente en un tiempo lineal esperado. Este resultado arroja algo de luz sobre por qué muchos algoritmos de isomorfismo gráfico reportados 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 manuscrita 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-duro . [7]
Para los árboles, Read (1972) presenta un algoritmo conciso de canonización polinómica que requiere un espacio O(n). [8] Comience etiquetando cada vértice con la cadena 01. De forma iterativa, para cada x que no sea hoja, elimine el 0 inicial y el 1 final de la etiqueta de x; luego ordene la etiqueta de x junto con las etiquetas de todas las hojas adyacentes en orden lexicográfico. Concatene estas etiquetas ordenadas, vuelva a agregar un 0 inicial y un 1 final, conviértala en la nueva etiqueta de x y elimine las hojas adyacentes. Si quedan dos vértices, concatene sus etiquetas en orden lexicográfico.
La canonización de gráficos es la esencia de muchos algoritmos de isomorfismo de gráficos. Una de las herramientas líderes es Nauty. [9]
Una aplicación común de la canonización de gráficos es la minería de datos gráficos , en particular en aplicaciones de bases de datos químicas . [10]
Varios identificadores de sustancias químicas , como SMILES e InChI, utilizan pasos de canonicalización en su cálculo, que es esencialmente la canonicalización del gráfico que representa la molécula. [11] [12] [13] Estos identificadores están diseñados para proporcionar una forma estándar (y a veces legible por humanos) de codificar información molecular y facilitar la búsqueda de dicha información en bases de datos y en la web.