teoria de redes

La modelación de redes permite la resolución de múltiples problemas de programación matemática mediante la implementación de algoritmos especiales creados para tal fin, conocidos como Algoritmos de optimización de redes. Dentro de los problemas más comúnmente resueltos mediante la modelación de redes se encuentran los ya vistos modelos de transporte, transbordo además de los muy conocidosmodelos de determinación de cronograma de actividades para proyectos como lo son el PERT y el CPM.
CONCEPTOS BÁSICOS EN TEORÍA DE REDES

Gráfica: Una gráfica es una serie de puntos llamados nodos que van unidos por unas líneas llamadas ramales o arcos.



Red: Una red es una gráfica que presenta algún tipo de flujo en sus ramales. Por ejemplo una gráfica cuyo flujo en sus ramales sea laelectricidad es una red eléctrica. En las redes se usa una simbología específica para denotar su tamaño y elementos que la constituyen, dicha notación es la (N, A) donde N representa el número de nodos que contiene la red y A representa el número de arcos o ramales.
Teoría de Redes Bryan Antonio Salazar López

Cadena: Una cadena corresponde a una serie de elementos ramales que van de un nodo aotro. En el siguiente caso se resalta una cadena que va desde el nodo 1 hasta el nodo 7 y que se compone por los elementos [1-4, 4-7].



Ruta: Una ruta corresponde a los nodos que constituyen una cadena, en el siguiente caso [1, 4, 7].
Teoría de redes Bryan Antonio Salazar López

Ciclo: Un ciclo corresponde a la cadena que une a un nodo con sigo mismo, en el siguiente ejemplo el ciclo estácompuesto por la cadena [4-2, 2-5, 5-7, 7-4].
Teoría de redes Bryan Antonio Salazar López

Ramal orientado: Un ramal o arco orientado es aquel que tiene un sentido determinado, es decir que posee un nodo fuente y un nodo destino.
Teoría de Redes Bryan Antonio Salazar López

Gráfica orientada: Una gráfica orientada es aquella en la cual todos sus ramales se encuentran orientados.
Teoría deRedes Bryan Antonio Salazar López

Árbol: Un árbol es una gráfica en la cual no existen ciclos, como el siguiente ejemplo.

Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la red, de igual manera no permite la existencia de ciclos.
Teoría de Redes Bryan Antonio Salazar López

Nodo fuente: El nodo fuente es aquel nodo en el cual todos sus ramales seencuentran orientados hacia afuera.



Nodo destino: El nodo destino es aquel nodo en el cual todos sus ramales se encuentran orientados hacia él.
Teoría de Redes Bryan Antonio Salazar López
ALGORITMO DEL ÁRBOL DE EXPANSIÓN MÍNIMA

El algoritmo del árbol de expansión mínima es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta conel objetivo de que la longitud total de los arcos o ramales sea mínima (entiéndase por longitud del arco una cantidad variable según el contexto operacional de minimización, y que puede bien representar una distancia o unidad de medida).



Sean



N = {1,2,3,...,n} el conjunto de nodos de la red.

Ck= Conjunto de nodos que se han enlazado de forma permanente en la iteración k

Čk=Conjunto de nodos que hacen falta por enlazarse de forma permanente.
PASO CERO (0): CONCEPTUALIZACIÓN DEL ALGORITMO

Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no se han enlazado de forma permanente nodo alguno, y por ende el conjunto que representa a los nodos que hacen falta por enlazarse de forma permanente es igual a la cantidad de nodos que existen en la red.PASO 1:

Se debe de escoger de manera arbitraria un nodo en el conjunto Č0 llamado i el cual será el primer nodo permanente, a continuación se debe de actualizar el conjunto C1 = {i}, que significa que al tiempo en que el conjunto C1 gana el elemento i el conjunto Č0 pierde el elemento i por ende ahora será igual a Č1 = N - {i}, además se debe actualizar el subíndice de los conjuntos k, el...