Dado um fluxo de rede encontrar se há um corte min que apenas uma das bordas dadas estava nela

Question

Dado um fluxo de rede $ g= (v, e) $ com função de capacidade $ c $ fonte $ S $ e buraco $ t $ , e dado 2 bordas $ E_1, E_2 $ .

Encontre se existe um corte mínimo de tal forma que apenas uma das bordas pertence ao corte mín.

Espero obter ajuda.

Answer 1

Primeiro, calcule o valor mínimo de corte $ c $ da rede.

segundo, remova a borda $ E_1 $ e aumente a capacidade de $ E_2 $ para infinito, entãoCalcule o valor mínimo de corte $ c_1 $ da nova rede.

terceiro, remova a borda $ E_2 $ e aumente a capacidade de $ E_1 $ para infinito, entãoCalcule o valor mínimo de corte $ c_2 $ da nova rede.

Agora você pode verificar se $ c-c_1 \ ge c (e_1) $ ou $ c-c_2 \ gec (e_2) $ para ver se existe um minetrotado na rede inicial que contém exatamente uma das $ E_1, E_2 $ .