Reduzindo a cobertura mínima de vértices em um gráfico bipartido para o fluxo máximo

É possível mostrar que a cobertura mínima de vértices em um gráfico bipartido pode ser reduzida a um problema de fluxo máximo? Ou para o problema de corte mínimo (siga o teorema de corte mínimo de fluxo máximo, a reivindicação é válida).

Intuitivamente: para cada fluxo, escolha um ponto final e, em seguida, é uma cobertura mínima de vértice no gráfico bipartido. Mas isso pode ser mostrado rigorosamente?

De acordo com o teorema de König , o tamanho da cobertura mínima de vértices no gráfico bipartido é igual ao tamanho da correspondência máxima em , e há uma redução óbvia da correspondência máxima no gráfico bipartido para o problema de fluxo máximo.$G$$G$

Chame as duas partições dos nós e . Adicionar dois novos nós, uma fonte e uma pia . Conecte o nó inicial a todos os nós em com uma borda com capacidade máxima de um. Conecte todos os nós em à pia com bordas com capacidade máxima de um. Por fim, forneça a todas as bordas originais do gráfico a capacidade máxima de uma. Agora, encontrar o fluxo máximo de a encontrará a cobertura mínima do vértice.$A$$B$$s$$t$$A$$B$$s$$t$

Para cada aresta incluída no fluxo máximo, o nó ou fará parte da cobertura mínima do vértice.$(u,v)$$u$$v$

Desenhe isso e você entenderá.