Corte maximo
Para un gráfico , un corte máximo es un corte cuyo tamaño es al menos el tamaño de cualquier otro corte. Es decir, es una partición de los vértices del gráfico en dos conjuntos complementarios S y T , de manera que el número de aristas entre el conjunto S y el conjunto T sea lo más grande posible. El problema de encontrar un corte máximo en una gráfica se conoce como Problema de corte máximo.
El problema se puede plantear simplemente de la siguiente manera. Se quiere un subconjunto S del conjunto de vértices de modo que el número de aristas entre S y el subconjunto complementario sea lo más grande posible. De manera equivalente, se desea un subgrafo bipartito del gráfico con tantas aristas como sea posible.
Existe una versión más general del problema llamada Max-Cut ponderado, donde cada borde está asociado con un número real, su peso , y el objetivo es maximizar el peso total de los bordes entre S y su complemento en lugar del número de Los bordes. El problema de corte máximo ponderado que permite ponderaciones tanto positivas como negativas se puede transformar trivialmente en un problema de corte mínimo ponderado cambiando el signo en todas las ponderaciones.
El siguiente problema de decisión relacionado con los cortes máximos se ha estudiado ampliamente en la informática teórica :
Se sabe que este problema es NP-completo . Es fácil ver que el problema está en NP : una respuesta afirmativa es fácil de probar presentando un corte lo suficientemente grande. La NP-completitud del problema se puede mostrar, por ejemplo, mediante una reducción de la máxima 2-satisfacibilidad (una restricción del problema de máxima satisfacibilidad ). [1] La versión ponderada del problema de decisión fue uno de los 21 problemas NP-completos de Karp ; [2] Karp mostró el NP-completo mediante una reducción del problema de la partición .
La canónica variante de optimización del problema de decisión anterior se conoce generalmente como el -Cut Máximo Problema o Max-Cut y se define como:
