Em matemática, o k-corte mínimo é o problema de otimização combinatória que requer encontrar um conjunto de arestas cuja remoção dessas arestas iria particionar o grafo em k componentes conexos. Essas arestas são chamadas de k-corte. O objetivo é encontrar o k-corte de peso mínimo. Esse particionamento pode ter aplicações em design VLSI, mineração de dados, elementos finitos e comunicação em computação paralela.
Definição formal Dado um grafo não direcionado G = (V, E) com atribuição de pesos nas arestas w: E → N e um inteiro k ∈ {2, 3, …, |V|}, particione V em k conjuntos disjuntos F = {C1, C2, …, Ck} enquanto minimizando
Para um k fixo, esse problema é solúvel em tempo polinomial de O(|V|k2).. No entanto, o problema é NP-completo se k for parte da entrada. Também é NP-completo se especificarmos vértices e pedirmos para o k-corte mínimo que separa esses vértices entre cada um dos conjuntos., which cites
Ver também Corte máximo Corte mínimo
Notes
Referências
Categoria:Otimização combinatória Categoria:Teoria dos grafos