Graph theory based single and multiple source water distribution network partitioning / Sectorización basada en la teoría de los grafos de redes de distribución de agua potable con una y con múltiples fuentes



Palabras clave:

district metering areas, graph algorithms, graph partitioning, hierarchical graph tree, sectorization, water distribution networks


A graph theory based methodology for design of water network partitioning is proposed. Both multiple and single source networks are considered. In the first case the partition refers to the definition of isolated sectors, each of them supplied by its own sources. The shortest paths from each water source to each network node are found and each network node is assigned to be supplied exclusively by the source with the shortest path distance to it. The pipes to be closed are the edge separators of such partition. In the second case the partitioning problem refers to a division of the network in relatively small district metering areas (DMAs) each of them fed by a single pipe. A hierarchical tree for the graph is constructed using a breadth-first search. A recursive approach is applied on this tree to find the design flow rates in each pipe summing the demand of descendant nodes. Based on these flow rates the nodes belonging to each DMA are found. The pipes to be closed are defined as the chords between branches of the hierarchical tree lying below the feeding pipe. The procedure has been tested on a real medium city all-pipe water distribution network model.