Cut (teoria dei grafi)

Nella teoria dei grafi , un taglio di un grafo è una partizione dei vertici in due sottoinsiemi. Chiamiamo anche cut l'insieme di bordi che hanno un'estremità in ogni sottoinsieme della partizione.

Se i bordi hanno un peso, il peso del taglio è la somma dei rispettivi pesi dei bordi tagliati. Altrimenti, è il numero di bordi nella sezione.

Questo oggetto appare nella modellazione di molti problemi in materia di reti, dove stiamo cercando un taglio st , vale a dire un taglio che separa due specificati vertici s e t .

Problemi algoritmici associati

I problemi naturali stanno trovando un peso minimo st in forma e un peso massimo st forma.

Problemi di taglio minimo e massimo di taglio

Il problema del taglio minimo (MIN-CUT) è equivalente al problema del flusso massimo , secondo il teorema flusso-max / taglio-min . Può essere risolto in tempo polinomiale .

Il problema di taglio massimo (MAX-CUT) è NP-completo (è uno dei 21 problemi NP-completo di Karp ).

Un altro problema

Un altro problema classico è quello del taglio meno denso ( taglio più scarso ). Definiamo la densità di un taglio come il rapporto tra il numero di bordi nel taglio e il numero di nodi nella più piccola delle due parti del taglio. Il problema è trovare un taglio di minore densità.

Bibliografia

• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , e Clifford Stein ( trad.  Dall'inglese), Introduzione agli algoritmi , Paris, Dunod ,2002, 2 °  ed. , 1.146  p. [ dettaglio edizione ] ( ISBN  2-10-003922-9 )

• (en) Richard M. Karp , "Reducibility Among Combinatorial Problems" , in Raymond E. Miller e James W. Thatcher, Complexity of Computer Computations , Plenum,1972( ISBN  978-1-4684-2003-6 , DOI  10.1007 / 978-1-4684-2001-2_9 , leggi online ) , p.  85-103

Note e riferimenti

1. ( Cormen et al. 2002 ), Note introduttive del Capitolo 26.
2. ( Karp 1972 ).
3. Visualizza (in) Vijay Vazirani , algoritmi di approssimazione , Springer Verlag , 2001 (e 2003), 380  p. ( ISBN  978-3-540-65367-7 ) , cap.  21 ("Taglio più scarno").
4. Yury Makarychev, "  Sparsest Cut: Computational and Metric Geometry  " , presso l' Università di Chicago .