Introducción a la teoria de redes


Universidad Nacional Experimental de Guayana
Vicerrectorado Académico
Proyecto de Carrera Ingeniería Industrial
Catedra: Investigación de Operaciones I.
Sección:







CONCEPTO DE REDES:
Una red consiste en una serie de nodos entrelazados con arcos (o ramas). La notación para describir una red es (N, A), donde N es el conjunto de nodos y A es el conjunto de arcos. Porejemplo, la red de la figura 1 se describe como sigue:
N= {1, 2 ,3 ,4 ,5}
A= {(1,2), (1,3), (2,3), (2,5), (3,4), (3,5), (4,2), (4,5)}








Arcos o Ramas
Nodos o Redes
El análisis de redes es el área encargada de analizar las redes mediante la teoría de redes (conocida más genéricamente como teoría de grafos). Las redes pueden ser de diversos tipos: social,transporte, eléctrica, biológica, internet, información, epidemiología, etc. Los estudios realizados sobre las redes abarcan sus estructuras tales como en las redes de mundo pequeño, las redes libres de escala, los círculos sociales, medidas de centralidad. Puede ser objeto de estudio la optimización como en el caso de método de la ruta crítica, el PERT (del inglés Program Evaluation & Review Technique).TERMINOLOGÍA DE REDES
RED O GRAFO: consiste en un conjunto de puntos y un conjunto de líneas que conectan pares de puntos. Los puntos se llaman NODOS o VÉRTICES y las líneas se llaman ARCOS o ARISTAS, estos pueden tener una dirección asociada, en este caso se denominan arcos dirigidos.


FLUJO: Se denomina flujo al valor que se le asigna a un arco que conecta dos nodos. Paranombrar el arco se pone primero el nodo de donde viene y luego el nodo hacia donde va. Por ejemplo, si el flujo solo va desde el nodo C hacia el nodo D, entonces el arco se llama CD y no DC.



TRAYECTORIA: Una trayectoria entre dos nodos es una sucesion de arcos distintos que conectan estos nodos. Por ejemplo, una trayectoria que conecta al nodo A con el nodo G es AC- CE- EG.



TRAYECTORIADIRIGIDA: Una trayectoria dirigida desde el nodo I al nodo J es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo J, de manera que el flujo del nodo I al nodo J a través de esta trayectoria es factible.
TRAYECTORIA NO DIRIGIDA: Una trayectoria no dirigida del nodo I al nodo J es una sucesión de arcos cuya dirección (si la tienen) puede ser hacia o desde el nodo J.CICLO: Es una trayectoria que comienza y termina en un mismo nodo, se denomina CICLO DIRIGIDO cuando esta formado por una trayectoria dirigida y CICLO NO DIRIGIDO cuando la trayectoria que lo conforma es no dirigida.



RED CONEXA: Dos nodos se encuentran conectados si la red contiene al menos una trayectoria no dirigida entre ellos. Una red conexa es una red en la que cada par de nodos estáconectado.




CAPACIDAD DEL ARCO: Es la cantidad maxima de flujo que puede circular en un arco dirigido.El nodo que tiene la propiedad de que su flujo que sale es mayor que el flujo que entra en el se le llam NODO FUERTE (NODO ORIGEN). Por el contrario, si su flujo que sale es menor que el flujo que entra a el se le llama NODO DEMANDA (NODO DESTINO). Si el flujo que entra es igual al flujo quesale, entonces se le llama NODO DE TRASBORDO (NODO INTERMEDIO).



ARBOL: Es una serie de nodos conectados que no contiene ciclos. Un Arbol de Expansion es un arbol que conecta todos los nodos de la red (contiene n-1 arcos, donde n es el numero de nodos).



MODELOS DE REDES
1. ÁRBOL DE EXPANSIÓN MÍNIMA.
Tiene que ver con la determinación de los ramales que pueden unir todos los nodos deuna red, tal que minimice la suma de las longitudes de los ramales escogidos. No se deben incluir ciclos en la solución del problema.
Para crear el árbol de expansión mínima tiene las siguientes características:
Se tienen los nodos de una red pero no las ligaduras. En su lugar se proporcionan las ligaduras potenciales y la longitud positiva para cada una si se inserta en la red. (Las medidas...