Aplicaciones de la teoría de grafos: búsqueda de caminos en una red y análisis de su conectividad

Resumen

Se presentan tres algoritmos para la búsqueda de caminos orientados en un digrafo, basados en la generación de un árbol en el que se hace una búsqueda exhaustiva, en amplitud en el primer algoritmo, y en profundidad en el segundo y en el tercero. El primero permite encontrar todos los caminos óptimos entre dos vértices; el segundo permite resolver este mismo problema así como el de hallar los caminos hamiltonianos con origen en un vértice, o los ciclos de cualquier orden, en tanto que el tercero permite encontrar todos los caminos o circuitos eulerianos. Se describen, asimismo, dos algoritmos que hacen uso del mismo tipo de técnicas para el análisis de la conectividad de un grafo. El primero permite separar un grafo no conexo en sus partes conexas, y el segundo permite la detección de puentes en grafos conexos.