Edmonds-Karpフロー容量のノードを持つグラフのアルゴリズム

Question

私はこのアルゴリズムを有向グラフに実装しています。しかし、このグラフノードに関する興味深い点は、独自のフロー容量も持っています。私は、元の問題のこの微妙な変更を特別な方法で処理しなければならないと考えています。元々の最大流量問題では、最初から最後までパスを見つけることは大丈夫でした（実際には、Edmonds-Karpアルゴリズムでは、BFSを実行し、最後のノードに到達する最初のパスを選択する必要があります）私たちは「このパス選択」の仕事にもっと注意する必要があります。元のアルゴリズムを実装し、max-flowよりも小さなフロー値を得ていることがわかったので、このノード容量制限と関係があるのか​​どうかは疑問です。

私はこれに多くの努力を払い、自己ループを追加することによってノードに容量制限のないグラフに初期グラフを変換するような考えを思いつきました（各ノードに自己ループを追加し、 - 経路上の各ノードのループ）、または重みが初期のノード容量の制約を上回る仮想ノードとエッジを追加することです。しかし、これらのどれもがこの問題の解決策であるとは確信していません。

どんな考えでも大歓迎です。

ありがとうございます。あなたのグラフのすべての頂点vについては

、2つの頂点v_inとv_outと交換してください：

Answer 1

通常の最大フロー問題へのノード容量の最大フローの問題から、単純な減少があります。すべての受信エッジはvに、v_inを指し、vからのすべての送信エッジはv_outを指す必要があります。次に、v_inからv_outまで1つの追加エッジを作成し、容量はc_v、頂点の容量はvです。

したがって、変換したグラフでEdmunds-Karpを実行するだけです。

s --> v_in --> v_out --> t 
    1  2   1 

：

s --> v --> t 
    1 2 1 

これは、最大フロー問題においてこのグラフに対応するであろう：

それでは、あなたはあなたの問題で以下のグラフを持っているとしましょう（頂点vは容量2を持っています）得られる最大流量が解であることは明らかである（そして、どちらかを証明することは特に困難ではない）。