最大流問題の押し戻しが合った際のここの値はどこへいったのだ・・・ - auの日記auです。 タイトルが思いつかなかったので心のままに書きました。 ネットワークの勉強をしている際に、最大流問題という、残余ネットワークを調べることで、流量を増やせる経路を見つけることができないのかというアルゴリズム的なことを勉強したのですが、一部納得ができないところが合ったので書いて置こうと思います。 一番上のような残余ネットワークがあります。 1回目に流量3を流し、その結果が真ん中のような図になります。 2回目に流量1を流し、その結果が一番下のような図になります。 この時に、2回目の時に、C→Bに流すために、流量1を戻すと思うのですが、押し戻されることにより、B→Cの流量が1減ります。その際にC→Dの流量に影響はないのかなと疑問になりました。 やっていくうちに理解できるのかもしれないのですが、今の所疑問に思っていることなので書いておきました。解説していただけるのなら解説していただきたいで
