Graficar isomorfismo y el grupo de automorfismo

8

Un enfoque común para decidir si dos gráficos dados son isomórficos es calcular la llamada etiqueta canónica (alternativamente, gráfico canónico) de cada gráfico y verificar si coinciden o no.

Herramientas como Nauty calculan el gráfico canónico a través de árboles de búsqueda que se podan utilizando algunas ideas inteligentes que se basan, entre otros, en los automorfismos de gráficos. Debido a esto, Nauty le permite a uno calcular un generador del grupo de automorfismo gráfico. Sin embargo, hasta donde entendí la idea detrás de Nauty, el cálculo del gráfico canónico no requiere uno para calcular un generador del grupo de automorfismo del gráfico en general.

Por lo tanto, mi pregunta es: ¿existe una relación formal de complejidad teórica entre GI y el cálculo de un grupo electrógeno del grupo de automorfismo gráfico?

Muchas gracias.

usuario88338
fuente
Podemos determinar si G y H son isomórficos a través del grupo de automorfismo GH. En el otro sentido, no estoy seguro, tal vez haya una manera simple de etiquetar canónicamente un gráfico dado su grupo de automorfismo.
Rebecca J. Stones
@ RebeccaJ.Stones, ¿es esa la misma pregunta? A menos que Wikipedia esté desactualizada, no se sabe si el isomorfismo del gráfico y la canonicalización del gráfico son equivalentes al tiempo polinomial, por lo que no creo que un algoritmo para etiquetar canónicamente un gráfico del grupo de automorfismo le diga algo útil sobre la relación entre la computación El grupo y GI.
Peter Taylor

Respuestas:

2

Como sugieren los comentarios, puede haber confusión sobre lo que llamas "GI". Pero la idea aquí es correcta. Es equivalente al tiempo polinomial encontrar generadores de un grupo de automorfismo como lo es encontrar un isomorfismo entre dos grupos. La idea es "clásica" en el sentido de que aparece en trabajos tempranos como el isomorfismo grupal de Luks en valencia limitada en tiempo polinómico, e incluso allí creo que la idea se consideró "conocida".

Reclamación. DejarG y Hestar conectado gráficos. EntoncesGH si, y solo si, cada grupo electrógeno S de Aut(GH) contiene un elemento gS tal que Gg=H.

Observación Importante aquí es que cada grupo electrógeno intercambia los gráficos ya que de lo contrario a veces se calculan generadores que no resuelven el problema. Entonces, por ejemplo, el isomorfismo de dos grupos no cede tan fácilmente de esta manera. Eso es porque no todos los conjuntos generadores deAut(G×H) intercambiará G y H cuando GH. en cambio, pueden ir a copias diagonales. Esa situación se puede solucionar, pero requiere un argumento más fuerte. Entonces, el enfoque aquí no se aplica en todas las categorías.

Prueba. Por el contrario si cada (o incluso si uno) conjunto generador deAut(GH) intercambios G y H entonces GH por la restricción de esa función a G. Así que esto se trata de la dirección hacia adelante. (Pero menciono esto porque la prueba es por contrapositivo, por lo que puede parecer que estoy a punto de ir en la misma dirección).

Suponer Aut(GH) es generado por un conjunto S todos cuyos elementos envían G a Gy H a H, (observe por suposición de conectividad si un vértice de G se envía a un vértice de H entonces todo el gráfico G es enviado a H y así por paloma algún vértice en H será enviado a G y entonces |G|=|H|y habremos intercambiado los dos gráficos). Ya queS envía G a G, entonces cada composición de funciones en S envía G a G, y también lo hacen los inversos de estas funciones. Entonces cada palabra enS envía G a G (y también H a H) Entonces, ningún elemento deAut(GH) intercambios G y H.

Finalmente si GH entonces un isomorfismo ϕ:GH ofrece un automorfismo ϕϕ1 de GH. Entonces la ausencia de elementos enAut(GH) intercambiar G y H implica GH. El resultado sigue.

Pero ahora el punto a tener en cuenta es que ir de la decisión (es GH?) para buscar (Dame ϕ:GH o un certificado que GH) todavía tiene que ser discutido (y puede serlo). También desde un isomorfismo hasta generadores de automorfismos hay otro argumento (individualice los gráficos y repita la prueba de isomorfismo). Entonces, todos dijeron que tienes un par de páginas de argumentos para hacer estas equivalencias. Sin embargo, ninguno mostrará el etiquetado canónico. Eso es mucho más difícil (NP-duro si no recuerdo mal). Aunque NAutY y Traces manejan muchos ejemplos rápidamente.

Algeboy
fuente