Red de flujo
En la teoría de grafos , una red de flujo (también conocida como red de transporte ) es un gráfico dirigido donde cada borde tiene una capacidad y cada borde recibe un flujo. La cantidad de flujo en un borde no puede exceder la capacidad del borde. A menudo, en la investigación de operaciones , un grafo dirigido se llama red , los vértices se llaman nodos y los bordes se llaman arcos . Un flujo debe satisfacer la restricción de que la cantidad de flujo que ingresa a un nodo es igual a la cantidad de flujo que sale de él, a menos que sea una fuente , que solo tiene flujo saliente, o un sumidero ., que solo tiene flujo entrante. Una red se puede utilizar para modelar el tráfico en una red informática, la circulación con demanda, los fluidos en las tuberías, las corrientes en un circuito eléctrico o cualquier cosa similar en la que algo viaja a través de una red de nodos.
Una red es un gráfico G = ( V , E ) , donde V es un conjunto de vértices y E es un conjunto de aristas de V , un subconjunto de V × V , junto con una función no negativa c : V × V → ∞ , llamada función de capacidad . Sin pérdida de generalidad , podemos suponer que si ( u , v ) ∈ E entonces ( v , u )es también un miembro de E , ya que si ( v , u ) ∉ E entonces podemos sumar ( v , u ) a E y luego establecer c ( v , u ) = 0 .
Si se distinguen dos nodos en G , una fuente s y un sumidero t , entonces ( G , c , s , t ) se denomina red de flujo . [1]
Hay varias nociones de una función de flujo que se pueden definir en un gráfico de flujo. Las funciones de flujo modelan el flujo neto de unidades entre pares de nodos y son útiles cuando se hacen preguntas como ¿cuál es el número máximo de unidades que se pueden transferir desde el nodo fuente s al nodo sumidero t? El ejemplo más simple de una función de flujo se conoce como pseudo-flujo.
Dado un pseudo-flujo f en una red de flujo, a menudo es útil considerar el flujo neto que ingresa a un nodo dado u , es decir, la suma de los flujos que ingresan a u . La función de exceso x f : V → está definida por x f ( u ) = Σ v ∈ V f ( v , u ) . Se dice que un nodo u está activo si x f ( u ) > 0 , deficiente si x f( u ) < 0 o conservando si x f ( u ) = 0 .
El valor de un flujo factible f , denotado | f | , es el flujo neto hacia el sumidero t de la red de flujo. Es decir, | f | = X F ( t ) .
