Beweisen, dass maximale Strömungen ungerichteter Grafik und äquivalent gerichteter Grafik gleich sind

Question

Es gibt eine ungerechte Grafik $ g $ .Ein Diagramm $ H $ wird durch Ändern jeder Kante $ (a, b) $ in $ g $ an ein Paar gerichtete Kanten $ (A, B) $ und $ (B, a) $ .Wie beweisen Sie, dass der maximale Durchfluss in $ H $ gleich dem maximalen Durchfluss in $ g $ ist?

Ich habe keine Ahnung, wie man es anfängt.Ich weiß nur, dass ich Ford-Fulkerson auf $ H $ verwenden kann, und aktualisieren Sie die Umkenderkante so, dass $ F (A,b) + f (b, a)= c (a, b) $ aber das ist es.

Answer 1

Wenn $ F_G $ ein gültiger Fluss für $ g $ ist, gibt es dann einen gültigen Flow $ F_H $ für $ H $ so, dass $ | f_g |= | f_h | $ . Dies gilt, da es immer einen Fluss- $ F'_g $ für $ G $ so, dass $ | f'_g |= | F_G | $ und keine Kante wird in beide Richtungen in beide Richtungen in einer Durchflusszusammensetzung von $ F'_g $ durchlaufen. Wenn einige Kante $ (u, v) $ von $ x $ Fließeinheiten von $ u $ bis $ V $ und $ y \ le x $ Flusseinheiten von $ V $ bis $ u $ dann könnten Sie den Fluss neu definieren Senden Sie nur $ XY $ Flusseinheiten von $ u $ bis $ V $ . Wenn $ (u, v) $ von $ U $ bis $ V $ Sie können dann $ F_H (u, v)= f'_g (u, v) $ und $ F_H (V, U)= 0 $ . (Wenn $ (u, v) $ nicht verwendet ist, dann $ f_h (u, v)= f_h (v, u)= 0 $ ).

Wenn $ F_H $ ein gültiger Fluss für $ H $ ist, gibt es einen gültigen Flow $ F_G $ für $ g $ so, dass $ | f_h |= | f_g | $ . Beachten Sie, dass, wenn $ F_H $ sowohl $ (u, v) $ und $ (V, U) $ (Nehmen Sie an, Wlog, diese $ f_h (u, v) \ GE F_H (V, U) $ ) Dann der Fluss $ F'_H $ definiert durch $ f'_h (u, v)= f_h (u, v ) - F_H (V, U) $ , $ F'_H (V, U)= 0 $ , und $ f'_h (x, y)= f_h (x, y) $ für $ (x, y) \ nicht \ in \ {(u, v ), (v, u) \} $ ist auch ein gültiger Fluss für $ H $ und $ | f'_h |= | f_h | $ . Dies zeigt, dass Sie $ F_G (U, V)= F'_H (U, V) $ definieren können.