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

10.3989/ic.1994.v46.i433.1115

1988-3234

A. Recuero,

Limits and Structures in Graph Theory

RESUMENSe 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