MODELO DE REDES

MODELO DE REDES

RUTA MAS CORTA

¿En que consiste?

El problema de la ruta más corta incluye un juego de nodos conectados donde sólo un nodo es considerado como el origen y sólo un nodo es considerado como el nodo destino. El objetivo es determinar un camino de conexiones que minimizan la distancia total del origen al destino.

Se trata de encontrar la ruta de menor distancia, o costo, a entre el punto de partida o nodo inicial y el destino o nodo terminal.

Ejemplo:

 -Se tienen n nodos, partiendo del nodo inicial 1 y terminando en el nodo final n.

 -Arcos bi-direccionales conectan los nodos con distancias mayores que cero.

 -Se desea encontrar la ruta de mínima distancia que conecta el nodo 1 con el nodo n.

 Por medio de la aplicación del algoritmo de este problema podemos conocer la menor distancia entre un nodo origen y un nodo destino.

Procedimiento:

1. Elaborar un cuadro con todos los nodos y los ramales que salen de él.

2. Partiendo del origen, debemos encontrar el nodo más cercano a él.

3. Anular todos los ramales que entren al nodo más cercano elegido.

4. Comenzando en el origen se debe encontrar el nodo más cercano a él, por intermedio del(los) nodo(s) ya elegido(s) y volver al tercer paso hasta llegar al destino

FLUJO MAXIMO

Flujo máximo en redes

En teoria de grafos, un grafo dirigido con pesos es tambien conocido como una red.En

los problemas de flujo en redes, las aristas representan canales por los que puede

circular cierta cosa: datos, agua, coches, corriente electrica, etc. Los pesos de las

aristas representan la capacidad maxima de un canal: velocidad de una conexion,

volumen maximo de agua, cantidad maxima de trafico, voltaje de una lınea electrica,

etc.; aunque es posible que la cantidad real de flujo sea menor.Un posible algoritmo

para calcular el flujo máximo La idea de los flujos, que van desde s hasta t, es muy

proxima a la de un camino por el que circula cierto fluido. Cada unidad de flujo que

llega hasta un nodo, debe salir por alguna de sus aristas. Por lo tanto, un posible

algoritmo podrıa basarse en encontrar caminos (s, v1, v2, ..., vk, t) en G. Por ese

camino podemos mandar cierta cantidad de flujo.¿Cuanto? Pues todo lo que quepa.

Por ejemplo, si en el grafo G de la figura 5.33 tomamos el camino (s, a, b, t), vemos que

las aristas por las que pasa tienen pesos: 5, 2, 4. El m´aximo flujo que podemos mandar

por ese camino esta limitado por el m´ınimo de las capacidades por las que pasa el

...