Diferencia entre revisiones de «Isomorfismo de grafos»
Contenido eliminado Contenido añadido
mSin resumen de edición |
m enlazo a "isomorfismo" en general |
||
Línea 1:
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 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.
| |||