Diferencia entre revisiones de «Isomorfismo de grafos»

73 bytes añadidos ,  hace 12 años
m
crea apartado para problema del isomorfismo de grafos
m
m (crea apartado para problema del isomorfismo de grafos)
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''.
 
LosA pesar de su diferente aspecto, los dos grafos que se muestran a continuación son isomorfos:
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
| first1 = Michael R.
| last1 = Garey
| authorlink1 =
| first2 = David S.
| last2 = Johnson
| authorlink2 =
| title = Computers and Intractability: A Guide to the Theory of NP-Completeness
| publisher = W. H. Freeman
| year = 1979
| isbn = 978-0716710455
| oclc = 11745039}}</ref>
 
Los dos grafos que se muestran a continuación son isomorfos:
 
{|class="wikitable" style="margin: 1em auto 1em auto"
<math> f(j) = 7</math>
|}
== Problema del isomorfismo de grafos ==
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
| first1 = Michael R.
| last1 = Garey
| authorlink1 =
| first2 = David S.
| last2 = Johnson
| authorlink2 =
| title = Computers and Intractability: A Guide to the Theory of NP-Completeness
| publisher = W. H. Freeman
| year = 1979
| isbn = 978-0716710455
| oclc = 11745039}}</ref>
== Referencias==
{{listaref}}
3719

ediciones