algorithm - 辺素な経路を見つける (数ではなく、経路)

Question

有向グラフが与えられた場合、edmonds-karp または ford-fulkerson アルゴリズムを使用して、有向グラフ内のエッジ素路の最大数を見つけることができます。

G に k 個のエッジ独立パスがあるとします。多項式時間で実際のパスを見つけるにはどうすればよいでしょうか? 私の最良の選択は BFS で、パスが見つかったら、それらのエッジを使用済みとしてマークします。

どうもありがとう！

Answer 1

フロー分解を使用できます。こんなふうになります：

1. 開始ノードから深さ優先検索を実行し、ゼロまたは負のフローを持つエッジを無視しましょう。

2. ターミナル ノードに到達したら、開始ノードからターミナル ノードまでのパス上のすべてのエッジを通るフローから 1 を引き、それらを出力します (それらはパスを形成します)。

3. ターミナル ノードに到達できる限り、これを続けます。

各実行では多項式の時間を使用し、グラフから 1 つのパスを見つけて削除します。互いに素なパスの数は明らかに多項式であるため、このアルゴリズムは多項式の時間計算量を持ちます。

幅優先検索も使用できます (正でないフローのエッジを無視する必要があります)。