Portal de Periódicos da CAPES

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

1994; Spanish National Research Council; Volume: 46; Issue: 433 Linguagem: Espanhol

1988-3234

Antonio Recuero Fornies,

Advanced Graph Theory Research

Se presentan tres algoritmos para la busqueda de caminos orientados en un digrafo, basados en la generacion de un arbol en el que se hace una busqueda exhaustiva, en amplitud en el primer algoritmo, y en profundidad en el segundo y en el tercero. El primero permite encontrar todos los caminos optimos entre dos vertices; el segundo permite resolver este mismo problema asi como el de hallar los caminos hamiltonianos con origen en un vertice, 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 tecnicas para el analisis de la conectividad de un grafo. El primero permite separar un grafo no conexo en sus partes conexas, y el segundo permite la deteccion de puentes en grafos conexos.