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
modificaUn taglio è la partizione dei vertici di un grafo in due sottinsiemi disgiunti S e T.
L'insieme di taglio di un taglio è l'insieme 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 e .
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à
modifica- L'intersezione fra un insieme di taglio e un ciclo contiene sempre un numero pari di archi.[1]
Taglio minimo
modifica
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
modifica
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 (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
modificaIl 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
modifica- ^ (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).
- ^ (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.
- ^ (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.
- ^ (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.
- ^ (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
modificaAltri progetti
modifica
Wikimedia Commons contiene immagini o altri file su taglio
