Redes de grafos

Scientia et Technica Año XI, No 27, Abril 2005. UTP. ISSN 0122-1701

33

IMPLEMENTACIÓN DE ALGORITMOS DE RECORRIDO DE GRAFOS PARA EL CÁLCULO DE LA REGULACIÓN EN REDES DE DISTRIBUCIÓN RADIALES
RESUMEN Este documento presenta una metodología para el cálculo de la regulación en redes de distribución radiales utilizando técnicas heurísticas para recorrido de grafos como son búsqueda en anchura oBFS (Breadth First Search) y búsqueda en profundidad o DFS (Depth First Search). PALABRAS CLAVES: Grafos, DFS, BFS, regulación, momento eléctrico. ABSTRACT This document presents a methodology for regulation calculus in radial distribution networks using heuristic techniques for traversing a graph like BFS (Breadth First Search) and DFS (Depth First Search). KEYWORDS: Graph, DFS, BFS, regulation,electric moment. ADOLFO LEON ESCOBAR Ingeniero Electricista Profesor Titular Universidad Tecnológica de Pereira adolfo@ohm.utp.edu.co Grupo de investigación en Planeamiento de Sistemas Eléctricos. EDUARDO GIRALDO SUÁREZ Ingeniero Electricista Universidad Tecnológica de Pereira egiraldos@ohm.utp.edu.co Grupo de investigación en Control e Instrumentación.

1. INTRODUCCIÓN Las técnicas heurísticaspara recorrido de grafos han sido utilizadas en muchas aplicaciones como la solución de circuitos eléctricos, en la exploración de entornos en robótica móvil, en el control de información en redes informáticas, entre otras [1]. Esto se debe a que todos los sistemas mencionados pueden ser modelados como grafos. Esto también es aplicable en el caso de las redes de distribución, donde cada nodo enla red de distribución es un nodo del grafo, y cada línea entre los nodos de la red de distribución, es un arco en el grafo. Para este caso se consideraron redes radiales, que son las más comunes en las redes de distribución, por lo que en los grafos no se obtenían trayectorias cerradas. Para el recorrido de grafos se pueden emplear técnicas heurísticas como son búsqueda en anchura o BFS (BreadthFirst Search) y búsqueda en profundidad o DFS (Depth First Search). Estas técnicas de recorrido permiten efectuar los cálculos necesarios para realizar los flujos de carga, cálculo de momentos eléctricos, regulación, etc. progresivamente. En este artículo se presentará la implementación de estas técnicas heurísticas (BFS, y DFS) para el cálculo de la regulación en una red de distribución radial. 2.MARCO TEÓRICO Antes de mostrar cómo fueron implementados estos algoritmos es necesario explicar su funcionamiento. 2.1 Algoritmo BFS El algoritmo de recorrido en anchura o BFS, explora sistemáticamente todas las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices más cercanos a un nodo inicial [2].
Fecha de Recepción: 31 Enero 2005 Fecha de Aceptación: 01 Marzo de2005

En la figura 1, se presenta la secuencia seguida para recorrer todos los nodos utilizando un algoritmo BFS.

Figura 1. Secuencia seguida por el algoritmo BFS para recorrer todo el grafo.

34 Para la implementación de este algoritmo se utiliza globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el recorrido. El algoritmo BFS requiere también unvector de cola auxiliar para gestionar los vértices no visitados [3]. En muchos casos es necesario ejecutar este algoritmo empezando en los nodos más alejados del nodo escogido como nodo inicial. 2.2 Algoritmo DFS El algoritmo de recorrido en profundidad o DFS, explora sistemáticamente las ramas o aristas del grafo de manera que primero se visitan los nodos o vértices adyacentes a los visitadosmás recientemente. De esta forma se va “profundizando” en el grafo, es decir, alejándose progresivamente del nodo inicial [2]. Esta estrategia admite una implementación simple en forma recursiva, utilizando globalmente un contador y un vector de enteros para marcar los vértices ya visitados y almacenar el orden del recorrido [3]. En la figura 2, se presenta la secuencia seguida para recorrer...