grafinhos

APLICACIONES DE LA TEORÍA DE GRAFOS:
BÚSQUEDA DE CAMINOS EN UNA RED Y
ANÁLISIS DE SU CONECTIVIDAD
(APPLICATIONS OF THE GRAPH THEORY: SEARCH FOR PATHS IN A NETWORK AND
ANALYSIS OF THEIR CONNECTIVITY)

A l f o n s o R e c u e r o , Dr. ingeniero de Caminos
Instituto Eduardo Torroja/CSIC

Fecha de recepción: 14 - X - 94

ESPAÑA

403-16

RESUMEN

SUMMARY

Se presentan tresalgoritmos 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 hamiltonianoscon
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 engrafos conexos.

This article presents three algorhitms for the search of oriented
paths in a digraph, based on the generation of a tree in which
an exhaustive search is performed—breadth—first in the first
one and depth-first in the second and third ones. The first one
allows us to find the optimum paths between two vertices, the
second permits the solution of the same problem and also findsthe Hamiltonian paths beginning in one vertex or the cycles of
any length, while the third one allows us to find all the paths
or the Eulerian circuits. The article also describes two
algorhitms that use the same type of techniques for the analysis
of the connectivity of a graph. The first one permits the
division of a non-connective graph into its connective parts
while the second onepermits the detection of bridges in
connective graphs.

1. Introducción

admitiendo la existencia de bucles (arcos que unen
a un vértice consigo mismo), en tanto que en un
grafo sólo puede haber un arco entre dos vértices,
los cuales han de ser distintos.

Considérese una red formada por un conjunto de N
vértices, identificados por los números de 1 a N,
conectados entre sí, bien porarcos orientados, cada
uno de ellos con un valor de recorrido (digrafo), o
por arcos bidireccionales (grafo). En un digrafo, dos
vértices pueden estar conectados mediante uno o
dos arcos, esto es, en u n o o a m b o s sentidos,
pudiendo ser distintos sus valores de recorrido,

(c) Consejo Superior de Investigaciones Científicas
Licencia Creative Commons 3.0 España (by-nc)

Llamaremos ordenal número de vértices, y tamaño
al número de arcos.
Dos vértices conectados por un arco, o dos arcos con
un extremo común, diremos que son adyacentes.

http://informesdelaconstruccion.revistas.csic.es

34
Informes de la Construcción, Vol. 46, n.° 433, septiembre/octubre 1994

El grafo asociado a un digrafo es el resultante de
transformar todos los arcos de éste en bidireccionales,suprimiendo los arcos duplicados y los que
conectan un vértice consigo mismo.
Vamos a describir cuatro problemas clásicos de búsqueda de caminos orientados en digrafos, teniendo
en cuenta el sentido de recorrido de los arcos, y
dos sobre la conectividad en grafos, presentando
para todos ellos algoritmos basados en la construcción de un árbol, que proporcionan soluciones eficaces a los mismos.Los grafos constituyen una herramienta de gran utilidad en la resolución de numerosos problemas en
una gran variedad de áreas. Por citar sólo algunas
de ellas mencionaremos: flujos en redes, árboles
genealógicos, distribución de espacios arquitectónicos, emparejamientos, programación de actividades,
análisis de estructura, resultados de torneos, coloreado de mapas, coloreado de análisis...