Isomorfismo gráfico

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

f:: V()G)→ → V()H){displaystyle fcolon V(G)to V(H)}

tal que cualquier dos vértices u y v de G están adyacentes G si f()u){displaystyle f(u)} y f()v){displaystyle f(v)} están adyacentes H. Este tipo de bijección se describe comúnmente como "bijeción conservante de borde", de acuerdo con la noción general de isomorfismo siendo una bijeción que conserva la estructura. Si existe un isomorfismo entre dos gráficos, entonces los gráficos se llaman isomorfo y denotado G≃ ≃ H{displaystyle Gsimeq H}. En el caso en que la bijeción es un mapeo de un gráfico sobre sí mismo, es decir, cuando G y H son uno y el mismo gráfico, la bijeción se llama automorfismo G. Si un gráfico es finito, podemos probar que es bijetivo mostrando que es uno-uno/a; no hay necesidad de mostrar ambos. El isomorfismo Gráfico 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 llama un clase de isomorfismo de gráficos. La cuestión de si el isomorfismo gráfico puede determinarse en el tiempo polinomio es un problema importante sin resolver en la informática, conocido como el problema del Isomorfismo Gráfico.

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 no ponderados, no etiquetados y no dirigidos. Sin embargo, la noción de isomórfico puede aplicarse a todas las demás variantes de la noción de grafo, agregando los requisitos para preservar los correspondientes elementos adicionales de estructura: direcciones de arco, pesos de borde, etc., con la siguiente excepción.

Isomorfismo de grafos etiquetados

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 conserva los bordes y las etiquetas.

Según otra definición, un isomorfismo es una biyección de vértice que conserva los bordes y que conserva las clases de equivalencia de las etiquetas, es decir, los vértices con etiquetas equivalentes (p. ej., las mismas) se asignan a los vértices con etiquetas equivalentes y viceversa; Lo mismo con las etiquetas de los bordes.

Por ejemplo, el K2{displaystyle K_{2} El gráfico con los dos vértices etiquetados con 1 y 2 tiene un único 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 enteros 1,...,n, donde n es el número de vértices del gráfico, utilizado solo para identificar de forma única los vértices. En tales casos, a veces se dice que dos gráficos etiquetados son isomorfos si los gráficos no etiquetados subyacentes 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 grafo", captura la noción informal de que algunos objetos tienen "la misma estructura" si uno ignora las distinciones individuales de "atómico" componentes de los objetos en cuestión. Siempre que la individualidad de "atomic" componentes (vértices y aristas, para gráficos) es importante para la representación correcta de lo que sea modelado por gráficos, el modelo se refina imponiendo restricciones adicionales en la estructura, y se utilizan otros objetos matemáticos: dígrafos, gráficos etiquetados, gráficos coloreados, árboles con raíces etcétera. 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/arista, la raíz del árbol enraizado, etc.

La noción de "isomorfismo gráfico" 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 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 isomorfismo clase también tienen exactamente un ciclo. Por otro lado, en el caso común cuando los vértices de un gráfico están (representados por) los números enteros 1, 2,... N, entonces la expresión

.. v▪ ▪ V()G)v⋅ ⋅ degv{displaystyle sum _{vin V(G)}vcdot {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 pero tienen gráficos de línea isomorfos.

El teorema del isomorfismo de la gráfica de Whitney, mostrado por Hassler Whitney, establece que dos gráficas conectadas son isomorfas si y solo si sus gráficas lineales son isomorfas, 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 K₃ como su gráfico lineal. El teorema del gráfico de Whitney se puede extender a las hipergrafías.

Reconocimiento del isomorfismo de grafos

Si bien el isomorfismo de grafos se puede estudiar 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 llama problema de isomorfismo de grafos.

Sus aplicaciones prácticas incluyen principalmente quimioinformática, química matemática (identificación de compuestos químicos) y automatización de 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 & Johnson (1979) cuya complejidad permanece sin resolver, siendo el otro la factorización de 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 de isomorfismo de grafos se puede resolver en tiempo cuasi-polinomio. Publicó versiones preliminares de estos resultados en las actas del Simposio sobre 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 polinomio y en su lugar estableció un límite de complejidad de tiempo subexponencial. Él restauró el reclamo original cinco días después. A partir de 2020, aún no se ha publicado la versión completa de la revista del artículo de Babai.

Se sabe que su generalización, el problema del 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 grafos.