¿Hay cualquier algoritmo para encontrar función de isomorfismo entre dos grafos?

Question

Dos gráficos que contienen el mismo número de vértices del grafo conectado de la misma manera se dice que son isomorfos. Formalmente, dos gráficos y con el gráfico vértices se dice que son isomorfos si existe una permutación de tal que está en el conjunto de los bordes del gráfico iff está en el conjunto de los bordes del gráfico. (entonces, ahora tengo dos gráficos e incluso sé que son isomorfos. pero no tengo una forma eficaz de encontrar esa permutación para demostrar que son isomorfos. Acabo de tratar de encontrar pero no es una buena manera porque toma demasiado tiempo y es como una permutación aleatoria.
¿Hay algún algoritmo o método sistemático para encontrar la permutación entre dos grafos isomorfos?

Gracias de antemano.

Answer 1

Esta muy interesante la pregunta que me temo que tiene (de momento) un poco decepcionante respuesta.

El problema de la gráfica de isomorfismo ha sido un objeto de estudio de la Complejidad Computacional desde los inicios del campo. Claramente, es un problema que pertenece a NP, es decir, la clase de problemas para los cuales las respuestas puede ser fácilmente verificado dado un 'testigo'- una pieza adicional de información que valida, en cierto sentido, la respuesta.

Por ejemplo, dados dos grafos isomorfos un testigo de su isomorfismo podría ser la permutación que transforma un gráfico en el otro.

Ahora la parte interesante. NP se divide en P (polinomio tiempo solveable) problemas NP-completos y problemas NP-intermedio problemas. Un NP completo es un problema cuya solución puede ser usado para codificar cualquier otro problema NP, lo que significa que si se pudiera solucionar de manera eficiente un NP-completo problema, podría solucionar de manera eficiente todos ellos, y por lo tanto $P=NP$.

Sin embargo, la mayoría de los investigadores creen que el $P\ne NP$. Una de las consecuencias de esto es la existencia de NP-intermedio problemas (Lardner del teorema) - problemas en NP, pero no en P ni NP-completo. Un aspecto destacado de la prueba de Ladner del teorema es que el hipotético lenguaje construido es muy poco natural. Es un problema abierto para encontrar un real NP-lenguaje intermedio.

Algunos candidatos han sido descalificados como posibles candidatos a la NP-intermediateness, pero el gráfico isomorfismo es uno de los restantes. Nosotros no sabemos en realidad si GI es en P, NP-completos o NP-intermedio.

La evidencia, sin embargo, sugiere que es NP-intermedio o P. Hay una muy reciente avance, debido a Babai, lo que demuestra que GI es soluble en cuasi-polinomio de tiempo, que es algo que no podemos esperar de un tipo NP-completo el problema.

Espero no han dejado ningún detalle. Siéntase libre de hacer preguntas acerca de GI o su primo, el gráfico no isomorfismo.

Answer 2

Como otros comentaristas han señalado, no es sencillo algoritmo para todos los gráficos que se ejecuta muy rápido. Sé que 'muy rápido' es vago, pero yo no soy capaz de analizar la complejidad del problema se da especialmente bien.

Sin embargo...

Para muchas clases de gráfico, tales como las de los delimitada grado, treewidth, etc - hay varios algoritmos para determinar un isomorfismo de la función que le asignan uno a la otra.

Un enfoque se basa en la partición de refinamiento. Esto es muy bien descrito aquí , pero voy a dar una breve descripción de como yo la entiendo. Tenga en cuenta que esto es a grandes rasgos la técnica utilizada por nAUTy y programas similares (bliss, rastros, descarado) para calcular gráfico isomorphisms y automorfismos.

Lo que se requiere para isomorfismo entre los dos gráficos - G, H - es un canónica de etiquetado (cl) para cada una de las que cl(G) = cl(H). Si usted simplemente querían probar para isomorfismo, entonces usted podría calcular un "certificado" para ambos. Por un par de árboles, esto es tan simple como una cadena formada por recursivamente de la construcción de las hojas (que llevan la etiqueta '01'), la clasificación en cada etapa, hasta llegar a la raíz (ver la descripción de partida "Para los árboles..." en la página de la wiki para canónica de etiquetado).

Para obtener la actual asignación, necesitamos crear una canónica de etiquetado - en otras palabras, elegir un determinado permutación para cada gráfico que 'reetiqueta' en la forma canónica. Aquí es donde la partición de refinamiento. Comenzando con una partición root - tales como la partición de los vértices de grado - nos sucesivamente 'refinar' la partición hasta que llegamos permutaciones. Las permutaciones son, en este punto de vista, sólo 'discretos' particiones con un vértice en cada bloque.

Aquí, una partición de Un es "más fino" que el de otra partición de B si tenemos dividir uno o más de los bloques de conseguir B. Dependiendo de cómo deseamos que el bloque de dividir, y cómo los bloques están ordenados en el refinado niño partición, tenemos un especial de etiquetado. El procedimiento de refinamiento de las formas de un árbol de particiones, con permutaciones como las hojas - y elegimos (decir) la primera de ellas nos alcance.

Es evidente que hay mucho más en este tema, pero es una buena introducción a este que he encontrado en este libro llamado "los Algoritmos de cálculo : la Generación de la Enumeración y de la Búsqueda" por Kreher y Stinson.

Answer 3

Si usted tuvo un polinomio en tiempo del algoritmo (con un polinomio de complejidad obligado, decir $C n^p$) para encontrar un isomorfismo para un par de gráficos que son, de hecho, isomorfo, usted podría utilizar para determinar en el polinomio tiempo si dos grafos son isomorfos. Es decir, se ejecuta el algoritmo con un tiempo límite de $C n^p$, y comprobar si se produce un isomorfismo. Tenga en cuenta que es fácil comprobar en el polinomio tiempo si algo es un isomorfismo de los gráficos.

Si los dos gráficos de pasar a ser isomorfos, entonces, por supuesto, el algoritmo produce un isomorfismo dentro de ese límite de tiempo, y su isomorfismo corrector de comprobar que es un isomorfismo. Si no, entonces ¿qué puede suceder? El algoritmo se ejecutará sobre el límite de tiempo, o va a parar dentro del límite de tiempo con algún resultado (tal vez un mensaje de error, o tal vez algo que no es un isomorfismo), y su isomorfismo corrector de mostrar que esto no es un isomorfismo.

Como otros han mencionado, no nos curently tienen un polinomio de tiempo de algoritmo para decidir gráfico isomorfismo, y hay alguna razón para creer que no existe tal algoritmo.

Sin embargo, eso es todo lo peor de la complejidad. En más "típico" de los casos, gráfico isomorfismo es relativamente fácil. Ver, por ejemplo, McKay y Picerno, "Práctico Gráfico Isomorfismo II".