Diferencia entre revisiones de «Isomorfismo de grafos»

8 bytes añadidos ,  hace 12 años
m
sin resumen de edición
(añade referencia)
m
En [[teoría de grafos]], un '''[[isomorfismo]]''' entre dos [[grafo]]s ''G'' y ''H'' es una [[biyección]] ''f'' entre los conjuntos de sus vértices <math> f: V(G) \rightarrow V(H) </math> que preserva la relación de adyacencia. Es decir, cualquier par de vértices ''u'' y ''v'' de ''G'' son adyacentes si y solo si lo son sus imágenes, ''f(u)'' y ''f(v)'', en ''H''.
 
La determinación de si dos grafos son isomorfos o no se conoce como el '''problema del isomorfismo de grafos'''. Este problema es una curiosidad en teoría de [[complejidad computacional]] ya que es uno de los pocos problemas citados por Garey y Johnson en 1979 pertenecientes a [[NP (Complejidad computacional)|NP]], de los que se desconoce si es resoluble en tiempo polinómico o si es NP-completo.<ref>*{{citation
3719

ediciones