Me gustaría preguntar si hay un resultado ya publicado sobre eso:
Tomamos todos los caminos diferentes posibles entre cada par de nodos de dos gráficos regulares conectados (con el grado , digamos, y el número de nodos n ) y escribimos sus longitudes. Por supuesto, este número de caminos distintos es exponencial. Mi pregunta es, si clasificamos las longitudes y las comparamos (las listas obtenidas por los dos gráficos) y son exactamente iguales, ¿podemos decir que los dos gráficos son isomórficos?
Por supuesto, incluso si este es un resultado, no podemos usarlo para responder al isomorfismo gráfico, ya que el número de caminos distintos es exponencial, como se dijo
Por rutas distintas , me refiero a rutas que tienen al menos un nodo diferente, obviamente.
Gracias a priori por su ayuda.
Respuestas:
Creo que la respuesta a su pregunta es "no" porque una condición equivalente implicaría una solución de tiempo polinomial a IG.
Para , la matriz de adyacencia del gráfico G , tenga en cuenta que el número de trayectos desde i hasta j de longitud k es ( A k ) i , j (con la repetición de vértices y aristas permitidas). Para dos gráficos G 1 y G 2 (con matrices de adyacencia A 1 y A 2 ) y k ≥ 1 , si clasificó los elementos de A k 1 y A k 2, entonces paraUNA sol yo j k ( Ak)i , j sol1 sol2 UNA1 UNA2 k ≥ 1 Ak1 Ak2 para ser isomorfo a G 2 , es una condición necesaria que las listas sean idénticas para todos los k .G1 G2 k
Creo que tu conjetura es equivalente a:
Si las listas ordenadas de elementos de y A d 2 son idénticas para k = 1 a n - 1 (en el camino más largo con vértices no repetidos), entonces G 1 y G 2 son isomórficos.Ak1 Ad2 k=1 n−1 G1 G2
Entonces, para resolver IG, uno solo tiene que realizar multiplicaciones de n × n matrices (y un poco de tiempo extra para ordenar y comparar n 2 elementos). Esto llevaría menos de n 4 veces.n−1 n×n n2 n4
Admito dos posibles fallas en mi argumento. Primero, es totalmente posible que GI tenga un algoritmo de tiempo polinómico y que lo hayamos descubierto juntos, justo ahora (¡hurra, somos famosos!). Esto me parece altamente improbable. En segundo lugar (y mucho más probable), lo que he propuesto no es realmente equivalente a su conjetura.
Pensamiento final. ¿Has probado esto para todos, digamos, gráficos de 3 regulares para el tamaño 8 más o menos? Creo que si su conjetura es falsa, debería haber un contraejemplo en gráficos 3-regulares de tamaño bastante pequeño.
fuente
Como solo está comparando las longitudes de las rutas (y mientras tanto olvidando a qué par de nodos corresponden si lo entendí bien), creo que gráficos muy similares deberían proporcionar un contraejemplo: al final solo está contando el número de caminos de una longitud fija e independientemente de los vértices que unen. Por ejemplo, creo que estos gráficos son un contraejemplo: http://www.mathe2.uni-bayreuth.de/markus/REGGRAPHS/GIF/06_3_3-2.gif y http://www.mathe2.uni-bayreuth.de/ markus / REGGRAPHS / GIF / 06_3_3-1.gif
Si no me equivoco (contar las rutas es tedioso), ambas tienen 9 rutas de longitud 1, 18 rutas de longitud 2, 48 rutas de longitud 3, 30 rutas de longitud 4 y 36 rutas de longitud 5
fuente
fuente