Diferencia entre revisiones de «Isomorfismo de grafos»
Contenido eliminado Contenido añadido
m crea apartado para problema del isomorfismo de grafos |
|||
Línea 27:
|}
== Problema del isomorfismo de grafos ==
La determinación de si dos grafos con el mismo número de vértices n y aristas son isomorfos o no se conoce como el '''problema del isomorfismo de grafos'''. Este problema
El problema del isomorfismo de grafos presenta una curiosidad en teoría de [[complejidad computacional]] al ser 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
Línea 39 ⟶ 41:
| isbn = 978-0716710455
| oclc = 11745039}}</ref>
== Referencias==
{{listaref}}
| |||