Red de flujoDe Wikipedia, la enciclopedia libre

Saltar a navegación, búsqueda

Entendiendo una red de flujo como un grafo dirigido, donde la fuente es quien produce o inicia el traspaso de algún material o producto por los arcos, estos últimos, vistos como caminos o conductos y tomando en cuenta la ley de corrientes de Kirchoff, donde, la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos saliendo del vértice.

[editar] Descripción matemáticaUna red de flujo es un grafo dirigido G = (V,E) en donde cada arco (u,v) E tiene una capacidad no negativa c(u,v) 0.

Se distinguen dos vértices: la fuente s y el destino t.

Se asume que cada vértice se encuentra en alguna ruta de s a t.

Un flujo en G es una función tal que

Restricción de capacidad:

Simetría: Conservación:

El valor del flujo es

El problema del flujo máximo trata de maximizar este flujo.

Descripción matemática =

Una red de flujo es un [[Grafo#Grafo_dirigido|grafo dirigido]] <math>G = (V,E)</math> en donde cada arco (u,v) E tiene una capacidad no negativa c(u,v) 0.

Se distinguen dos vértices: la fuente '''s''' y el destino '''t'''.

Se asume que cada vértice se encuentra en alguna ruta de '''s''' a '''t'''.

Un flujo en G es una [[Función matemática|función]] <math>f: VxV \mapsto R</math> tal que

*Restricción de capacidad: <math>\forall \quad u,v \in V,\quad f(u,v) \le c(u,v)</math>

*Simetría: <math>f(u,v) = - f(v,u) \,</math>

*Conservación: <math>\forall u \in V - \left \{ s,t \right \} \quad \sum_{v \in V} f(u,v) = 0 </math>

El valor del flujo es <math>|f| = \sum_{v \in V}f(s,v)</math>

El problema del flujo máximo trata de maximizar este flujo.

[editar] Problemas de Redes de Flujo= PROBLEMAS DE REDES DE FLUJO =

== ALGORITMO DE FLUJO MAXIMAL ==

TENEMOS EL CONOCIDO PROBLEMA DE FLUJO MÁXIMO: ¿CUÁL ES LA TASA MAYOR A LA CUAL EL MATERIAL PUEDE SER TRANSPORTADO DE LA FUENTE AL RESUMIDERO SIN VIOLAR NINGUNA RESTRICCIÓN DE CAPACIDAD?

EN OTRAS PALABRAS, EL PROBLEMA CONSISTE EN DETERMINAR LA MÁXIMA CAPACIDAD DE FLUJO QUE PUEDE INGRESAR A TRAVÉS DE LA FUENTE Y SALIR POR EL NODO DE DESTINO.

EL PROCEDIMIENTO PARA OBTENER EL FLUJO MAXIMAL DE UNA RED, CONSISTE EN SELECCIONAR REPETIDAS VECES CUALQUIER TRAYECTORIA DE LA FUENTE AL DESTINO Y ASIGNAR EL FLUJO MÁXIMO POSIBLE EN ESA TRAYECTORIA.

:'''CAPACIDAD RESIDUAL''': ES LA CAPACIDAD ADICIONAL DE FLUJO QUE UN ARCO PUEDE LLEVAR: :<MATH>C_{F}(U,V)= C(U,V) - F(U,V) \,</MATH>

*DADA UNA [[RED DE FLUJO]] MAXIMAL, PLANTEE LA RED RESIDUAL ASOCIADA.

*ENCUENTRE LA [[TRAYECTORIA]] DE LA [[FUENTE]] AL DESTINO CON CAPACIDAD DE [[FLUJO]] ESTRICTAMENTE POSITIVO (SI NO EXISTE ALGUNO, ES POR QUE SE HA ENCONTRADO EL ÓPTIMO).

*EXAMINE ESTAS [[TRAYECTORIA]]S PARA ENCONTRAR LA RAMA O ARCO CON LA MENOR CAPACIDAD DE FLUJO RESTANTE E INCREMENTE EN ÉSTE VALOR, LA CAPACIDAD DEL FLUJO EN SENTIDO CONTRARIO.

*DETERMINE TODAS LAS TRAYECTORIAS ESTRICTAMENTE POSITIVAS, HASTA QUE NO SE PERMITA FLUJO DEL NODO A UN NODO DESTINO.

PODEMOS, MEDIANTE EL [[ALGORITMO DE FORD-FULKERSON]], ENCONTRAR EL FLUJO MÁXIMO DE UNA RED.

{{ESBOZO DE|MATEMÁTICA}}[[CATEGORÍA:TEORÍA DE GRAFOS]][[CATEGORÍA:INVESTIGACIÓN OPERATIVA]]

[[CS:TOK V SÍTI]][[DE: FLÜSSE UND SCHNITTE IN NETZWERKEN]][[EN:NETWORK FLOW]][[HE: זרימה רשת ]][[TH:การไหลในเคร�อข่�าย]][[VI:LUỒNG TRÊN MẠNG]]

[EDITAR] ALGORITMO DE FLUJO MAXIMAL

Tenemos el conocido Problema de flujo máximo: ¿Cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al resumidero sin violar ninguna restricción de capacidad?

En otras palabras, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.

El procedimiento para obtener el flujo maximal de una red, consiste en seleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.

CAPACIDAD RESIDUAL: ES LA CAPACIDAD ADICIONAL DE FLUJO QUE UN ARCO PUEDE LLEVAR:

DADA UNA RED DE FLUJO MAXIMAL, PLANTEE LA RED RESIDUAL ASOCIADA.

ENCUENTRE LA TRAYECTORIA DE LA FUENTE AL DESTINO CON CAPACIDAD DE FLUJO ESTRICTAMENTE POSITIVO (SI NO EXISTE ALGUNO, ES POR QUE SE HA ENCONTRADO EL ÓPTIMO).

EXAMINE ESTAS TRAYECTORIAS PARA ENCONTRAR LA RAMA O ARCO CON LA MENOR CAPACIDAD DE FLUJO RESTANTE E INCREMENTE EN ÉSTE VALOR, LA CAPACIDAD DEL FLUJO EN SENTIDO CONTRARIO.

DETERMINE TODAS LAS TRAYECTORIAS ESTRICTAMENTE POSITIVAS, HASTA QUE NO SE PERMITA FLUJO DEL NODO A UN NODO DESTINO.

Podemos, mediante el Algoritmo de Ford-Fulkerson, encontrar el flujo máximo de una red.

Algoritmo de Ford-FulkersonDe Wikipedia, la enciclopedia libre

Saltar a navegación, búsqueda

Aplicable a los Flujos maximales

Ford-Fulkerson(G,s,t){ for (cada arco (u,v) de E) { f[u,v]= 0; f[v,u]= 0; } while (exista un camino p desde s a t en la red residual Gf) { cf(p) = min{cf(u,v) : (u,v) está sobre p}; for (cada arco (u,v) en p) { f[u,v]= f[u,v] + cf(p) ; f[v,u]= - f[u,v]; } } }