$ S $ s $ -component in minut

Question

Supponiamo che vi sia un grafico diretto $ g= (v, e) $ , con sorgente $ S $ e lavello $ T $ e calcolo il flusso massimo su di esso. Allora so che riesco a trovare un min-taglio $ (a, b) $ , lasciando $ A $ Essere il set di vertici che sono raggiungibili dalla sorgente $ s $ .

La mia domanda è questa set $ a $ la più piccola possibile $ s $ -Component? Penso che sia. Per essere precisi, esistono un sottoinsieme di vertici $ a ^ * $ , in modo tale da $ (a ^ *, v \ Setminus a ^ *) $ è un minimo e per tutti gli altri possibili sottoinsiemi di vertici $ A $ tale che $ (A, V \ SetMinus A) $ è un minimo, abbiamo $ Dimensione (A ^ *) \ Leq Dimensione (A) $ .

Inoltre, per qualsiasi altra classe min-tagliata $ (c, d) $ , abbiamo $ a \ sottoinsieme C $ ?. Penso anche che questo sia il caso. Ma non posso provarlo.

Qualsiasi intuizione / suggerimenti è molto apprezzata!

Modifica

Definizione di $ s $ -Component: Il min-taglio è la partizione dei vertici di $ G $ in due set disgiunti $ (A, B) $ < / span>, dove $ A $ contiene la sorgente $ s $ e $ B $ Contiene il lavello $ T $ . La $ s $ -Component w.r.t. Un min-taglio è quindi il set $ A $ .

con "più piccolo" $ s $ -Component intendo $ s $ -Component con cardinalità più piccola . Mi sto chiedendo se ci possono essere diverse diverse minimal $ s $ -component w.r.t. Impostare l'inclusione, I.e. $ s $ -Componenti con la stessa cardinalità, ma non sono uguali come set. Equivalentemente, chiedendo se c'è un minimo $ s $ -Component; Un insieme di vertici che è in tutto $ s $ -Components.

Answer 1

Credo che la risposta sia sì: qualsiasi min-taglio costruito in questo modo da un flusso massimo avrà anche una possibile cardinalità minima possibile, tra tutti i possibili minimi tagliati.

Ci possono essere più minimi minimi, tutti con lo stesso costo. Formano una struttura a reticolo: l'intersezione di due minimi minuti è un altro minimo, e l'unione di due tagli minuti è un altro minimo. È possibile identificare un elemento "più piccolo" in questo reticolo prendendo l'intersezione di tutti i minimi minimi; Questo sarà un altro taglio minimo, e avrà la più piccola cardinalità di tutti i tagli minuti.

Come lo capisco, è possibile dimostrare che il minimo ottenuto da un flusso massimo è sempre questo min-taglio "più piccolo". O, per metterlo in un altro modo, se pensi alla fonte $ s $ a sinistra e il lavandino $ t $ Sulla destra, quindi qualsiasi minuto ottenuto da una $ s, T $ -max-flow sarà sempre un taglio "a sinistra". Inoltre, seguirà che qualsiasi altro min-taglio sarà un superset di questo taglio trovato da max-flow, esattamente come hai congetturato.

Per i riferimenti a questi risultati e in altri materiali correlati, consultare le seguenti domande (Nota: potrebbe essere necessario ricontrollare alcune delle rivendicazioni te stesso, poiché non ho verificato personalmente):

Ford-Fulkerson produce sempre il min-taglio a sinistra

https://stackoverflow.com/a/8101250/781723

https://stackoverflow.com/Q/26696312/781723

https://stackoverflow.com/Q/9210755/781723

https://stackoverflow.com/q/41964288/781723

Answer 2

Rispondi alla tua prima domanda: non necessariamente. Qualsiasi algoritmo a flusso massimo di scaffale o min-taglio produrrà una partizione arbitraria min-tagliata, non una cardinalità minima. Ma puoi aumentare il tuo grafico, in modo tale che l'output del flusso massimo sia ciò che desideri:

Let $ A, V \ SetMINUS A $ e $ B, v \ setmino B $ Essere Partizioni min-tagliate: $$ \ DELTA (A, V \ SetMINUS A)=DELTA (B, V \ SetMINUS B)=min_ {X \ SOTETETQ V, S \ IN X} \ Delta ( X, v \ setmino x) $$ Ora, aggiungi i bordi con il peso $ \ varepsilon> 0 $ da vertice $ T $ a tutti gli altri vertici. I nuovi tagli corrispondenti a $ A $ e $ B $ Avere i pesi aggiornati: $$ \ Delta (A, V \ SetMinus A) + | A | \ clot \ varepsilon, \\ \ Delta (B, V \ SetMinus B) + | B | \ clot \ varepsilon $$ rispettivamente. Poiché entrambi i primi termini sono uguali, i secondi termini $ \ varepsilon | A | $ e $ \ varepsilon | B | $ determinerà l'ordine. Quindi il minimo nel nuovo grafico è la cardinalità minima, partizione min-tagliata nel grafico originale. L'unico avvertueat è che $ \ varepsilon $ deve essere scelto abbastanza piccolo, per assicurarsi che il min-taglio nel nuovo grafico sia un minimo del grafico originale . Se i pesi sono numeri interi, qualsiasi valore inferiore a $ 1 / | v | $ sarebbe sufficiente.

( $ \ stella) $ : $ \ delta (x, v \ setmino x) $ denota la somma dei pesi dei bordi tra i bordi tra $ x $ e $ v \ setmino x $ .