加重有向グラフが与えられた場合、グローバルに最小のカット、つまり、削除された場合にグラフを 2 つの半分に分離し、他のそのようなカットと比較して総加重が最小になるエッジのセットを見つけたいと考えています。
さて、以下は機能しているように見えますが、その推論は間違っていると言われました。しかし、率直に言って、私にはその方法がわかりませんし、彼がどれほど確信を持っていたかもわかりません。
U,Vグローバルな最小カット (つまり、st-cut、 where ) によって分離されたノードのセットを考えてみましょうs in U, t in V。V注: からへ戻るエッジは気にしませんU。
任意u in U, v in Vの m について、uv-cut を よりも小さくすることはできません。それ以外のs-t-cut場合、st-cut は (グローバルに) 最小ではありません。同じ理由で、2 つの頂点間uまたは 2 つの頂点間のカットをV小さくすることはできません。
一方、UV カットを大きくすることはできません。それ以外の場合U->Vは、st カットの一部ではないエッジを含める必要があります。つまり、st カットはまったくカットされません。
したがって、s任意に修正して他のすべての頂点を反復するだけで十分ですx。sが inUの場合、sx-cut が大域的最小値に対応するのxは is inVの場合であり、xs-cut はsis inVおよびxis in の場合ですU。それらが両方とも同じセットの一部である場合、カットは少なくともグローバル最小値と同じくらい大きくなります (ただし、より大きくなる可能性もあります)。
したがって、両方を計算し、これまでに遭遇した最小カットを追跡することで、最終的にグローバル最小値を見つけます。
それは私には理にかなっているように思えました。私が間違っている？もしそうなら、なぜですか？