180
A
vances
en
la
hidráulica
de
redes
de
distribución
de
agua
potable
a) Definir un grafo simple (original) de una red de agua. El primer paso consiste en
la definición de un grafo simple de la red de agua
G=(V,A)
,
por medio de la matriz
de adyacencia G=(V,A), donde
V
es el conjunto finito de vértices (o nodos) y
A
es el
conjunto de aristas (o tuberías).
b) Buscar los sectores independientes, usando un algoritmo de
búsqueda primero en pro-
fundidad
(
BPP
) (en inglés
Depth First Search
o
DFS
). Esta fase se basa en algoritmos de
la teoría de grafos que generalmente son más eficientes que los algoritmos basados
en álgebra lineal sobre las matrices topológicas en términos de velocidad de cálculo
y memoria (Giustolisi
et al
. 2008a, Giustolisi y Savic 2010). El algoritmo de la teoría de
grafos que se utilizó, conocido como búsqueda en profundidad, fue propuesto por
Tarjan (1972) y permite la exploración de la conectividad de un grafo. El algoritmo
BPP comienza en algún nodo y explora cada ruta alejándose tanto como sea posible
del nodo inicial (en “profundidad”) hasta que no hay más nodos adyacentes no visi-
tados antes de iniciar un nuevo camino. Este algoritmo es diferente del algoritmo de
búsqueda primero en amplitud
(con sus siglas en inglés BFS, de
breadth first search
) (Pohl,
1969), que inicia en un nudo raíz y explora primero todos los nodos adyacentes (en
“amplitud”) hasta que no haya más nodos adyacentes no visitados. Perelman y Ost-
7
8
9
14
10
13
12
11
5
6
4
1
2
3
A
B
7
7
8
8
9
9
14
14
10
10
13
13
12
12
11
11
5
5
6
6
4
4
1
1
2
2
3
3
A
B
NJ=1
NJ=2
NJ=3
NJ=4
NJ=5
NJ=6
NJ=7
NJ=8
NJ=9
NJ=10
NJ=11
NJ=1
Nivel Jerárquico
a)
b)
c)
Nivel Jerárquico
NJ=2
NJ=3
NJ=4
NJ=5
NJ=6
NJ=7
NJ=8
NJ=9
NJ=10
NJ=11
Figura 2.4.2 Red hidráulica propuesta.
