Algoritmo de Ford-Fulkerson
O algoritmo de Ford-Fulkerson é um algoritmo utilizado para resolver problemas de fluxo em rede. O algoritmo é empregado quando se deseja encontrar um fluxo de valor máximo que faça o melhor uso possível das capacidades disponíveis na rede em questão.
Imagem: Fernanda Duarte · BY-SA · Openverse
Uma rede de fluxo é um grafo direcionado G = ( N , A ) {\displaystyle G=(N,A)} , sendo N {\displaystyle N} o conjunto de nós e A {\displaystyle A} o conjunto de arestas, dotado das seguintes propriedades: Um fluxo é uma função f : A → R + {\displaystyle f:A\rightarrow \mathbb {R_{+}} \,} que respeite as seguintes propriedades: Para evitar comportamentos patológicos, em geral se supõe que os valores das capacidades são inteiros (o que acarreta, neste algoritmo, em valores de fluxos inteiros). Definindo o valor de um fluxo como v ( f ) = ∑ a ∈ o u t ( s ) f ( a ) {\displaystyle v(f)=\sum _{a\in out(s)}f(a)} (sendo o u t ( s ) {\displaystyle out(s)} o conjunto de arestas que sai de s {\displaystyle s} ), o problema a ser resolvido é, dada uma rede de fluxo G {\displaystyle G} , achar um fluxo f {\displaystyle f} tal que v ( f ) {\displaystyle v(f)} seja o máximo possível.
Começamos supondo que o fluxo inicial em todas as arestas é nulo. Desta forma, iremos aumentar gradativamente este valor acrescentando fluxo na fonte através de algumas regras básicas. A ideia principal do algoritmo gira em torno de duas operações: quando uma aresta possui menos fluxo do que permite a sua capacidade (o que inclui possuir fluxo nulo), temos a opção de “empurrar” fluxo na sua direção (“empurrar fluxo à frente”); do mesmo modo, quando uma aresta possui uma quantidade positiva de fluxo, seja ela menor ou igual à sua capacidade, temos a opção de fazer com que esse fluxo retroceda, “empurrando-o para trás”, ou seja, na direção contrária. Para concretizar tais operações, definimos primeiramente um grafo auxiliar que vamos chamar de grafo residual ( G R {\displaystyle G_{R}} ) , que é construído da seguinte forma: Observação: Cada aresta do grafo original G {\displaystyle G} pode dar origem a no máximo duas arestas correspondentes a ela no grafo residual, já que se a {\displaystyle a} possuir um fluxo positivo que seja menor que sua capacidade, uma aresta de mesma direção será criada para representar o fluxo a mais que ainda pode ser carregado, e uma aresta de direção oposta será inserida para representar o fluxo existente que pode retroceder caso seja necessário para a otimização do problema. Resumindo, G R {\displaystyle G_{R}} pode possuir até duas vezes o número de arestas de G {\displaystyle G} .
Imagem: Fernanda Duarte · BY-SA · Openverse
Para valores inteiros de c a {\displaystyle c_{a}} , a complexidade do algoritmo é O ( m f ) {\displaystyle O(mf)} , em que m {\displaystyle m} representa o número de arestas presentes no grafo G {\displaystyle G} e f {\displaystyle f} o fluxo máximo encontrado. Utilizando uma busca em largura (breadth-first search) ou uma busca em profundidade (depth-first search), é possível encontrar um caminho simples s {\displaystyle s} - t {\displaystyle t} no grafo residual em O ( m + n ) {\displaystyle O(m+n)} , tal que n {\displaystyle n} é o número total de nós do grafo. Supondo que todos os nós possuem pelo menos uma aresta incidente, podemos afirmar que m > n / 2 {\displaystyle m>n/2} e, portanto, simplificamos a expressão anterior para O ( m ) {\displaystyle O(m)} . Cada caminho simples encontrado resulta em um novo fluxo a ser acrescentado no grafo original. Como os incrementos de fluxo obtidos em cada iteração serão sempre maiores ou iguais a 1, por as capacidades serem inteiras, podemos concluir que o algoritmo irá rodar em no máximo O ( m f ) {\displaystyle O(mf)} para atingir o fluxo máximo desejado.
