redes

TEORIA DE REDES

Muchos problemas de optimización importantes se analizan mejor por medio de una representación gráfica o de red.

DEFINICIONES BASICAS
Una gráfica, o red se define mediante dosconjuntos de símbolos; nodos y arcos, primero se define un conjunto (llámelo v) de puntos extremos o vértices. Los vértices de una gráfica o red también se llaman nodos.
Una red consiste en unconjunto de puntos y un conjunto de líneas que unen ciertos pares de puntos. Los puntos se llaman nodos (o vértices); por ejemplo, la red de la figura 9.1 tiene siete nodos que son representados por sietecírculos. Las líneas se llaman arcos (o ligaduras, aristas o ramas); por ejemplo, la red de la figura 9.1 tiene 12 arcos que corresponden a los 12 caminos del sistema del parque. Los arcos seetiquetan al dar el nombre de los nodos en sus puntos terminales; por ejemplo, en la fi gura 9.1, AB es el arco entre los nodos A y B.



la red de la figura 9.1 tiene siete nodos que son representadospor siete círculos.

ARCO DIRIGIDO, La dirección se indica al agregar una cabeza de flecha al final de la línea que representa el arco. Cuando se etiqueta un arco dirigido con el nombre de los nodosque unen, siempre se pone primero el nodo de donde viene y después el nodo hacia dónde va, esto es, un arco dirigido del nodo A al nodo B debe etiquetarse como AB y no como BA. Otra manera deetiquetarlo es A → B.

TRAYECTORIA, entre dos nodos es una sucesión de arcos distintos que conectan estos nodos. Por ejemplo, una de las trayectorias que conectan a los nodos O y T en la fi gura 9.1 es lasucesión de arcos OB–BD–DT (O → B → D → T), y viceversa.


Para ilustrar estas definiciones, la figura 9.2 muestra una red dirigida común. (Sus nodos y arcos son los mismos que los de la fi gura3.13, donde los nodos A y B representan dos fábricas y los nodos D y E representan dos almacenes, el nodo C es un centro de distribución y los arcos representan las rutas de embarque.) La sucesión de...