Loading AI tools
Da Wikipédia, a enciclopédia livre
No campo da Otimização, o teorema do fluxo máximo-corte mínimo afirma que em um fluxo de rede, o valor máximo do fluxo passando de um ponto-origem até um ponto destino é igual à sua capacidade mínima, que quando removida da rede de uma forma específica ocasiona a situação onde nenhum fluxo passa mais entre a origem e o destino..
Este artigo não cita fontes confiáveis. (Março de 2011) |
O teorema do fluxo máximo-corte mínimo é um caso especial do teorema da dualidade e pode ser usado pra derivar o Teorema de Menger e o Teorema de König-Egerváry.
Seja uma rede (digrafo) com e sendo a origem e o destino de respectivamente.
O problema do fluxo máximo é maximizar | f |, ou seja, transportar o maior quantidade possível de fluxo de s até t.
O problema do corte mínimo é minimizar , ou seja, determinar S e T tal que a capacidade do corte S-T é mínimo.
O teorema do Fluxo Máximo-Corte Mínimo afirma que
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.