Isomorfismo
de grafos
Dados G=(V,E) y G´=(V´,E´), se denomina
isomorfismo de G a G´ a la aplicación biyectiva f tal que para a,bÎV, {a,b}ÎE Û se cumple
{f(a),f(b)}ÎE´. Es decir, la aplicación que relaciona biyectivamente pares de
vértices de E con pares de vértices de E´, de modo que los vértices conectados
por aristas siguen estándolo.
G y G´ se denominan isomorfos, y son
matemáticamente iguales, solo varia la apariencia, o sea, que se mantienen las
adyacencias, estructura, caminos y ciclos.
Los grafos G y G ‘ son isomorfos pues
existe la biyección f: V ® V ‘ definida por f(a) = 2, f(b) = 1, f(c) = 3, f(d)
= 4 que conserva la adyacencia.
Complejidad
Los problemas matemáticos se pueden
dividir en primera instancia en dos grupos:
Problemas indecidibles: aquellos que no
se pueden resolver mediante un algoritmo.
Problemas decidibles: aquellos que cuentan al
menos con un algoritmo para su cómputo.
Sin embargo, que un problema sea
decidible no implica que se pueda encontrar su solución, pues muchos problemas
que disponen de algoritmos para su resolución son inabordables para un
computador por el elevado número de operaciones que hay que realizar para
resolverlos. Esto permite separar los problemas decidibles en dos:
intratables: aquellos para los que no es
factible obtener su solución.
tratables: aquellos para los que existe
al menos un algoritmo capaz de resolverlo en un tiempo razonable.
Los problemas pueden clasificarse también
atendiendo a su complejidad. Aquellos problemas para los que se conoce un
algoritmo polinómico que los resuelve se denominan clase P. Los algoritmos que
los resuelven son deterministas. Para otros problemas, sus mejores algoritmos
conocidos son no deterministas. Esta clase de problemas se denomina clase NP.
Por tanto, los problemas de la clase P son un subconjunto de los de la clase
NP, pues sólo cuentan con una alternativa en cada paso.
El problema de isomorfismo de grafos no
se sabe si es un problema de la clase P o de la clase NP, y si hubiese una
clase intermedia entre ambas, el isomorfismo de grafos sería el tipo de
problema ideal para ella.
Existe un caso concreto de grafos (los
árboles) donde el problema del isomorfismo si se puede resolver mediante la
aplicación de algoritmos no muy complejos. Este caso será el que
desarrollaremos en la segunda parte del proyecto, apartado
No hay comentarios.:
Publicar un comentario