Algoritmos en Gráficas: Árboles de Expansión Mínima y Caminos Cortos

Abstract

El objetivo de esta tesis es el estudio detallado del diseño de cuatro algoritmos para gráficas, los primeros dos serán para el estudio del problema del árbol de expansión mínima en una gráfica no dirigida y los otros dos para el problema de caminos cortos con origen fijo en una gráfica dirigida, los cuales al ser aplicados a una gráfica, nos producirán ya sea un árbol de expansión mínima o un árbol de caminos cortos, según sea el caso. Para poder resolver este tipo de problemas con gráficas de manera eficiente, es necesario analizar y recorrer todos los vértices de la gráfica de manera sistemática.