transformaciones teorema resueltos monomorfismo matematicas lineal isomorfos isomorfismo identificar grafos epimorfismo ejercicios discretas como algorithm graph

algorithm - teorema - Isomorfismo Gráfico



teorema de la dimension (9)

¿Hay un algoritmo o heurística para el isomorfismo gráfico?

Corolario: un gráfico se puede representar en diferentes dibujos diferentes.

¿Cuál es el mejor enfoque para encontrar diferentes dibujos de un gráfico?

Es un gran problema.

En general, la idea básica es simplificar el gráfico en una forma canónica, y luego realizar la comparación de las formas canónicas. Los árboles de expansión se generan con este objetivo, pero los árboles de expansión no son únicos, por lo que debe tener una forma canónica para crearlos.

Después de tener formas canónicas, puede realizar la comparación de isomorfismo (relativamente) fácil, pero eso es solo el comienzo, ya que los gráficos no isomórficos pueden tener el mismo árbol de expansión. (por ejemplo, piense en un árbol de expansión T y una sola adición de un borde para crear T ''. Estos dos gráficos no son isomorfos, pero tienen el mismo árbol de expansión).

Otras técnicas implican la comparación de descriptores (por ejemplo, número de nodos, número de bordes), que pueden producir falsos positivos en general.

Te sugiero que comiences con la página wiki sobre el problema del isomorfismo gráfico . También tengo un libro para sugerir: "Teoría de gráficos y sus aplicaciones" . Es un tomo, pero vale la pena en cada página.

A partir de su corolario, toda posible distribución espacial de los vértices de un gráfico determinado es un isomorfo. Entonces, dos gráficos isomorfos tienen la misma topología y son, al final, el mismo gráfico, desde el punto de vista topológico. Otra cuestión es, por ejemplo, encontrar esas estructuras isomorfas que disfrutan de propiedades particulares (por ejemplo, con bordes que no cruzan, si existen), y eso depende de las propiedades que desee.

Hay algoritmos para hacer esto, sin embargo, no he tenido motivos para investigarlos seriamente hasta el momento. Creo que Donald Knuth está escribiendo o ha escrito sobre este tema en su serie Art of Computing durante su segundo pase al (re) escribirlos.

En cuanto a una forma simple de hacer algo que podría funcionar en la práctica en gráficos pequeños, recomendaría contar grados, luego para cada vértice, también tenga en cuenta el conjunto de grados para los vértices adyacentes. Esto le dará un conjunto de posibles isomorfismos de vértice para cada punto. A continuación, intente todos estos (a través de la fuerza bruta, pero eligiendo los vértices en orden creciente de posibles conjuntos de isomorfismo de vértices) de este conjunto restringido. Intuitivamente, la mayoría del isomorfismo gráfico se puede calcular de esta manera de manera práctica, aunque es evidente que habría casos degenerados que podrían llevar mucho tiempo.

Hace poco encontré el siguiente artículo: http://arxiv.org/abs/0711.2010 Este artículo propone "Algoritmo de tiempo polinomial para isomorfismo de gráfico"

Un problema muy similar, el automorfismo de gráficos, se puede resolver con descaro , que está disponible en el código fuente. Esto encuentra todas las simetrías de un gráfico. Si tiene dos gráficos, únalos en uno y cualquier isomorfismo se puede descubrir como un automorfismo de la unión.

Descargo de responsabilidad: soy uno de los coautores de descaro.

nauty y Traces son programas para calcular grupos de automorfismos de gráficos y dígrafos [*]. También pueden producir una etiqueta canónica. Están escritos en un subconjunto portátil de C y se ejecutan en un número considerable de sistemas diferentes.

En cuanto a la heurística: he estado fantaseando con un algoritmo de Ullmann modificado, donde no solo utiliza la primera búsqueda de amplitud sino que la mezcla con la profundidad primero busca el camino, que primero utiliza la búsqueda de amplitud en primer lugar de forma intensiva, que establece un límite para análisis de amplitud e ir más profundo después de verificar unos pocos vecinos, y se baja el pan cada paso en cierta cantidad. Así es como me encuentro en un mapa: primero me ubico con la primera búsqueda de ancho, luego busco la ruta con la primera búsqueda de profundidad, en gran medida, y esta es la mejor evolución de mi cerebro que jamás se haya inventado. :) A largo plazo, se puede agregar cierta inteligencia para aumentar el primer recuento vecino de búsqueda en los vértices críticos, por ejemplo, donde hay un gran número de vértices vecinos con el mismo recuento de bordes. Como verificar tu ruta real a veces con el auto (sin gps).

Descubrí que el algoritmo pertenece a la categoría de los algoritmos Weisfeiler-Lehman de dimensión k y falla con los gráficos regulares. Para más aquí:

http://dabacon.org/pontiff/?p=4148

La publicación original sigue:

He trabajado en el problema para encontrar gráficos isomórficos en una base de datos de gráficos (que contienen composiciones químicas).

En resumen, el algoritmo crea un hash de un gráfico utilizando el método de iteración de potencia. Puede haber falsas colisiones hash positivas, pero la probabilidad de que sea muy pequeña (no tuve tales colisiones con decenas de miles de gráficos).

La forma en que funciona el algoritmo es esta:

Realice iteraciones N (donde N es el radio del gráfico). En cada iteración y para cada nodo:

  • Ordenar los hash (del paso anterior) de los vecinos del nodo
  • Hash los hash ordenados concatenados
  • Reemplace el hash del nodo con hash recién calculado

En el primer paso, el hash de un nodo se ve afectado por los vecinos directos del mismo. En el segundo paso, el hash de un nodo se ve afectado por el vecindario a 2 saltos de él. En el N-ésimo paso, el hash de un nodo se verá afectado por los N-hop vecinos que lo rodean. Por lo tanto, solo tiene que seguir ejecutando Powerhash para N = steps graph_radius. Al final, el hash del nodo del centro del gráfico se habrá visto afectado por el gráfico completo.

Para producir el hash final, clasifique los hashes de nodo del paso final y concatenarlos juntos. Después de eso, puedes comparar los hashes finales para encontrar si dos gráficos son isomórficos. Si tiene etiquetas, agréguelas (en el primer paso) a los valores hash internos que calcule para cada nodo.

Hay más antecedentes aquí:

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

Puede encontrar el código fuente aquí:

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py