Menor $ S $ -Component em minut

Question

Suponha que haja um gráfico direcionado $ g= (v, e) $ , com fonte $ S $ e pia $ t $ e eu calcula o fluxo máximo nele. Então eu sei que posso encontrar um min-corte $ (A, B) $ , permitindo $ a $ Seja o conjunto de vértices que são acessíveis a partir da fonte $ S $ .

minha pergunta é esta definida $ a $ a $ o menor possível $ s $ -component? Eu acho que é. Para ser preciso, existe um subconjunto de vértices $ a ^ * $ , tal que $ (A ^ *, V \ setminus a ^ *) $ é um corte mínimo, e para todos os outros subconjuntos possíveis de vértices $ a $ tal que $ (a, v \ setminus a) $ é um corte mínimo, temos $ tamanho (A ^ *) \ leq tamanho (a) $ .

Além disso, para qualquer outro min-corte $ (c, d) $ , temos $ a \ subconjunto C $ ?. Eu também acho que este é o caso. Mas eu não posso provar isso.

Qualquer intuição / dicas são muito apreciadas!

editar

Definição de $ S $ -component: O minetro é a partição dos vértices de $ g $ em dois conjuntos de disjuntos $ (A, B) $ < / span>, onde $ a $ contém a fonte $ s $ e $ B $ contém a pia $ t $ . A $ s $ -component w.r.t. Um minett é então o conjunto $ a $ .

Por "menor" $ S $ -component quero dizer $ S $ -component com menor cardinalidade . Eu estou querendo saber se pode haver vários mínimo $ s $ -component w.r.t. Defina a inclusão, isto é, $ S $ -Componentes com a mesma cardealidade, mas não são iguais como conjuntos. Equivalentemente, imaginando se há um mínimo $ s $ -component; Um conjunto de vértices que está em todos os $ s $ -components.

Answer 1

Eu acredito que a resposta é sim: qualquer corte mínimo construído dessa maneira de um fluxo máximo também terá uma cardinalidade mínima possível, entre todos os pequenos min-cortes.

Pode haver vários min-cortes, todos com o mesmo custo. Eles formam uma estrutura de treliça: A intersecção de dois min-cortes é outro corte mínimo, e a união de dois min-cortes é outro corte mínimo. Você pode identificar um elemento "menor" nesta treliça, tomando a interseção de todos os min-cortes; Este será outro corte mínimo, e terá a menor cardinalidade de todos os min-cortes.

Como eu entendo, é possível provar que o corte minet obtido a partir de um fluxo máximo é sempre este min-corte mínimo "menor". Ou, para colocar em outra maneira, se você pensar na fonte $ s $ à esquerda e a pia $ t $ à direita, em seguida, qualquer corte mínimo obtido a partir de uma $ s, T $ -max-flow será sempre um corte "mais à esquerda". Além disso, ele seguirá que qualquer outro corte mínimo será um superset deste corte encontrado pelo fluxo máximo, exatamente como você conjetou.

Para referências a esses resultados, e outros materiais relacionados, consulte as seguintes perguntas (Nota: Você pode precisar dar duas vezes algumas das reivindicações, pois não os verificou pessoalmente):

FORD-Fulkerson sempre produz a esquerda mais min-cortada

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

Responda sua primeira pergunta: não necessariamente. Qualquer algoritmo de fluxo máximo ou corte off-o-prateleira produzirá uma partição min-cortada arbitrária, não uma cardinalidade mínima. Mas você pode aumentar seu gráfico, de modo que a saída máxima do fluxo é o que você deseja:

Deixe $ a, v \ setminus a $ e $ b, v \ setminus b $ ser Partições mínimas: $$ \ delta (A, v \ setminus a)=delta (B, v \ setminus b)=min_ {x \ subseteq v, s \ in x} \ delta X, v \ setminus x) $$ Agora, adicione bordas com peso $ \ VAREPSILON> 0 $ do vértice $ t $ para todos os outros vértices. Os novos cortes correspondentes a $ a $ e $ B $ Tenha os pesos atualizados: $$ \ delta (A, v \ setminus a) + | a | \ Cdot \ Varepsilon, \\ \ delta (B, v \ setminus b) + | b | \ cdot \ varepsilon $$ respectivamente. Como ambos os primeiros termos são iguais, os segundos termos $ \ VAREPSILON | A | $ e $ \ varepsilon | b | $ irá determinar o pedido. Assim, o min-cortado no novo gráfico é a cardealidade mínima, a partição mínima no gráfico original. A única ressalva é que $ \ VAREPSILON $ deve ser escolhido pequeno o suficiente, para se certificar de que o mínimo no novo gráfico é um corte mínimo no gráfico original . Se os pesos são inteiros, qualquer valor menor que $ 1 / | v | $ seria suficiente.

( $ \ star) $ : $ \ delta (x, v \ setminus x) $ Denota a soma de pesos de bordas transversais entre $ x $ e $ v \ setminus x $ .