En teoría de grafos , un corte de un grafo es una partición de los vértices en dos subconjuntos. También llamamos cortar al conjunto de bordes que tienen un final en cada subconjunto de la partición.
Si los bordes tienen un peso, el peso de corte es la suma de los respectivos pesos de los bordes de corte. De lo contrario, es el número de aristas de la sección.
Este objeto aparece en el modelado de muchos de los problemas relativos a las redes, en las que estamos buscando un corte st , es decir, un corte que separa dos especificados vértices s y t .
Los problemas naturales están encontrando un peso mínimo st ajuste y un peso máximo st ajuste.
El problema de corte mínimo (MIN-CUT) es equivalente al problema de flujo máximo , según el teorema de flujo-máx / corte-mínimo . Se puede resolver en tiempo polinomial .
El problema de corte máximo (MAX-CUT) es NP-completo (es uno de los 21 problemas NP-completo de Karp ).
Otro problema clásico es el del corte menos denso ( corte más escaso ). Definimos la densidad de un corte como la relación entre el número de bordes en el corte y el número de nudos en la más pequeña de las dos partes del corte. El problema es encontrar un corte de menor densidad.