`maxflow`

Fluxo máximo em uma rede, de uma origem a um destino.

Categoria: Mathematics > Graph and Network Algorithms

Sintaxe

mf = maxflow(G, s, t)

Retorna o valor do fluxo máximo do nó s ao nó t.

[mf, GF] = maxflow(G, s, t)

Também retorna um grafo com o fluxo em cada aresta.

Descrição

O fluxo máximo é quanto se pode enviar de s a t sem exceder a capacidade de nenhuma aresta. Pelo teorema do fluxo máximo e corte mínimo, ele é igual à capacidade do conjunto mais barato de arestas cuja remoção desconecta t de s. Os usos clássicos são redes de transporte e de tubulações, emparelhamento bipartido e conectividade.

Argumentos de entrada

G: Um graph ou digraph cuja coluna Weight guarda as capacidades das arestas. Sem pesos, toda capacidade é 1.
s, t: Nós de origem e destino (sorvedouro).

Argumentos de saída

mf: Valor do fluxo máximo.
GF: Grafo com os mesmos nós e arestas de G, em que Weight é o fluxo transportado por cada aresta.

Exemplo

Duas rotas com capacidade limitada

D = digraph([1 1 2 3], [2 3 4 4], [3 2 2 3]);
[mf, GF] = maxflow(D, 1, 4);
mf
GF.Edges.Weight'

Saída

mf = 4
ans = 1×4

     2     2     2     2

Veja também

shortestpath minspantree digraph adjacency