Resumen:
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.
Descripción:
De acuerdo a los resultados obtenidos, hay varias cosas que se pueden mencionar del funcionamiento del algoritmo, una de las más evidentes desde las primeras fases es que el tiempo de ejecución y el uso de memoria comparten el mismo comportamiento, esto quiere decir que si uno crece exponencialmente el otro también lo hará.
El hecho de que el algoritmo funcione de forma lineal en las gráficas cactus indica que el número de vértices o aristas de la gráfica no es determinante, sino, que lo que realmente incrementa su complejidad de análisis y por lo tanto el uso de
recursos del algoritmo de forma significativa es el número de ciclos intersectados.
Un claro ejemplo de esto se puede observar cuando una gráfica cactus de más de 500 vértices tiene un tiempo de ejecución mucho menor a la una gráfica completa de 9x9, y esta idea se refuerza al no encontrar un patrón de crecimiento si solo nos fijamos en el número de vértices o aristas, el factor que define que tan grande o pequeño es el tiempo de ejecución sobre una gráfica es la cantidad de ciclos intersectados.
Obviamente esto no quiere decir que no afecte en nada el número de vértices y aristas, una entrada grande tardara más en procesarse que una pequeña, pero este factor no es tan determinante, en otras palabras un aumento en el número de
ciclos intersectados origina un incremento exponencial, mientras un incremento en el número de vértices y aristas origina un incremento lineal, siempre y cuando ese aumento no origine más ciclos intersectados.
Esto es producto de que el algoritmo de conteo tenga un tiempo polinómico de ejecución y el algoritmo para procesar los algoritmos con ciclos intersectados tenga un tiempo de tiempo de un límite exponencial bajo, por lo tanto un incremento en los procesos que debe hacer uno u otro refleja su respectivo
incremento.
El hecho de que el algoritmo mantenga su funcionamiento constante y cumpla con lo esperado permite decir que se pueda generar una ecuación característica de crecimiento que permite deducir los valores que se obtendrán con ejemplos que
sería muy tardado de procesar, estas se encuentran junto a las gráficas que representan los diferentes crecimientos tanto en tiempo como uso de memoria.
Todas estas características de la implementación hacen que su aplicación para resolver el problema de conteo de cubiertas sea eficaz al ofrecer un algoritmo exacto con una complejidad de límite exponencial inferior, la cual sin embargo no
llega a ser una solución completamente optima, ya que no reduce la complejidad al ideal polinómico.