Diferencia entre revisiones de «Isomorfismo de grafos»

277 bytes añadidos ,  hace 12 años
m (crea apartado para problema del isomorfismo de grafos)
|}
== 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 esadmite unaun curiosidadataque en teoría de [[complejidadpor computacional]]fuerza yabruta que esexigiría unocomprobar desi loslas pocosn! problemasbiyecciones citadosposibles porpreservan Gareyla y Johnson en 1979 pertenecientes a [[NP (Complejidad computacional)|NP]]adyacencia, depero los queno se desconoceconoce siun esalgoritmo resolubleeficiente, enal tiempomenos polinómicopara oel sicaso es NP-completogeneral.<ref>*{{citation
 
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
| isbn = 978-0716710455
| oclc = 11745039}}</ref>
 
== Referencias==
{{listaref}}
3719

ediciones