Топ-100
Indietro

ⓘ 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 ins ..




                                     

ⓘ 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 linsieme 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.

                                     

1. Definizione

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

Linsieme di taglio di un taglio C = S, T {\displaystyle C=S,T} è linsieme { u, v ∈ E | u ∈ S, v ∈ T } {\displaystyle \{u,v\in E|u\in S,v\in T\}} degli archi che hanno un estremo in S e laltro 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 s ∈ S {\displaystyle s\in S} e t ∈ T {\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.

                                     

2. Taglio minimo

Un taglio è minimo se il suo peso è al più uguale di quello di tutti gli altri possibili tagli. Limmagine 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 lalgoritmo di Edmonds-Karp.

                                     

3. Taglio massimo

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

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

                                     

4. 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.