Taglio (teoria dei grafi)

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.

Definizione

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.

Proprietà

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

Taglio minimo

Un taglio minimo

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]

Taglio massimo

Un 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]

Sparsest cut

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.

Note

1. (EN) Kevin Wayne, Greedy Algorithms II (PDF), su cs.princeton.edu, Università di Princeton, Dipartimento di Informatica, 18 febbraio 2013. URL consultato il 13 settembre 2016 (archiviato dall'url originale il 13 settembre 2016).
2. (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, Introduction to Algorithms, 2nd, MIT Press and McGraw-Hill, 2001, p. 563, 655,1043, ISBN 0-262-03293-7.
3. (EN) Michael R. Garey e David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979, A2.2: ND16, pg.210, ISBN 0-7167-1045-5.
4. (EN) R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller e J. W. Thacher (a cura di), Complexity of Computer Computation, New York, Plenum Press, 1972, pp. 85–103.
5. (EN) S. Khot, G. Kindler, E. Mossel e R. O’Donnell, Optimal inapproximability results for MAX-CUT and other two-variable CSPs? (PDF), in Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, 2004, pp. 146–154.

Voci correlate

• Grafo connesso
• Taglio massimo
• Teorema del flusso massimo e taglio minimo
• Conduttanza (teoria dei grafi)

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su taglio

Collegamenti esterni

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