Prouvant que Max flux de graphique non dirigé et d'équivalent graphique dirigé sont égaux

Question

Il y a un graphique non dirigé $ g $ .Un graphique $ h $ est construit en changeant chaque bord $ (A, B) $ in $ g $ à une paire d'arêtes dirigées $ (a, b) $ et $ (b, a) $ .Comment prouver que le débit maximum dans $ h $ est égal au flux maximal dans $ g $ ?

Je n'ai aucune idée de la façon de commencer.Je sais juste que je peux utiliser Ford-Fulkerson sur $ h $ et mettre à jour le bord inversé de telle que $ F (A,b) + f (b, a)= c (a, b) $ mais c'est tout.

Answer 1

si $ f_g $ est un flux valide pour $ g $ , il existe alors un flux valide $ f_h $ pour $ h $ tel que $ | f_g |= | f_h | $ . Ceci est vrai car il y a toujours un flux $ f'_g $ pour $ g $ tel que $ | F'_G |= | f_g | $ et aucun bord n'est traversé dans les deux sens dans une décomposition de flux de $ f'_g $ . Si un bord $ (u, v) $ est traversé par $ x $ unités de flux de U $ U $ à $ v $ et $ y \ le x $ unités de débit de $ v $ à $ u $ alors vous pouvez redéfinir le flux vers Seulement envoyer $ xy $ unités de flux de $ u $ to $ V $ . Si $ (u, v) $ est utilisé à partir de $ u $ to $ v $ Vous pouvez alors définir $ f_h (u, v)= f'_g (u, v) $ et "Conteneur mathématique"> $ f_h (v, u)= 0 $ . (Si $ (u, v) $ est inutilisé alors $ f_h (u, v)= f_h (v, u)= 0 $ ).

si $ f_h $ est un flux valide pour $ h $ , puis il existe un flux valide $ f_g $ pour $ g $ tel que $ | f_h |= | f_g | $ . Notez que si $ f_h $ utilise à la fois $ (u, v) $ et $ (v, u) $ (assumer wlog, que $ f_h (u, v) \ ge f_h (v, u) $ ) alors le flux $ f'_h $ défini par $ f'_h (u, v)= f_h (u, v ) - f_h (v, u) $ , $ f'_h (v, u)= 0 $ et $ f'_h (x, y)= f_h (x, y) $ pour $ (x, y) \ pas \ in \ {(u, v ), (v, u) \} $ est également un flux valide pour $ h $ h $ et $ | $ | f'_h |= | f_h | $ . Cela montre que vous pouvez définir $ f_g (u, v)= f'_h (u, v) $

.