Nella teoria dei grafi, un taglio è una partizione dei vertici di un grafo in due sottoinsiemi disgiunti.

Ogni taglio determina un insieme di taglio (o cut-set), definito come l'insieme degli archi che hanno i propri estremi nei due sottinsiemi della partizione. In un grafo connesso, ogni cut-set è relativo ad un unico taglio.

In una rete di flusso, un taglio s-t è un taglio tale che il vertice sorgente (s) ed il pozzo (t) non appartengano allo stesso sottinsieme della partizione. La capacità di un taglio s-t è definita come la somma delle capacità degli archi appartenenti al cut-set.

Un taglio ${\displaystyle C=(S,T)}$ è la partizione dei vertici ${\displaystyle V}$ di un grafo ${\displaystyle G=(V,E)}$ in due sottinsiemi disgiunti S e T.

L'insieme di taglio di un taglio ${\displaystyle C=(S,T)}$ è l'insieme ${\displaystyle \{(u,v)\in E|u\in S,v\in T\}}$ degli archi che hanno un estremo in S e l'altro in T. Dato un grafo connesso G, condizione necessaria e sufficiente per cui un insieme di archi sia un cut-set è che la rimozione degli stessi renderebbe G non connesso.

In una rete di flusso G, detti s e t rispettivamente la sorgente e il pozzo di G, un taglio s-t è uno specifico taglio in cui ${\displaystyle s\in S}$ e ${\displaystyle t\in T}$.

In un grafo non orientato e non pesato, la dimensione (o peso) di un taglio è il numero di archi che lo attraversano. In un grafo pesato, il valore (o peso) di un taglio è la somma dei pesi degli archi che attraversano il taglio stesso.

Questa sezione sull'argomento matematica è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Teknopedia. Segui i suggerimenti del progetto di riferimento.

• L'intersezione fra un insieme di taglio e un ciclo contiene sempre un numero pari di archi.^[1]

Un taglio è minimo se il suo peso è al più uguale di quello di tutti gli altri possibili tagli. L'immagine sulla destra mostra un esempio di taglio minimo: la dimensione del taglio è 2, e non ci sono tagli di dimensione 1 poiché il grafo è privo di ponti.

Il teorema del flusso massimo e taglio minimo prova che il flusso massimo di una rete è uguale al peso di un taglio s-t. Esistono metodi che risolvono in tempo polinomiale il problema del taglio minimo, in particolare l'algoritmo di Edmonds-Karp.^[2]

Lo stesso argomento in dettaglio: Taglio massimo.

Un taglio è massimo se il suo peso è almeno uguale a quello di tutti gli altri possibili tagli. L'immagine sulla destra mostra un esempio di taglio massimo: la dimensione del taglio è 5, e non ci sono tagli di dimensione ${\displaystyle 6=|E|}$ (il numero degli archi), poiché il grafo non è bipartito.

In generale, trovare un taglio massimo è computazionalmente difficile.^[3] Il problema del taglio massimo è uno dei 21 problemi NP-completi di Karp,^[4] ed è APX-difficile, ovvero non esistono schemi di approssimazione in tempo polinomiale, a meno che P = NP.^[5]

Il problema sparsest cut (lett. "taglio più sparso") consiste nel bipartire i vertici in modo da minimizzare il rapporto tra il numero di archi attraversati dal taglio e quello dei vertici nella più piccola metà della partizione.

• Grafo connesso
• Taglio massimo
• Teorema del flusso massimo e taglio minimo

• Wikimedia Commons contiene immagini o altri file su taglio

• (EN) Eric W. Weisstein, Taglio, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica