Trova l'unione di tutti i tagli minuti di una rete di flusso

Question

Sto cercando di risolvere la seguente domanda:

.

Data una rete di flusso $ n= (g= (v, e), c, s, t) $ . Let $ \ Mathcal F $ Sii il set di tutti i tagli minimi. Dimostra che $ \ mathcal f $ è chiuso sotto intersezioni e sindacati, cioè per ogni $ s_1, s_2 \ in \ mathcal f , S_1 \ Coppa S_2 \ in \ Mathcal F $ e $ s_1 \ cap s_2 \ in \ mathcal f $ .

Quella parte di cui mi sono preso cura di andare bene usando il teorema min-cut-max-flow.

L'altra parte è quella che ho avuto problemi con:

.

Dato un flusso massimo $ f $ , trovare $ s _ {\ min}=bigcap_ {s \ in \ Mathcal f} s \ testo {e} s _ {\ max}=bigcup_ {s \ in \ mathcal f} s $ .

Mi sono reso conto che quando si considera un taglio min $ (s, t) $ e dato il grafico residuo (che può essere costruito dal flusso massimo indicato), Ogni vertice raggiungibile da $ s $ (nodo sorgente), deve essere in $ s $ , quindi io è stato in grado di usarlo per trovare un algoritmo per trovare $ s _ {\ min} $ .

Ma come per trovare un algoritmo per $ s _ {\ max} $ , sono un po 'di avere difficoltà a mettere il dito su una proprietà di un bordo minimo, cioè cosa ci vuole per essere un bordo tagliato (o per un vertice da essere in $ s $ ) di qualche taglio minimo?

Non sto cercando la risposta completa ma piuttosto un suggerimento .. Qualsiasi aiuto è apprezzato.

Answer 1

Nota $ s _ {\ max}= v- \ bigcap_ {s \ in \ mathcal {f}} (V) $ .E $ \ bigcap_ {s \ in \ mathcal {f} \ in \ mathcal {f}} (vs) $ è il set di tutti i vertici da cui $ T $ è raggiungibile nel grafico residuo.

Il motivo per cui $ \ bigcap_ {s \ in \ mathcal {f} \ in \ mathcal {f}} (vs) $ è il set di tutti i vertici da cui $ T $ è raggiungibile nel grafico residuo è lo stesso del motivo per cui $ s _ {\ min} $ è il set diTutti i vertici raggiungibili da $ s $ .Puoi dimostrarlo usando le condizioni relative alle ristrettezza complementari.