エッジに沿ってフロー ボリュームを持つ有向グラフがあり、循環フローをすべて削除して単純化したいと考えています。これは、特定のサイクルの各エッジに沿って最小のフロー ボリュームを見つけ、その最小ボリュームによってサイクル内のすべてのエッジのフローを減らし、フローがゼロのエッジを削除することによって実行できます。すべての循環フローが削除されると、グラフは非循環になります。
たとえば、A→B から 1、B→C から 2、C→A から 3 のフローを持つ頂点 A、B、C を持つグラフがある場合、A→B からのフローなし、1 からのフローでこれを書き直すことができます。 B→C、C→Aから2。グラフ内のエッジの数が 3 から 2 に減り、結果のグラフは非循環になります。
この問題を解決するアルゴリズムはどれですか?
フロー分解定理(この max-flow の説明の§6.2 を参照)を使用すると便利な場合があります。この定理では、フローは一連のフロー パスとフロー サイクルに分解できるとされています。さらに、グラフ内のフロー パスとサイクルの総数は最大で m です。つまり、フロー サイクルを排除するための単純なアルゴリズムの 1 つは、グラフ内のすべてのフロー パスを見つけてから、フロー サイクルに対応する必要があるため、グラフ内の残りのフローをすべて削除することです。
フロー パスまたはサイクルを見つけるには、ソース ノードから単純な深さ優先検索を使用できます。ソース ノードから始めて、ターミナル ノードに到達するか、以前にアクセスしたノードにアクセスするまで、必要に応じてエッジをたどります。終点ノードにたどり着いた場合、たどったパスは単純なフロー パスです。いくつかのノードに 2 回遭遇した場合は、フロー サイクル (見つけたばかりのループによって形成された) を見つけたことになります。その後、グラフからフロー パス/サイクルを削除して繰り返すと、すべてのフロー パスとサイクルを検出することになります。ソース コードから流れを運ぶエッジがなくなったら、完了です。フロー パスを見つけるたびに、そのすべてのエッジを横切る合計フローを記録すると、フロー パスがなくなるまでこれを繰り返すことで循環フローをなくすことができます。
各 DFS には O(m + n) の時間がかかり、多くても O(m) のフロー パスがあるため、このステップの合計実行時間は O(m 2 + mn) であり、これはグラフのサイズの多項式です。
お役に立てれば！
与えられたフローの値を計算し、V与えられたネットワークとフロー値の最小コスト フロー問題を解いて、各エッジにVコストを割り当てることができます。1
その場合、(コストに関して) 最適ではないため、結果のフローにサイクルが含まれないようにする必要があります。
トポロジカルソートを使用できます http://en.wikipedia.org/wiki/Topological_sorting
有向グラフでサイクルを見つける場合に最適です
最小全域木を作成することを考えたことがありますか? そのためにダイクストラのアルゴリズムを使用できます。グラフが周期的かどうかを最初に調べたい場合は、トポロジカル ソートを使用して判断できます。