EVALUACION DEL USO DE MEMORIA DE UN MÉTODO EXACTO PARA EL CONTEO DE CUBIERTAS DE ARISTAS EN GRÁFICAS

Abstract

La teoría de graficas es un campo de las ciencias computacionales y de las matemáticas, relacionada íntimamente con las ciencias experimentales, sus usos como técnica en diversas disciplinas es cada vez más extendido, incluso en las llamadas ciencias sociales. Tanto en el campo de las matemáticas como en la teoría de graficas existen problemas que han captado la atención de los investigadores durante años y que aun en nuestros días no se ha podido encontrar una solución algorítmica que pueda resolverlos adecuadamente con un uso de recursos aceptable. En el caso de la teoría de grafos hay dos grandes grupos con características y dificultades propias, por un lado los problemas NP y por otro los problemas #P, dentro de estos últimos encontramos el problema de conteo de cubiertas de aristas. El objetivo es encontrar el mínimo número de coberturas de aristas dentro de un grafo simple, es decir, encontrar el mínimo conjunto de aristas que toquen a todos los vértices del grafo. Esto se complica cada vez más mientras aumentamos el número de vértices o el grafo tiene aristas que formen parte de más de un ciclo, aumentando notablemente la complejidad y el tiempo de procesamiento requerido. Realmente hay muy pocas investigaciones que traten de resolver los problemas #P en general y el problema de conteo de cubiertas de aristas en específico, y de los pocos que lo han intentado se han decidido por un enfoque heurístico o de aproximación. Una mejor solución es a través de un método exacto, ya que aunque es más complicado de desarrollar con una complejidad algorítmica razonable, tiene muchas ventajas, entre ellas el hecho de que al conocer exactamente como es su funcionamiento es más fácil de estudiar y analizar a fondo. El algoritmo propuesto en (Hernández Servín, et al., 2014) pretender ser una solución eficaz al problema de conteo de cubiertas de aristas, al mismo tiempo que es un paso hacia adelante en el estudio de los problemas #P al ofrecer un método exacto para la solución de este problema con una complejidad algoritmo exponencial de límite inferior. Este algoritmo solo está comprobado matemáticamente a falta de una implementación que permita su comprobación práctica. Es por esto que esta Tesis de investigación tiene como fin la implementación del algoritmo y su consecuente comprobación. Con el fin de poder estudiar a fondo el comportamiento del algoritmo en cuanto a su eficacia para resolver el problema, así como de los recursos utilizados, en cuanto tiempo de ejecución y uso de memoria, de los que hace uso durante su ejecución. Para de esta forma conocer la fiabilidad el algoritmo como una solución al problema de conteo de cubiertas y definir cuáles podrían ser las siguientes líneas de investigación a seguir para llegar aún más lejos en el intento de solucionar los problemas #P.