Taglio massimo

In un grafo, un taglio massimo è un taglio di dimensione almeno pari a quella di tutti gli altri tagli. Il problema della ricerca di un taglio massimo in un grafo è noto come problema max-cut.

Il problema può essere enunciato semplicemente come segue. Si vuole ottenere un sottinsieme S dell'insieme dei vertici tale che il numero di archi tra S e l'insieme complementare abbia la più alta cardinalità possibile.

Esiste una versione più avanzata del problema, che riguarda i grafi pesati. In questa versione, ad ogni arco è associato un numero reale, detto "peso", e l'obiettivo del problema è di massimizzare non il numero di archi ma il peso totale degli archi fra S ed il suo complemento. Il problema max-cut su grafi pesati è solitamente ristretto ai pesi non-negativi, dato che pesi negativi possono determinare un problema di diversa natura.