1

グラフ内のすべてのカットを一覧表示するのに役立つ効率的なアルゴリズムを探しています。グラフはフロー ネットワーク (有向グラフ) であり、ソースとシンクが固定されています。片面にソース、もう片面にシンクがある可能なすべてのカット セットを調べたいと思います。

最小カットではなく、すべてのカット セットを見つけることが優先されることに注意してください。

たとえば、次のエッジ リストを持つグラフを考えてみましょう: s-->a-->t s-->b-->t

上記のグラフのカット セットは、{sa,sb}、{at,bt}、{sa,sb,at}、{sa,sb,bt}、{sa,sb,at,bt} です。

4

1 に答える 1

1

指数関数的な量のカットがあるため、効率的ではありません。ソースは S、シンクは T、ST はカットです。これについて考えてみてください: すべての頂点について、S または T にある可能性があります。すべての頂点を長い 2 進数と考えてください。ここで、1 は頂点 i が S にあることを意味し、0 は T にあることを意味します。

いくつのオプションがありますか? n 個の頂点がある場合、異なる 2 進数はいくつありますか? 答えは 2^n ですが、シンクとソースは無視できます。

于 2014-01-23T14:07:18.463 に答える