Órbitas de matrices de adyacencia bajo verbal por matrices de la permutación.

Question

(Descargo de responsabilidad: soy nuevo aquí, así que tenga paciencia con mis errores, pero doy la bienvenida a correcciones, consejos o comentarios.)

Estoy interesado en si alguien sabe de formas de caracterización de las órbitas de una matriz de adyacencia de un multi-gráfico cuando se conjuga por una matriz de permutación. Para aclarar: Las matrices en cuestión son simétricas, con cero diagonal (a veces llamado hueco simétrica), y las entradas de todos los enteros no negativos.

La conjugación por una matriz de permutación le dará otra matriz de adyacencia con todas las mismas propiedades. Desde una cierta perspectiva, esto puede ser visualizado como volver a dibujar el gráfico que dio lugar a la matriz de adyacencia (en una manera que es isomorfo en la gráfica de la teoría del sentido).

Quiero saber si, dadas dos matrices de adyacencia con las mismas dimensiones, es posible determinar si se encuentran en la misma órbita (sin re-construcción de la necesaria permutación de matrices). Sin embargo, estoy interesado en los resultados que están relacionados con este tema, ya que creo que la respuesta es no conocida (me corrija si estoy equivocado).

Answer 1

Usted está pidiendo un algoritmo para determinar si dos multigraphs dada por las matrices de adyacencia son equivalentes. El problema de la gráfica de isomorfismo es un notorio uno en la teoría de la complejidad, ya que sólo es conocido a sentarse en algún lugar entre medio de P y NP, pero no se sabe si es P o NP.

De esto resulta claro que el problema no es fácil. El mejor programa existente para la gráfica de problemas de isomorfismo es nauty. Sin embargo, no sé si es compatible con multigraphs fuera de la caja. Hay interfaces para nauty en la Salvia y el Magma.