Max-flow min-cut??

O max-flow min-cut teorema que, para um senario transmissão unicast, que é apenas um nó de origem e receber um nó, o fluxo máximo do nó de origem para receber o nó é equivalente ao valor (de) min corte entre os nó de origem e de receber o nó.

Nas declarações acima, o conceito de corte min, ou corte mínimo, deveria ser explicado.Cut é um conjunto de arestas, e quando você remover este conjunto de arestas do nó de origem será desligado do nó receber.Para cada corte, não existe um valor associado que é a soma das capacidades das arestas no corte.Obviamente, corte mínimo é um corte, cujo valor é o menor.Às vezes, nós também chamar o valor do corte mínimo de corte mínimo.

Este teorema foi provado por mais de meio século por várias pessoas.Com o advento da teoria de codificação de rede, ele aparece com muita freqüência.

 
Max-flow min-cut implica que a quantidade máxima de fluxo é igual à capacidade do corte mínimo.Cut-Cut é a partição de vértices do grafo em dois conjuntos.
estes dois conjuntos de vértices são ligados por arestas (linhas)
estas arestas tem algum peso (capacit)
pode haver muitos cortes de muitos como este em um gráfico de grandes dimensões.

corte mínimo de corte mínimo é aquele em que as linhas ou arestas que são a ligação entre dois partição de um conjunto têm capacidade ou o peso mínimo, em comparação com todos os outros cortes no gráfico.

capacidade para, finalmente, é superior limitada pelo mais fraco corte.

esse max-min formulários de fluxo de corte

também se referem a Wikipédia

 
Dear My Friend
Para obter mais informações você pode consultar literaturas sobre "a capacidade dos canais de retransmissão" ou "rede de codificação".

 

Welcome to EDABoard.com

Sponsor

Back
Top