Publicación:

Restricciones planares de problemas duros un estudio de caso

Resumen

Los grafos son estructuras matemáticas útiles en labores de modelado dentro de diversas áreas del conocimiento. En particular, el isomorfismo de grafos brinda la posibilidad de extender propiedades de interés, que se sabe presentes en un grafo, a otro, gracias a la existencia de una función denominada de isomorfismo que a cada vértice de un grafo le asigna como imagen un vértice en el otro grafo de modo tal que la relación de adyacencia es preservada. Dados dos grafos, saber si son isomorfos (problema del isomorfismo de grafos) es un problema que a día de hoy no puede ser resuelto por una máquina determinista en tiempo polinomial. Sin embargo, es sabido que clases específicas como la que agrupa a los grafos planos puede ser solucionada de manera eficiente. En este proyecto se estudia el problema del isomorfismo de grafos centrando la atención, particularmente, en su complejidad computacional y en la versión del problema restringida a grafos planos. También es estudiado un algoritmo que puede ser implementado capaz de, dados dos grafos planos como entrada, decidir si los grafos del input son isomorfos en un tiempo . La metodología utilizada por el algoritmo consiste en la generación de un código único que identifica cada grafo de modo tal que dos grafos serán isomorfos si y solo si dichos códigos son iguales.