Diferencia entre revisiones de «Isomorfismo de grafos»

m
Bot: Cambiada la la plantilla: Citation; cambios triviales
(→‎Problema del isomorfismo de grafos: Hacía referencia a el número de vértices como n (el orden del grafo) pero a la hora de hacer referencia al nombre de aristas (la medida del grafo) no ponía variable alguna. Añado la m, la mas usual.)
m (Bot: Cambiada la la plantilla: Citation; cambios triviales)
! Un isomorfismo <br />entre G y H
|-
|style="padding-left:2em;padding-right:2em;"|[[ImagenArchivo:Graph isomorphism a.svg|100px]]
|style="padding-left:1em;padding-right:1em;"|[[ImagenArchivo:Graph isomorphism b.svg|210px]]
|align="center" style="background-color:white;"|<math> f(a) = 1</math>
 
La determinación de si dos grafos con el mismo número de vértices n y aristas m son isomorfos o no se conoce como el '''problema del isomorfismo de grafos'''. Este problema admite un ataque por fuerza bruta que exigiría comprobar si las n! biyecciones posibles preservan la adyacencia, pero no se conoce un algoritmo eficiente, al menos para el caso general. En este contexto, eficiencia debe interpretarse como crecimiento del número de pasos inferior a [[cota superior asintótica|O(e<sup>n</sup>)]].
 
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 (actualmente está en revisión la demostración de que el problema está en P). <ref>*{{citationObra citada
| first1 = Michael R.
| last1 = Garey
112 802

ediciones