Isomorfismo gráfico - Graph isomorphism
En teoría de grafos , un isomorfismo de grafos G y H es una biyección entre los conjuntos de vértices de G y H
tal que cualquiera de los dos vértices 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áficos, entonces los gráficos se denominan isomorfos y se denotan como . En el caso cuando la biyección es una cartografía de un gráfico sobre sí misma, es decir, cuando G y H son una y la misma gráfica, la biyección se llama un automorfismo de G .
El isomorfismo de gráficos es una relación de equivalencia en los 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 .
Los dos gráficos que se muestran a continuación son isomorfos, a pesar de sus dibujos de aspecto diferente .
| Gráfico G | Gráfico H | Un isomorfismo entre G y H |
|---|---|---|
|
|
f ( a ) = 1
f ( b ) = 6 f ( c ) = 8 f ( d ) = 3 f ( g ) = 5 f ( h ) = 2 f ( i ) = 4 f ( j ) = 7 |
Variaciones
En la definición anterior, se entiende que los gráficos son gráficos unidireccionales no etiquetados y no ponderados . Sin embargo, la noción de isomorfo se puede aplicar a todas las demás variantes de la noción de gráfico, agregando los requisitos para preservar los elementos adicionales de estructura correspondientes: direcciones de arco, pesos de borde, etc., con la siguiente excepción.
Isomorfismo de gráficos etiquetados
Para los gráficos etiquetados , se utilizan dos definiciones de isomorfismo.
Bajo una definición, un isomorfismo es una biyección de vértice que preserva los bordes y preserva la etiqueta.
Bajo 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 mapean en los vértices con etiquetas equivalentes y viceversa; lo mismo con las etiquetas de borde.
Por ejemplo, la gráfica 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.
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 forma ú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 no etiquetados 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 los gráficos) es importante para la representación correcta de lo que se modela en los 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 de colores , árboles enraizados, 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 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 gráfico" nos permite distinguir propiedades de gráfico inherentes a las estructuras de los propios gráficos a partir de las propiedades asociadas con las representaciones gráfico: dibujos de gráficos , estructuras de datos para gráficos , marcajes gráfico , 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 una gráfica son ( representados por) los enteros 1, 2, ... N , entonces la expresión
puede ser diferente para dos gráficos isomorfos.
Teorema de Whitney
El teorema del isomorfismo del grafo de Whitney , mostrado por Hassler Whitney , establece que dos grafos conectados son isomorfos si y solo si sus grafos lineales son isomorfos, con una sola excepción: K 3 , el grafo completo en tres vértices y el grafo bipartito completo K 1 , 3 , que no son isomorfos pero ambos tienen K 3 como su gráfica lineal. El teorema del gráfico de Whitney puede extenderse a los hipergráficos .
Reconocimiento del isomorfismo de grafos
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 grafos finitos son isomorfos se llama problema de isomorfismo de grafos.
Sus aplicaciones prácticas incluyen principalmente química informática , química matemática (identificación de compuestos químicos) y automatización del diseño electrónico (verificación de equivalencia de varias representaciones del diseño de un circuito electrónico ).
El problema de 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, siendo el otro la factorización de números enteros . Sin embargo, se sabe que si el problema es NP-completo, la jerarquía polinomial colapsa a un nivel finito.
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 un tiempo cuasi polinomial . Publicó versiones preliminares de estos resultados en las actas del Simposio de Teoría de la Computación de 2016 y del Congreso Internacional de Matemáticos de 2018 . En enero de 2017, Babai se retractó brevemente de la afirmación de cuasi-polinomialidad y, en su lugar, declaró un límite de complejidad de tiempo sub-exponencial . Restauró el reclamo original cinco días después. A partir de 2020, 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 del isomorfismo del subgrafo , 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.
Ver también
- Homomorfismo gráfico
- Problema de automorfismo gráfico
- Problema de isomorfismo gráfico
- Canonización de grafos