corte máximo

Para um grafo, um corte máximo é um corte cujo tamanho é de pelo menos o tamanho de qualquer outro corte. O problema de encontrar um corte máximo em um grafo é conhecido como Problema do Corte-Máximo (Max-Cut). O problema pode ser descrito simplesmente como segue. Deseja-se um subconjunto S do conjunto de vértices tal que o número de arestas entre S e o subconjunto complementar é tão grande quanto possível. Há uma versão mais avançada do problema que se chama Corte-Máximo ponderado. Nesta versão cada aresta tem um número real, o seu peso, e o objetivo é maximizar não o número de arestas, mas o peso total das arestas entre S e seu complemento. O problema do Corte-Máximo ponderado é frequente, mas nem sempre, restrito a pesos não-negativos, porque pesos negativos podem alterar a natureza do problema.