Encontre a união de todos os cortes min de uma rede de fluxo

Question

Estou tentando resolver a seguinte pergunta:

.

Dada uma rede de fluxo $ n= (g= (v, e), c, s, t) $ . Deixe $ \ Mathcal F $ Seja o conjunto de todos os cortes mínimos. Prove que $ \ mathcal f $ está fechado sob interseções e uniões, ou seja, para cada $ s_1, s_2 \ in \ mathcal f , S_1 \ cope s_2 \ in \ mathcal f $ e $ s_1 \ cap s_2 \ in \ mathcal f $ .

Essa parte eu cuidei de apenas bem usando o teorema de fluxo Min-Cut-Max.

A outra parte é aquela que eu tive problemas com:

.

Dado um fluxo máximo $ F $ , encontrar $ s _ {\ min}=bigcap_ {s \ in \ bigcap_ {s \ in mathcal f} s \ text {e} s _ {\ max}=bigcock_ {s \ in \ mathcal f} S $ .

Eu percebi que, ao considerar um corte min $ (s, t) $ e, dado o gráfico residual (que pode ser construído a partir do fluxo máximo fornecido), cada vértice que é acessível a partir de $ s $ (nó de origem), deve estar em $ s $ , então eu foi capaz de usar isso para chegar a um algoritmo para encontrar $ s _ {\ min} $ .

mas como para encontrar um algoritmo para $ s _ {\ max} $ , estou meio tendo problemas para colocar meu dedo em uma propriedade de uma borda mínima, ou seja, o que é preciso para ser uma borda de corte (ou para um vértice para estar em $ s $ ) de algum corte mínimo?

Eu não estou procurando a resposta completa, mas sim uma sugestão .. qualquer ajuda é apreciada.

Answer 1

Nota $ s _ {\ max}= v- \ bigcap_ {s \ in \ mathcal {f}} (v-s) $ .E $ \ bigcap_ {s \ in \ mathcal {f}} (vs) $ é o conjunto de todos os vértices da qual $ t $ é acessível no gráfico residual.

A razão pela qual $ \ bigcap_ {s \ in \ mathcal {f}} (vs) $ é o conjunto de todos os vértices do qual $ t $ é acessível no gráfico residual é o mesmo que o motivo pelo qual $ s _ {\ min} $ é o conjunto deTodos os vértices acessíveis a partir de $ S $ .Você pode provar isso usando as condições complementares de esclacrição.