Dado el gráfico G1, G2 y G3, queremos realizar la prueba de isomorfismo F entre G1 y G2, así como entre G1 y G3. Si G2 y G3 son muy similares, de modo que G3 se forma eliminando un nodo e insertando un nodo de G2, y tenemos el resultado de F (G1, G2), ¿podemos calcular F (G1, G3) sin calcularlo desde cero? mediante la ampliación de cualquier método de vanguardia existente?
Por ejemplo, si G2 está formado por los nodos 2,3,4,5 y G3 está formado por los nodos 3,4,5,6, ¿podemos utilizar el resultado de F (G1, G2) para calcular F (G1, G3) más eficientemente?
graph-theory
graph-algorithms
graph-isomorphism
Eric Huang
fuente
fuente
Respuestas:
Esta es una simple reducción de tiempo polinomial para mostrar que el problema es GI completo : incluso si sabe quesol1, G2 son isomorfos, verificando si sol3 , construido a partir de sol2 eliminando y agregando un nodo, es isomorfo a sol1 es tan duro como el isomorfismo gráfico en sí (en el peor de los casos).
Dados dos gráficosG = ( V, E) , G′= ( V′, E′) construir
es decir, la unión de los dos gráficos más un nodo adicionaltu conectado a todos los vértices de V
recogersol2= G1 ; y claramente son isomorfos.
Ahora construyasol3 eliminando tu y agregando tu′ conectado a todos los vértices de V′ :
fuente