Red de flujo

En teoría de grafos, una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente, al que se le asocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales se mantiene la ley de corrientes de Kirchoff, en donde la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el tráfico en un sistema de autopistas, fluidos viajando en tuberías, corrientes eléctricas en circuitos eléctricos o sistemas similares por lo que viaje algo entre nodos.

Descripción matemática

Una red de flujo es un grafo dirigido en donde cada arco tiene una capacidad no negativa .

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

Se supone 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.

Other Languages