Provando que os fluxos máximos de gráfico não direcionado e gráfico dirigido equivalente são iguais

Question

Há um gráfico não direcionado $ g $ .Um gráfico $ h $ é construído alterando cada borda $ (A, B) $ na $ g $ para um par de bordas dirigidas $ (A, B) $ e $ (b, a) $ .Como provar que o fluxo máximo em $ h $ é igual ao fluxo máximo em $ g $ ?

Eu realmente não tenho nenhuma ideia de como começar.Eu só sei que posso usar ford-fulkerson em $ h $ e atualizar a borda inversa tal que $ f (A,b) + f (b, a)= c (a, b) $ mas é isso.

Answer 1

Se $ f_g $ é um fluxo válido para $ g $ , então existe um fluxo válido $ f_h $ para $ h $ tal que $ | f_g |= | f_h | $ . Isso é verdade, já que sempre há um fluxo $ f'_g $ para $ g $ tal que $ | f'_g |= | f_g | $ e nenhuma borda é percorrida em ambas as direções em uma decomposição de fluxo de $ f'_g $ . Se alguma borda $ (u, v) $ é percorrida por $ x $ unidades de fluxo de $ U $ para $ v $ e $ y \ le x $ unidades de fluxo de $ v $ para $ u $ então você poderia redefinir o fluxo para Só envia $ xy $ unidades de fluxo de $ u $ para $ v $ . Se $ (u, v) $ é usado a partir de $ u $ para $ v $ Você pode então definir $ f_h (u, v)= f'_g (u, v) $ e $ f_h (v, u)= 0 $ . (Se $ (u, v) $ não é usado, então $ f_h (u, v)= f_h (v, u)= 0 $ ).

Se $ f_h $ é um fluxo válido para $ h $ , então existe um fluxo válido $ f_g $ para $ g $ tal que $ | F_H |= | f_g | $ . Observe que, se $ f_h $ usa ambos $ (u, v) $ e $ (v, u) $ (assumir o wlog, que $ f_h (u, v) \ ge f_h (v, u) $ ) então o fluxo $ f'_h $ definido por $ f'_h (u, v)= f_h (u, v ) - f_h (v, u) $ , $ f'_h (v, u)= 0 $ e $ f'_h (x, y)= f_h (x, y) $ para $ (x, y) \ não \ in \ \ {(u, v ), (v, u) \} $ também é um fluxo válido para $ h $ e $ | f'_h |= | f_h | $ . Isso mostra que você pode definir $ f_g (u, v)= f'_h (u, v) $ .