Em geral

Na teoria dos grafos, uma rede de fluxo é um grafo direcionado onde existem dois vértices especiais "Vértice (Teoria dos Grafos)"), um chamado fonte, ao qual um fluxo positivo está associado, e outro chamado sink, que possui um fluxo negativo e uma certa capacidade positiva está associada a cada aresta. Em cada vértice diferente dos dois especiais, é mantida a lei das correntes de Kirchoff, onde a soma dos fluxos que entram em um vértice deve ser igual à soma dos fluxos que saem dele (propriedade de conservação do fluxo). Ele pode ser usado para modelar o tráfego em um sistema rodoviário, fluidos viajando em tubulações, correntes elétricas em circuitos elétricos ou sistemas similares em que algo viaja entre nós.

Um dos principais usos dos chamados algoritmos de fluxo é encontrar o fluxo máximo da fonte ao coletor, sempre obedecendo a certas restrições.

Uma rede de fluxo é um grafo direcionado onde cada arco tem uma capacidade não negativa.

Dois vértices são distinguidos: a origem s e o destino t.

Supõe-se que cada vértice esteja em algum caminho de s a t.

Um fluxo em G é uma função tal que.

O valor do fluxo é.

O problema de fluxo máximo tenta maximizar esse fluxo.

Contenido

Tenemos el conocido problema de flujo máximo o maximal: ¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero 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 máximo 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.

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

Este algoritmo es un método iterativo, el cual, empieza con un flujo nulo y en cada iteración se va obteniendo un valor del flujo que va aumentando el camino, hasta que no se pueda aumentar más.

Depende de tres puntos vitales:.

Restrições

As restrições de capacidade mencionadas são as seguintes:.