Isomorfismo gráfico

En teoría de grafos, un isomorfismo de grafos es una biyección entre conjuntos de vértices de grafos tales que dos vértices cualesquiera y el gráfico son adyacentes si y solo si los vértices y son adyacentes en el gráfico . Aquí, se entiende que los gráficos no están dirigidos y no tienen pesos de vértice y borde. Si el concepto de isomorfismo se aplica a gráficos dirigidos o ponderados, se imponen restricciones adicionales sobre la preservación de la orientación del arco y los valores de peso. Si se establece el isomorfismo de las gráficas, se denominan isomorfas y se denotan como . $G=\izquierda\langle V_{G},E_{G}\right\rangle$ $H=\izquierda\langle V_{H},E_{H}\right\rangle$ $f\dos puntos\V_{G}\rightarrow V_{H}$ $tu$ $v$ $GRAMO$ $f(tu)$ $f(v)$ $H$ $G \ simeq H$

A veces, una biyección se escribe como una sustitución de isomorfismo . Algunos problemas de procesamiento de gráficos requieren no solo verificar el isomorfismo, sino también descubrir su sustitución. $F$ ${\begin{pmatrix}a_{1}&a_{2}&\puntos &a_{n}\\f(a_{1})&f(a_{2})&\puntos &f(a_{n})\end{ pmatrix}}$

La relación de isomorfismo de grafos es una relación de equivalencia definida para grafos y permite dividir la clase original de todos los grafos en clases de equivalencia . El conjunto de grafos isomorfos entre sí se denomina clase , su número depende de la secuencia A000088 en OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346, .. .) . $norte$

Si la biyección mapea el gráfico sobre sí mismo (los gráficos y coinciden), se llama automorfismo de gráfico . $F$ $GRAMO$ $H$ $GRAMO$

También hay problemas relacionados en la teoría de grafos, como encontrar un subgrafo isomorfo y encontrar un subgrafo isomorfo común máximo , que pertenecen a la clase de NP-completo . En ramas afines de las matemáticas, existen problemas similares, por ejemplo, el isomorfismo de planos proyectivos y el isomorfismo de grupos finitos , que son reducibles polinómicamente al problema de isomorfismo gráfico (la posibilidad de reducibilidad polinomial inversa no ha sido probada en el caso general ) [1] .

Ejemplo

Los dos gráficos dados en el ejemplo son isomorfos.

Grafico $GRAMO$	Grafico $H$	Isomorfismo entre gráficas y $GRAMO$ $H$	sustitución de isomorfismo $F$
		$f(a)=1$ $f(b)=6$ $f(c)=8$ $f(d)=3$ $f(g)=5$ $f(h)=2$ $f(yo)=4$ $f(j)=7$	${\begin{pmatrix}a&b&c&d&g&h&i&j\\1&6&8&3&5&2&4&7\end{pmatrix}}$

Isomorfismo general de grafos

Los gráficos y son isomorfos si permutando las filas y columnas de la matriz de adyacencia del gráfico , es posible obtener la matriz de adyacencia del gráfico . Sin embargo, la enumeración de todas las permutaciones posibles se caracteriza por la complejidad computacional (siempre que las matrices de adyacencia se comparen en un tiempo independiente de , lo que suele ser injusto y además aumenta la estimación anterior), lo que limita significativamente la aplicación de este enfoque en la práctica. Hay métodos para la enumeración limitada de posibles pares de vértices supuestamente isomórficos (análogos al método de ramificación y límite ), pero mejoran ligeramente las asintóticas anteriores [2] . $GRAMO$ $H$ $GRAMO$ $H$ $¡EN!)$ $norte$

Teorema de Whitney

El teorema de isomorfismo de grafos de Whitney [3] [4] , formulado por Hassler Whitney en 1932 , establece que dos grafos conectados son isomorfos si y solo si sus gráficos lineales son isomorfos, a excepción de los grafos (un gráfico completo de 3 vértices) y un bipartito completo graph , que no son isomorfos, pero ambos tienen un gráfico como un gráfico de líneas. El teorema de Whitney se puede generalizar a las hipergrafías [5] . $K_{3}$ $K_{{1,3}}$ $K_{3}$

Invariantes

Hay un conjunto de características numéricas de los gráficos, llamados invariantes , que coinciden para gráficos isomorfos (la coincidencia de invariantes es una condición necesaria pero no suficiente para el isomorfismo) [6] . Estos incluyen el número de vértices y el número de arcos/aristas del gráfico G , el vector de grados de vértices ordenados en orden ascendente o descendente, el vector de valores propios de la matriz de adyacencia del gráfico (espectro de gráfico) ordenados en orden ascendente o descendente. el orden descendente, el número cromático , etc. El hecho de que los invariantes coincidan no suele aportar información sobre la sustitución de isomorfismos. $n(G)$ $m(G)$ $s(G)=(\rho (v_{1}),\rho (v_{2}),\puntos,\rho (v_{n}))$ $\ chi (G)$

Se dice que un invariante es completo si la coincidencia de los invariantes del gráfico es necesaria y suficiente para establecer un isomorfismo. Por ejemplo, cada uno de los valores y (el código mini y maxi de la matriz de adyacencia) es un invariante completo para un gráfico con un número fijo de vértices . $\mu _{{min}}(G)$ $\mu _{{máx}}(G)$ $norte$

Diferentes invariantes tienen diferente complejidad computacional. Actualmente se desconoce un grafo completo invariante computable en tiempo polinomial, pero no se ha probado que no exista. Los intentos de encontrarlo se hicieron repetidamente en los años 60 y 80 del siglo XX , pero no tuvieron éxito.

Producto Weesing modular

El producto modular de grafos , propuesto por V. G. Vizing , nos permite reducir el problema de comprobar el isomorfismo al problema de determinar la densidad de un grafo que contiene vértices. Si , , entonces el gráfico contiene un subgráfico isomorfo al gráfico . $Y=G\rombo H$ $\varfi (Y)$ $n(G)\cdot n(H)$ $\varphi (Y)=n(G)$ $n(G)\leq n(H)$ $H$ $GRAMO$

Isomorfismo de grafos de una forma especial

Complejidad computacional

Aunque el problema de isomorfismo de grafos pertenece a la clase NP , no se sabe si es NP-completo o pertenece a la clase P (suponiendo que P ≠ NP ). Además, el problema de encontrar un subgrafo isomorfo en un grafo es NP-completo . La investigación moderna tiene como objetivo desarrollar algoritmos rápidos para resolver tanto el problema general del isomorfismo de gráficos arbitrarios como gráficos de un tipo especial.

Aplicaciones

En la práctica, la necesidad de verificar el isomorfismo de los gráficos surge cuando se resuelven problemas de quimioinformática , química matemática (computadora) [7] , automatización del diseño de circuitos electrónicos (verificación de varias representaciones de un circuito electrónico ) [2] , optimización de programas (identificación de subexpresiones comunes).

Véase también

Invariante (matemáticas)
problemas matematicos abiertos
El problema de encontrar un subgrafo isomorfo
subgrafo isomorfo común máximo

Enlaces

Problema de isomorfismo gráfico _ _

Notas

↑ Ponomarenko I. N. El problema del isomorfismo de grafos: aspectos algorítmicos (notas para conferencias) Copia de archivo del 22 de junio de 2018 en Wayback Machine
↑ 1 2 Kureichik V. M., Glushan V. M., Shcherbakov L. I. Modelos de hardware combinatorios y algoritmos en CAD. - M. : Radio y comunicación, 1990. - 216 p.
↑ H. Whitney. Gráficos congruentes y conectividad de gráficos // Am. J. Matemáticas.. - 1932. - T. 54 . - S. 160-168 . -doi : 10.2307/ 2371086 .
↑ Harari F. Teoría de grafos . - M .: Mir , 1973. (Ed. 3, M.: KomKniga, 2006. - 296 p.)
↑ Dirk L. Vertigan, Geoffrey P. Whittle. Un teorema de 2 isomorfismos para hipergrafías // J. Comb. Teoría, Ser. B. - 1997. - T. 71 , núm. 2 . - S. 215-230 . -doi : 10.1006/ jctb.1997.1789 .
↑ Zykov A. A. . Fundamentos de la teoría de grafos. — M .: Nauka, 1986. — 384 p. - ISBN 978-5-9502-0057-1 .
↑ Trofimov M. I., Smolensky E. A. Aplicación de índices de electronegatividad de moléculas orgánicas en problemas de informática química // Izvestiya de la Academia de Ciencias. Serie química. - 2005. - S. 2166-2176 .