コーメンのアルゴリズム入門などでプッシュフローアルゴリズムを読んでいます。
私は以下のように言及されている補題26.20を理解するのに苦労しています：
G =（V、E）をソースsとシンクtを持つフローネットワークとし、fをGのプリフローとします。次に、オーバーフローする頂点uに対して、残りのネットワークGfにuからsへの単純なパスがあります。 。
このリーマのコンテキストを確認するには、次のリンクを参照してください。
http://integrator-crimea.com/ddu0164.html
これを理解するためにあなたの助けを求めてください。
お手数をおかけしますが、よろしくお願いいたします。
この最大フローのすべてを調べてからしばらく経ちましたが、これについて正しく考えている場合は、補題26.20が言っていることです。
明らかに、uに過剰があるため、s->uからのパスがあります。考えるべき補題の重要な部分は、u-> sからの単純なパスがあり、これは元のフローの反対方向であり、uでオーバーフローを引き起こします（フローはsで始まり、uに移動するため）。uにはオーバーフローがあるため、s-> uからの単純なパスがあり、パス全体に少なくとも1単位のフローがあります。c（a、b）= 1およびf（a、b）= 1である場合でも、c（a、b）= 0になります。ここで、aとbはすべてその単純なパスの頂点のペアであり、c（b、a） = c（b、a）-f（b、a）= 1-（-1）= 2（f（a、b）= -f（b、a）であるため）。したがって、その方向の容量に達する前に、そのエッジを介して2ユニットを押し戻すことができます（1は、すでに流れている1に対抗して、そのエッジ0を越えて流れ、もう1つは、そのエッジ1を越えて流れます）。
The reason you know it is a simple path is because if there was no simple path from s -> u there would be no flow at all through u. This is because even though there are non simple ways to reach u from s, there has to be at least one simple way or else all the flow would be caught in the non simple path which would mean none would be passing through u.
Picture this. Draw a flow graph where the source is completely cycled through a couple nodes. Is it possible to hit u (pick a node) without making a simple residual path back to s? Now try making one which has the flow maxed out in several edges all directed into u. Now try to find a simple path back to s. This may demonstrate what lemma 26.20 is saying. Some of those lemmas are pretty hard to understand, but once you really think about it, it will usually make sense. They just do a proof by contradiction to prove this which is the best way to formally prove what they are saying. Also, check the wiki page on this, it has some good insight as always! http://en.wikipedia.org/wiki/Push-relabel_maximum_flow_algorithm
Hope that makes some sense and I'm willing to work with you if it doesn't just let me know!