Isomorfismo de grafos

Biyección entre el conjunto de vértices de dos grafos

En teoría de grafos , un isomorfismo de los grafos G y H es una biyección entre los conjuntos de vértices de G y H.

${\displaystyle f\colon V(G)\to V(H)}$

de modo que dos vértices cualesquiera u y v de G son adyacentes en G si y solo si y son adyacentes en H. Este tipo de biyección se describe comúnmente como "biyección que preserva las aristas", de acuerdo con la noción general de que el isomorfismo es una biyección que preserva la estructura. ${\displaystyle f(u)}$ ${\displaystyle f(v)}$

Si existe un isomorfismo entre dos grafos, entonces los grafos se denominan isomorfos y se denotan como . En el caso en que el isomorfismo es una aplicación de un grafo sobre sí mismo, es decir, cuando G y H son uno y el mismo grafo, el isomorfismo se denomina automorfismo de G . ${\displaystyle G\simeq H}$

El isomorfismo de grafos es una relación de equivalencia entre grafos y, como tal, divide la clase de todos los grafos en clases de equivalencia . Un conjunto de grafos isomorfos entre sí se denomina clase de isomorfismo de grafos. La cuestión de si el isomorfismo de grafos se puede determinar en tiempo polinomial es un importante problema sin resolver en informática, conocido como el problema del isomorfismo de grafos . ^{[1] [2]}

Los dos gráficos que se muestran a continuación son isomorfos, a pesar de que sus dibujos tienen un aspecto diferente .

Variaciones

En la definición anterior, se entiende por grafos aquellos que no están dirigidos , no están etiquetados y no tienen ponderaciones . Sin embargo, la noción de isomorfismo puede aplicarse a todas las demás variantes de la noción de grafo, añadiendo los requisitos de preservar los elementos adicionales correspondientes de la estructura: direcciones de los arcos, pesos de las aristas, etc., con la siguiente excepción.

Isomorfismo de grafos etiquetados

Para los gráficos etiquetados , se utilizan dos definiciones de isomorfismo.

Según una definición, un isomorfismo es una biyección de vértices que preserva tanto los bordes como las etiquetas. ^{[3] [4]}

Según otra definición, un isomorfismo es una biyección de vértices que preserva las aristas y que preserva las clases de equivalencia de las 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 ocurre con las etiquetas de las aristas. ^[5]

Por ejemplo, el gráfico con los dos vértices etiquetados con 1 y 2 tiene un solo automorfismo bajo la primera definición, pero bajo la segunda definición hay dos automorfismos. ${\displaystyle K_{2}}$

La segunda definición se asume en ciertas situaciones en las que los grafos están dotados de etiquetas únicas, comúnmente tomadas del rango entero 1,..., n , donde n es el número de vértices del grafo, utilizado únicamente para identificar de forma única los vértices. En tales casos, a veces se dice que dos grafos etiquetados son isomorfos si los grafos subyacentes no etiquetados correspondientes son isomorfos (de lo contrario, la definición de isomorfismo sería trivial).

Motivación

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 grafos) sea importante para la representación correcta de lo que sea que se modele mediante grafos, el modelo se refina imponiendo restricciones adicionales a la estructura y se utilizan otros objetos matemáticos: dígrafos , grafos etiquetados , grafos coloreados , árboles con raíz , etc. La relación de isomorfismo también se puede definir para todas estas generalizaciones de grafos: la biyección de isomorfismo debe preservar los elementos de la estructura que definen el tipo de objeto en cuestión: arcos , etiquetas, colores de vértices/aristas, la raíz del árbol con raíz, etc.

La noción de "isomorfismo de grafos" nos permite distinguir las propiedades de los grafos inherentes a las estructuras de los grafos mismos de las propiedades asociadas con las representaciones de los grafos: dibujos de grafos , estructuras de datos para grafos , etiquetados de grafos , etc. Por ejemplo, si un grafo tiene exactamente un ciclo , entonces todos los grafos 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 grafo son ( representados por) los números enteros 1, 2,... N , entonces la expresión

${\displaystyle \sum _{v\in V(G)}v\cdot {\text{deg }}v}$

Puede ser diferente para dos gráficos isomorfos.

Teorema de Whitney

La excepción al teorema de Whitney: estos dos gráficos no son isomorfos sino que tienen gráficos lineales isomorfos.

El teorema de isomorfismo de grafos de Whitney , ^[6] demostrado por Hassler Whitney , establece que dos grafos conexos son isomorfos si y solo si sus grafos lineales son isomorfos, con una única excepción: K ₃ , el grafo completo en tres vértices, y el grafo bipartito completo K _1,3 , que no son isomorfos pero ambos tienen a K ₃ como su grafo lineal. El teorema de grafos de Whitney se puede extender a los hipergrafos . ^[7]

Reconocimiento del isomorfismo de grafos

Si bien el isomorfismo de grafos puede estudiarse de forma 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 grafos finitos son isomorfos se denomina problema de isomorfismo de grafos.

Sus aplicaciones prácticas incluyen principalmente la quimioinformática , la química matemática (identificación de compuestos químicos) y la automatización del diseño electrónico (verificación de la equivalencia de varias 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 únicos dos, de un total de 12, problemas enumerados en Garey & Johnson (1979) cuya complejidad permanece sin resolver, el otro es la factorización de enteros . Sin embargo, se sabe que si el problema es NP-completo, la jerarquía polinómica colapsa a un nivel finito. ^[8]

En noviembre de 2015, László Babai , matemático y científico informático de la Universidad de Chicago, afirmó haber demostrado que el problema del isomorfismo de grafos se puede resolver en tiempo cuasipolinomial . ^{[9] [10]} Publicó versiones preliminares de estos resultados en las actas del Simposio de 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 cuasipolinomia y declaró en su lugar un límite de complejidad temporal subexponencial . Restableció la afirmación original cinco días después. ^[13] A fecha de 2024 ^[actualizar], la versión completa de la revista 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 para el 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 grafos de Weisfeiler-Leman se puede utilizar para probar heurísticamente el isomorfismo de grafos. ^[14] Si la prueba falla, se garantiza que los dos grafos de entrada no son isomorfos. Si la prueba tiene éxito, los grafos pueden ser isomorfos o no. Existen generalizaciones del algoritmo de prueba que garantizan la detección de isomorfismos, sin embargo, su tiempo de ejecución es exponencial.

Otro algoritmo conocido para el isomorfismo de grafos es el algoritmo vf2, desarrollado por Cordella et al. en 2001. ^[15] El algoritmo vf2 es un algoritmo de búsqueda en profundidad que intenta construir un isomorfismo entre dos grafos de forma incremental. Utiliza un conjunto de reglas de viabilidad para podar el espacio de búsqueda, lo que le permite manejar de manera eficiente grafos con miles de nodos. El algoritmo vf2 ha sido ampliamente utilizado en varias aplicaciones, como reconocimiento de patrones, visión artificial y bioinformática. Si bien tiene una complejidad temporal exponencial en el peor de los casos, funciona bien en la práctica para muchos tipos de grafos.

Véase también

• Homomorfismo de grafos
• Problema de automorfismo de grafos
• Problema de isomorfismo de grafos
• Canonización de gráficos

Notas

1. Grohe, Martin (1 de noviembre de 2020). "El problema del isomorfismo de grafos". Comunicaciones de la ACM . 63 (11): 128–134. doi :10.1145/3372123 . Consultado el 6 de marzo de 2023 .{{cite journal}}: Mantenimiento CS1: fecha y año ( enlace )
2. Klarreich, Erica (14 de diciembre de 2015). «El algoritmo Landmark rompe un impasse de 30 años». Quanta Magazine . Consultado el 6 de marzo de 2023 .
3. pág. 424
4. Hsieh, Shu-Ming; Hsu, Chiun-Chieh; Hsu, Li-Fu (2006). "Método eficiente para realizar pruebas de isomorfismo de gráficos etiquetados". Ciencias computacionales y sus aplicaciones - ICCSA 2006 . Apuntes de clase en informática. Vol. 3984. págs. 422–431. doi :10.1007/11751649_46. ISBN 978-3-540-34079-9.
5. Pierre-Antoine Champin, Christine Solnon, "Medición de la similitud de gráficos etiquetados" en: Lecture Notes in Computer Science , vol. 2689, págs. 80-95
6. Whitney, Hassler (enero de 1932). "Gráficos congruentes y conectividad de grafos". American Journal of Mathematics . 54 (1): 150–168. doi :10.2307/2371086. hdl : 10338.dmlcz/101067 . JSTOR  2371086.
7. Dirk L. Vertigan, Geoffrey P. Whittle: Un teorema de 2-isomorfismo para hipergrafos. J. Comb. Theory, Ser. B 71(2): 215–230. 1997.
8. Schöning, Uwe (1988). "El isomorfismo de grafos se encuentra en la jerarquía baja". Journal of Computer and System Sciences . 37 (3): 312–323. doi :10.1016/0022-0000(88)90010-4.
9. Cho, Adrian (10 de noviembre de 2015), "Un matemático afirma haber logrado un gran avance en la teoría de la complejidad", Science , doi :10.1126/science.aad7416.
10. Klarreich, Erica (14 de diciembre de 2015), "Un algoritmo emblemático rompe un impasse de 30 años", Quanta Magazine
11. Babai, László (2016), "Isomorfismo de grafos en tiempo cuasipolinomial [resumen extendido]", STOC'16—Actas del 48.° Simposio Anual ACM SIGACT sobre Teoría de la Computación , ACM, Nueva York, págs. 684–697, doi :10.1145/2897518.2897542, ISBN 978-1-4503-4132-5, MR  3536606, S2CID  17118954
12. Babai, László (2018), "Grupo, grafos, algoritmos: el problema del isomorfismo de grafos", Actas del Congreso Internacional de Matemáticos—Río de Janeiro 2018. Vol. IV. Conferencias invitadas , World Sci. Publ., Hackensack, NJ, pp. 3319–3336, MR  3966534
13. Babai, László (9 de enero de 2017), Actualización de isomorfismo gráfico
14. Huang, Ningyuan Teresa; Villar, Soledad (2021). "Un breve tutorial sobre la prueba de Weisfeiler-Lehman y sus variantes". ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) . págs. arXiv : 2201.07083 . doi :10.1109/ICASSP39728.2021.9413523. ISBN 978-1-7281-7605-5. Número de identificación del sujeto  235780517.
15. Cordella, LP; Foggia, P.; Sansone, C.; Vento, M. (2001). "Un algoritmo mejorado para la correspondencia de gráficos grandes". Tercer taller IAPR-TC15 sobre representaciones basadas en gráficos en el reconocimiento de patrones : 149–159.

Referencias

• Garey, Michael R. ; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Serie de libros sobre ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. Sr.  0519066. OCLC  247570676.