181
M
etodologías
para
el
diseño
óptimo
de
la
sectorización
de
las
redes
feld (2011), que aplicaron el algoritmo BPP a una red de suministro de agua, proponen
un procedimiento para agrupación topológica de los nodos que se puede utilizar
para diferentes propósitos, tales como mejoras en la seguridad del agua a través de
colocación de sensores en grupos o para el aislamiento eficiente de una intrusión de
contaminantes. Más específicamente, Tzatchkov
et al
. (2006a) utilizo el algoritmo BPP
para identificar los sectores independientes de una red de distribución de agua.
El algoritmo permitió la identificación de todos los posibles sectores independientes
(etapa b) empezando de cada nodo fuente en la red (correspondientes a los nodos
raíz). La aplicación del algoritmo BPP hace posible identificar una estructura nuevo
grafo de la red, que se compone de árboles y ramas, llamado
grafo del bosque de bús-
queda en profundidad
(Cormen
et al
., 1990). Con respecto a la pequeña red de la Figura
2.4.2 a, la rutina BPP, empezando de los nodos A y B (las dos fuentes de la red de agua
o raíces del grafo), localizó fácilmente dos árboles con ramas, como se ilustra en las
Figura 2.4.2 b y Figura 2.4.2 c.
c) Identificar el nivel jerárquico NJ (en inglés HL con sus siglas de hierarchical level))
del grafo que corresponde a cada fuente (nodos comunes pueden existir). Un enfoque
jerárquico (Di Battista
et al
., 1999) elegido para dibujar el grafo de árbol, en el que
todos los nodos de la red son representados por diferentes niveles con una clara je-
rarquía de conexión. En este enfoque la jerarquía se pueden identificar fácilmente, y
hay una correspondencia entre la percepción visual y el análisis de conexión de red,
posteriormente, los nodos “ancestros” y “descendientes” pueden ser definidos (Di
Battista
et al
., 1999), los cuales asignan un nivel jerárquico (NJ) específico.
Un conjunto de nodos
t
s
" ,
es un subgrafo de red que puede estar asociado con una
categoría específica, llamado un grafo de árbol, en que cada dos vértices cualquiera
en el grafo están conectados por un solo camino. Con respecto al ejemplo en la Figura
2.4.2a con
s
=2, los dos grafos de árbol,
t
1
" ,
y
t
2
" ,
, tienen 11 niveles jerárquicos (paso
c), como se ilustra en la Figura 2.4.2b y Figura 2.4.2c.
d)
Obtener los conjuntos de nodos independientes y comunes para cada NJ del grafo.
En la Fi-
gura 2.4.2 b, a partir del primer nivel del árbol
t
1
" ,
(correspondiente al nodo fuente
A), para cada nivel jerárquico, el algoritmo examina si existen nodos comunes para
el otro árbol,
t
2
" ,
(correspondiente al nodo fuente B). La Figura 2.4.3 muestra que
hasta el cuarto NJ no hay ningún nodo de conjunto
t
t
1
4
1
1
$
"
.
,
+
perteneciente al conjunto
t
t
2
4
1
1
$
"
.
,
+
, por lo tanto, él
t
1
4
$ .
+
se fija como un subconjunto de i-DH
1
,
t
2
4
$ .
+
y él se
fija como un subconjunto de i-DH
2
. A partir del quinto NJ, hay nodos que pertene-
cen a los conjuntos
t
t
t
1
1
1
4
= -
$
"
$
.
,
.
+
+
y
t
t
t
2
2
2
4
= -
$
"
$
.
,
.
+
+
; por lo tanto, es necesario
elegir cuál i-DH es mejor para la asignación de estos nodos. Hasta esta etapa de la
metodología, la simulación hidráulica de la red es innecesaria, y el grafo se trata
como un grafo no dirigido.
e) Diseñar las válvulas de seccionamiento que limitan los i-DH utilizando un procedi-
miento heurístico basado en la minimización de la potencia disipada y un algoritmo
genético. Este paso, basado en simulación hidráulica y en un procedimiento de opti-
mización, puede ser dividido en dos sub-etapas como sigue:
