¿Algoritmos para el gráfico poliédrico (gráfico plano de 3 conectados) isomorfismo?

Question

He puesto algunas investigaciones sobre el tema del isomorfismo del gráfico para los gráficos del Planar 3-Conectado, pero hay una abundancia de algoritmos de la restricción diferente, la complejidad teórica y la frecuencia de uso y estoy teniendo problemas para encontrar uno que se encuentrafuera como:

• fácil de entender
• se puede implementar con la máxima claridad
• buen desempeño práctico en gráficos pequeños (hasta vértices en las docenas)

Es difícil saberlo sin comprender los diferentes algoritmos, ya sea que esté mejor con uno de los algoritmos mayores y más especializados para este problema o los más nuevos, más generales. entre todos los candidatos posibles, ¿cuál es uno / uno es el mejor ajuste?

Answer 1

Creo que el algoritmo de Weinberg se ajusta a la factura.

• fácil de entender: calcular sistemas de rotación para g y h como subproductos de un Algoritmo de prueba de planaridad. Dado que G y H están 3-conectados, estos sistemas de rotación son isomorfos para intercambiar en el sentido de las agujas del reloj y en sentido antihorario si y solo si G y H son isomorfas. Elija un dardo (= borde con una dirección indicada) D en G y intente asignarse a todos los dardos E en H (y repetir para la otra orientación de H). Dado que G está conectado, todos los demás dardos D 'se pueden alcanzar a partir de D compensando las dos operaciones del sistema de rotación para G. Aplicar las operaciones correspondientes a E y verificar si hay isomorfismo.

• Claridad máxima: Aparte de la prueba de planaridad, la anterior es una página de código. Tal vez usted podría reutilizar la prueba de planaridad de otra persona? Hay uno en el impulso, por ejemplo. Si no, todavía creo que la implementación de su cuenta es más fácil que reescribir a Nauty.

• Buen rendimiento práctico en gráficos pequeños: después de las pruebas de planaridad, el algoritmo de Weinberg es básicamente dos travesaños de profundidad sincronizados: primeros travesaños para cada dardo. El tiempo total de funcionamiento es O (| v | ^{2 ) sin constantes grandes que acechan.}