最初の頂点から最後の頂点までのすべてのパスに表示される、グラフ内のエッジの最小数を見つける必要があります。たとえば、画像では、最初の頂点がV0で、最後の頂点がV8の場合、V0からV8までのすべてのパスに表示される頂点の最小数は2であり、緑色（またはV6-V8の代わり）の頂点です。 V0-V3またはV3-V6である可能性があります）。
画像の例：
しばらく検索してきましたが、これを行うためのアルゴリズムが見つかりません（または考えられません）...
質問する
654 次
1 に答える
0
あなたの質問は、グラフで最小の st カットを見つけることと同じです。このカットは、削除された場合に s と t を切断するエッジの最小セットを与えるためです。これは、すべてのパスが最小カットのエッジを通過すると言っているのと同じです。
最小 st カットを見つけるアルゴリズムは多数あります。たとえば、最大フロー最小カット定理は、s から t への最大フローの値 (各エッジに単位容量がある場合) は、最小 st カットのエッジ数と同じフローを持つと述べています。したがって、Ford-Fulkerson や Edmonds-Karp などの最大フロー アルゴリズムを使用して、最小カットのコストを直接計算できます。そこから、残差グラフで s から到達可能なすべてのエッジを見つけ、このセットに 1 つのエンドポイントがあり、補数に別のエンドポイントがあるすべてのエッジを取得することで、最小カットを簡単に回復できます。
お役に立てれば！
于 2013-01-22T08:07:48.407 に答える