G = (V, E) を s と t をソースとシンクとするネットワークとします。f を G の最大フローとします。G に一意の最小カットが存在するかどうかを判断するアルゴリズムを見つけます。
このサイトで同様の質問を見つけることができました：
そこに与えられた答えの要約：
残差グラフで s から到達可能なすべての頂点を見つけると、G の最小カット (S,T) が見つかりました。
t から始まる同じ残差グラフを見てください。矢印の逆方向に t から到達可能な頂点のグループ (つまり、t に到達できるすべての頂点) を見てください。
このグループもミニカットです。
そのカットが元のカットと同一である場合は、1 つしかありません。それ以外の場合は、2 つのカットが見つかっただけなので、元のカットが一意である可能性はありません。
カットが元のカットと同一である場合、そのカットがユニークである理由がわかりません。他に最小カットがないことを誰が約束できますか?
前もって感謝します
これまでのところ、元の投稿 (こことコピー元の投稿の両方) で提示されたアルゴリズムのすべての議論は、2 つの最小カットが同じである場合、それが一意の最小値であることを実際に証明するまでには至っていないようです。切る。しかし、これは難しいことではありません！
では、これら 2 つの最小カットとは何ですか? 最大フロー アルゴリズムを実行し、残差グラフを確認します。最初のカットは (S,T=VS) です。ここで、S は、残りの容量を持つエッジのみを使用してソースから到達できるすべてのノードのセットです。2 番目のカットは (VT,T) です。ここで、T は、余剰容量を持つエッジのみを使用してシンクに到達できるすべてのノードのセットです。
これら 2 つのカットが異なる場合、明らかに複数の最小カットが存在します。しかし、それらが同じである場合、laike9m で説明されている手法を使用して、これが唯一の最小カットであることを示すことができます。なんで？さて、前の段落の S と T の定義により、カット内の各エッジ e=(v0->v1) には、残余容量を持つパス s->v0 とパス v1->t が付属しています。したがって、e の容量を増やすと、最大フローが増えることがわかります。これはカット内のすべてのエッジ e に当てはまるため、この最小カットは一意であることを意味します。