modelo de redes


















Introducción



La  representación  gráca  de  las  vías  de  comunicación  de  cualquier  región 
geográca es un claro ejemplo de una red, lo cual le conere relevancia natural 
por tener la capacidad de proporcionarnos información acerca de los diferentes caminos que podemos utilizar para trasladarnos de un origen hasta un destino preestablecido pero, en general, esnecesario obtener aún más información de un diagrama de redes, como encontrar cuál de todas las posibles rutas es la que tiene un recorrido total menor a cualquier otra, es decir, la ruta más corta de todas o,
por ejemplo, cuál es la ruta con mayor auencia o ujo máximo, así como el ujo
de costo mínimo. Se puede observar que el denominador común de los términos recién presentados como: “más corta” y“mínimo o máximo”, tiene una relación
directa con la optimización. Es en este sentido que se presenta tanto la denición 
de los modelos de redes, su terminología y construcción, así como casos prácticos para resolver con la metodología presentada a lo largo de este capítulo.


En las diferentes secciones del capítulo se estudiarán los problemas mencionados a través de la solución de casos deaplicación, por lo que se sugiere que el lector resuelva de nueva cuenta tales ejemplos, así como la sección de ejercicios y la autoevaluación.


6.1.  Denición del modelo

En general, una red es la representación gráca de un proceso, serie de actividades 
interconectadas o la distribución de puntos geográcos especícos, por ejemplo, 
un mapa carretero o la distribución de una red de computadorasrepresentada en un diagrama, aunque existen muchos más contextos donde se aplican las redes.

Por  mostrar  una  representación  de  la  realidad,  las  redes  se  clasican  como  un 
modelo. Es así como se dene el modelo de redes, el cual cuenta con terminología 
propia, necesaria para su desarrollo. A continuación se presenta la notación y terminología empleada.






Notación y terminología


Red.Conjunto de puntos llamados nodos (o vértices) y líneas que los unen llamadas arcos (o ligaduras, aristas o ramas).

Los arcos se etiquetan con los nombres de los nodos en sus puntos terminales, por ejemplo, AB es el arco entre los nodos A y B.

Arcos dirigidos. Un arco es dirigido cuando tiene ujo en una sola dirección y ésta se indica con una cabeza de echa al nal del arco o línea en la dirección del 
ujo.

Arcos no dirigidos. Un arco donde se permite el ujo en ambas direcciones.


Trayectoria. Sucesión de arcos distintos que conectan dos nodos.


Trayectoria dirigida. Una trayectoria dirigida del 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 ujo del 
nodo i al nodo j, a través de esta trayectoria, es factible.

Trayectoria no dirigida. Una trayectoria nodirigida 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.


Red dirigida. Es una red que tiene sólo arcos dirigidos.


Red no dirigida. Es una red donde todos sus arcos son no dirigidos.


Red conexa. Una red conexa es una red en la que cada par de nodos está conectado. Se dice que dos nodos están conectados si la red contiene al menosuna trayectoria no dirigida entre ellos aparte.


Se debe resaltar que no es necesario que la trayectoria sea dirigida aun cuando la red sea dirigida.

Capacidad de arco. Es la cantidad máxima de ujo (quizás innito) que puede 
circular en un arco dirigido.

Nodo fuente (o nodo de origen). Tiene la propiedad de que el ujo que sale del 
nodo excede al ujo que entra a él. 


Nodo demanda (o nododestino). Es el caso contrario al nodo fuente, donde el
ujo que llega excede al que sale de él. 






Nodo de trasbordo  (o  nodo  intermedio).  Satisface  la  conservación  del  ujo,  es 
decir, el ujo que entra es igual al que sale.


Esta terminología se utilizará en el desarrollo del algoritmo y ejemplos. Conforme se requiera, se recuperará alguno...