En teoría de grafos , un isomorfismo de los gráficos G y H es una biyección entre los conjuntos de vértices de G y H.
tal que dos vértices cualesquiera u y v de G son adyacentes en G si y sólo si y son adyacentes en H. Este tipo de biyección se describe comúnmente como "biyección que preserva los bordes", de acuerdo con la noción general de que el isomorfismo es una biyección que preserva la estructura. Si existe un isomorfismo entre dos gráficas, entonces las gráficas se llaman isomorfas y se denotan como . En el caso de que la biyección sea una aplicación de un gráfico sobre sí mismo, es decir, cuando G y H son el mismo gráfico, la biyección se denomina automorfismo de G. Si una gráfica es finita, podemos demostrar que es biyectiva demostrando que es uno-uno/sobre; no es necesario mostrar ambos. El isomorfismo de gráficos es una relación de equivalencia en gráficos y, como tal, divide la clase de todos los gráficos en clases de equivalencia . Un conjunto de gráficos isomorfos entre sí se denomina clase de gráficos de isomorfismo . La cuestión de si el isomorfismo de grafos se puede determinar en tiempo polinómico es un importante problema sin resolver en informática, conocido como problema de isomorfismo de grafos . [1] [2]
Los dos gráficos que se muestran a continuación son isomórficos, a pesar de sus dibujos de apariencia diferente.
En la definición anterior, se entiende por gráficos no dirigidos , no etiquetados y no ponderados . Sin embargo, la noción de isomorfismo puede aplicarse a todas las demás variantes de la noción de gráfico, agregando los requisitos para preservar los correspondientes elementos adicionales de estructura: direcciones de arco, pesos de aristas, etc., con la siguiente excepción.
Para gráficos etiquetados , se utilizan dos definiciones de isomorfismo.
Según una definición, un isomorfismo es una biyección de vértice que preserva los bordes y las etiquetas. [3] [4]
Según otra definición, un isomorfismo es una biyección de vértices que preserva los bordes y que preserva las clases de equivalencia de etiquetas, es decir, los vértices con etiquetas equivalentes (por ejemplo, las mismas) se asignan a los vértices con etiquetas equivalentes y viceversa; Lo mismo con las etiquetas de los bordes. [5]
Por ejemplo, el gráfico con los dos vértices etiquetados con 1 y 2 tiene un solo automorfismo según la primera definición, pero según la segunda definición hay dos automorfismos.
La segunda definición se asume en ciertas situaciones cuando los gráficos están dotados de etiquetas únicas comúnmente tomadas del rango de números enteros 1,..., n , donde n es el número de vértices del gráfico, usado solo para identificar de manera única los vértices. En tales casos, a veces se dice que dos gráficos etiquetados son isomórficos si los correspondientes gráficos subyacentes sin etiquetar son isomórficos (de lo contrario, la definición de isomorfismo sería trivial).
La noción formal de "isomorfismo", por ejemplo, de "isomorfismo de grafos", captura la noción informal de que algunos objetos tienen "la misma estructura" si se ignoran las distinciones individuales de los componentes "atómicos" de los objetos en cuestión. Siempre que la individualidad de los componentes "atómicos" (vértices y aristas, para gráficos) es importante para la representación correcta de lo que se modela mediante gráficos, el modelo se refina imponiendo restricciones adicionales a la estructura y se utilizan otros objetos matemáticos: dígrafos , gráficos etiquetados. , gráficos coloreados , árboles enraizados , etc. La relación de isomorfismo también se puede definir para todas estas generalizaciones de gráficos: la biyección de isomorfismo debe preservar los elementos de estructura que definen el tipo de objeto en cuestión: arcos , etiquetas, colores de vértice/borde, la raíz del árbol enraizado, etc.
La noción de "isomorfismo de gráficos" nos permite distinguir las propiedades de los gráficos inherentes a las estructuras de los propios gráficos de las propiedades asociadas con las representaciones de los gráficos: dibujos de gráficos , estructuras de datos para gráficos , etiquetado de gráficos , etc. Por ejemplo, si un gráfico tiene exactamente un ciclo , entonces todos los gráficos en su clase de isomorfismo también tienen exactamente un ciclo. Por otro lado, en el caso común cuando los vértices de un gráfico son ( representados por) los números enteros 1, 2,... N , entonces la expresión
puede ser diferente para dos gráficos isomórficos.
El teorema del isomorfismo del gráfico de Whitney , [6] mostrado por Hassler Whitney , establece que dos gráficos conectados son isomorfos si y sólo si sus gráficos lineales son isomorfos, con una única excepción: K 3 , el gráfico completo en tres vértices, y el bipartito completo. gráfico K 1,3 , que no son isomorfos pero ambos tienen K 3 como gráfico lineal. El teorema del grafo de Whitney se puede extender a los hipergrafos . [7]
Si bien el isomorfismo de grafos puede estudiarse de una manera matemática clásica, como lo ejemplifica el teorema de Whitney, se reconoce que es un problema que debe abordarse con un enfoque algorítmico. El problema computacional de determinar si dos gráficos finitos son isomorfos se llama problema de isomorfismo de gráficos.
Sus aplicaciones prácticas incluyen principalmente quimioinformática , química matemática (identificación de compuestos químicos) y automatización del diseño electrónico (verificación de equivalencia de diversas representaciones del diseño de un circuito electrónico ).
El problema del isomorfismo de grafos es uno de los pocos problemas estándar en la teoría de la complejidad computacional que pertenece a NP , pero no se sabe que pertenezca a ninguno de sus subconjuntos bien conocidos (y, si P ≠ NP , disjuntos): P y NP-completo . Es uno de los dos únicos problemas, de un total de 12, enumerados en Garey y Johnson (1979) cuya complejidad sigue sin resolverse; el otro es la factorización de números enteros . Sin embargo, se sabe que si el problema es NP-completo, entonces la jerarquía polinomial colapsa a un nivel finito. [8]
En noviembre de 2015, László Babai , matemático e informático de la Universidad de Chicago, afirmó haber demostrado que el problema del isomorfismo gráfico se puede resolver en tiempo cuasipolinomial . [9] [10] Publicó versiones preliminares de estos resultados en las actas del Simposio sobre Teoría de la Computación de 2016 , [11] y del Congreso Internacional de Matemáticos de 2018 . [12] En enero de 2017, Babai se retractó brevemente de la afirmación de cuasipolinomio y en su lugar declaró un límite de complejidad temporal subexponencial . Restauró el reclamo original cinco días después. [13] A partir de 2020 [actualizar], la versión completa del artículo de Babai aún no se ha publicado.
Se sabe que su generalización, el problema de isomorfismo de subgrafos , es NP-completo.
Las principales áreas de investigación del problema son el diseño de algoritmos rápidos y las investigaciones teóricas de su complejidad computacional , tanto para el problema general como para clases especiales de gráficos.
La prueba de isomorfismo de gráficos de Weisfeiler Leman se puede utilizar para probar heurísticamente el isomorfismo de gráficos. [14] Si la prueba falla, se garantiza que los dos gráficos de entrada no serán isomorfos. Si la prueba tiene éxito, las gráficas pueden ser isomorfas o no. Existen generalizaciones del algoritmo de prueba que garantizan la detección de isomorfismos; sin embargo, su tiempo de ejecución es exponencial.
{{cite journal}}: Mantenimiento CS1: fecha y año ( enlace )