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 grafo etiquetado Canon( G ) que es isomorfo a G , de modo que cada grafo 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 grafo es un ejemplo de un invariante de grafo completo : cada dos grafos isomorfos tienen la misma forma canónica, y cada dos grafos no isomorfos tienen diferentes formas canónicas. [1] [2] Por el contrario, cada invariante completo de grafos puede usarse para construir una forma canónica. [3] El conjunto de vértices de un grafo de n vértices puede identificarse con los números enteros de 1 a n , y usando tal identificación una forma canónica de un grafo también puede describirse como una permutación de sus vértices. Las formas canónicas de un grafo también se denominan etiquetados canónicos , [4] y la canonización de grafos también se conoce a veces como canonización de grafos .
El problema del isomorfismo de grafos es el problema computacional de determinar si dos grafos finitos son isomorfos . Claramente, el problema de canonización de grafos es al menos tan difícil computacionalmente como el problema del 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 pregunta abierta si los dos problemas son equivalentes en tiempo polinomial . [2]
En 2019, László Babai anunció un algoritmo de tiempo cuasi-polinomial para la canonización de grafos, es decir, uno con tiempo de ejecución para algún fijo . [5] 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 grafo elegido uniformemente al azar del conjunto de todos los grafos de n vértices después de solo dos pasos de refinamiento. Pequeñas modificaciones y un paso de búsqueda en profundidad agregado producen un etiquetado canónico de dichos grafos aleatorios elegidos uniformemente en un tiempo esperado lineal. Este resultado arroja algo de luz sobre el hecho de por qué muchos algoritmos de isomorfismo de grafos informados se comportan bien en la práctica. [6] [7] Este fue un avance importante en la teoría de la complejidad probabilística que llegó a ser ampliamente conocido 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 conocida comúnmente es el grafo lexicográficamente más pequeño dentro de la clase de isomorfismo , que es el grafo 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 grafo lexicográficamente más pequeño es NP-hard . [8]
Para los árboles, Read (1972) presenta un algoritmo de canonización polinomial conciso que requiere un espacio O(n). [9] Comience etiquetando cada vértice con la cadena 01. De manera iterativa, para cada x que no sea una 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, agregue nuevamente un 0 inicial y un 1 final, haga que esta sea 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 grafos es la esencia de muchos algoritmos de isomorfismo de grafos. Una de las herramientas más importantes es Nauty. [10]
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 . [11]
Varios identificadores de sustancias químicas , como SMILES e InChI, utilizan pasos de canonización en su cálculo, que es esencialmente la canonización del gráfico que representa la molécula. [12] [13] [14] 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.
