問題タブ [max-flow]

BSDライセンスを持つ最大フロー/最小カット計算（できればBoykov-Kolmogorovを使用）を実行するための高速cython / pythonライブラリはありますか？

軽量のCライブラリも便利です。

次のリンクでプッシュフローアルゴリズムを読んでいます。

http://community.topcoder.com/tc?module=静的&d1=チュートリアル&d2=maxflowPushRelabel

超過フロー - 超過フロー e を e(u) = f(V,u)、u への正味フローと定義します。e(u) > 0 の場合、頂点 u ∊ V-{s,t} はオーバーフロー/アクティブです。

単純なフローネットワークの例を探しています e(u) をどのように計算しますか?

お時間をいただきありがとうございます。

V wrt の頂点の有効なラベル付け。プリフロー x は関数 d[.] : V -> Z を満たす:

d[s] = n ^ d[t] = 0

すべての (v,w) は E に属します: d[v] <= d[w] + 1

(s と t) を含む 4 つの頂点があるとします。

d[s] = 4

有効なラベル付けによれば、d[v] <= d[w]+1 である必要がありますが、「s」に由来するエッジの場合、4 <= 1 は false であるため有効ではありません。このロジックはソースだけではありませんか？

私はそれを正しく理解していますか？私を修正してください。

お時間をいただきありがとうございます。

コーメンのアルゴリズム入門などでプッシュフローアルゴリズムを読んでいます。

私は以下のように言及されている補題26.20を理解するのに苦労しています：

G =（V、E）をソースsとシンクtを持つフローネットワークとし、fをGのプリフローとします。次に、オーバーフローする頂点uに対して、残りのネットワークGfにuからsへの単純なパスがあります。 。

このリーマのコンテキストを確認するには、次のリンクを参照してください。

http://integrator-crimea.com/ddu0164.html

これを理解するためにあなたの助けを求めてください。

お手数をおかけしますが、よろしくお願いいたします。

無向グラフ G = (V, E) が与えられた場合、G のエッジは非負の重みを持ちます。

[1] 2 つのノード s と t の間のすべてのエッジ独立パスと等コスト パスを見つける方法は?

[2] 2 つのノード s と t の間のすべてのエッジ独立パスを見つける方法は?

[3] 2 つのノード s と t の間のすべての頂点分離パスと等コスト パスを見つける方法は?

[4] 2 つのノード s と t の間のすべての頂点分離パスを見つける方法は?

代わりに近似アルゴリズムはありますか?

学級試験で問題が出題されました。ある図書館では、各メンバーが 4 冊の本をリクエストし、各本は 2 人のメンバーのみによってリクエストされました。この情報は、二部グラフ G = ( X + Y , E ) の形式で与えられます。

X : すべてのメンバーのセット Y : すべてのブックのセット エッジ E = エッジのセット (x,y) ここで、x はブック y に対して要求されたメンバーです。私たちは、司書が各メンバーに最大 2 冊の本を与えて、最大のメンバーが満足できるようにする方法を見つけなければなりません。

私は2つのアプローチを思い付きました：

1. 2 つの新しい頂点 s(ソース) と t(デスティネーション) を導入します。s から X のすべてのメンバーに容量 2 でエッジを導入します。すべてのエッジ E は容量 1 を持ち、新しいエッジ Y から t は容量 1 を持ちます。ここで最大フロー アルゴリズムを適用して、最大の一致を見つけます。最大マッチングが必要なソリューションです。
2. もう 1 つの方法は、同じエッジを導入することによって上記と同じアルゴリズムに従うことですが、各エッジの容量は 1 です。次に、最大一致を見つけます。このマッチングは、最大会員数に1冊の本をプレゼントします。一致した書籍を削除し、上記のアルゴリズムを再度適用します。一致した本と 2 冊の本を持っているメンバーを再度削除し、X と Y の間にエッジがなくなるまでアルゴリズムを適用します。達成されたソリューションは、必要なソリューションです。

アルゴリズムを超えましたが、どちらが正しいか、どれも正しくないかわかりません。他のアルゴリズムがある場合は、ここで提案してください。

多くの小さなDAGS（8〜12ノード、20〜60エッジ）の最小カット問題を非常に迅速に解決したいと思います。最善の解決策は、最大フローを解き、そこからカットを推定することであるように見えます。理論的および経験的タイミング比較の両方が利用可能な最大フローアルゴリズムはかなりありますが、これらはすべて、グラフがどんどん大きくなるにつれてパフォーマンスが興味深いことを前提としています。また、使用される複雑なデータ構造のセットアップ時間は非常に長くなる可能性があることもよく言われます。それで、注意深く最適化された実装（おそらくC ++で）を考えると、どのアルゴリズムが小さなグラフでの初期化と実行に最も速いことがわかりますか？（私の素朴な仮定は、エドモンズ・カープはおそらくデータ構造の点で同じくらい単純なので、より複雑なアルゴリズムを打ち負かすだろうということですが、それは単なる推測です。）

質問に飛び込む前に、私がすでに持っているものの背景情報をいくつか示します。

-最初に、エッジの重みが計算された距離である米国中の都市に基づいて、無向隣接行列グラフを作成しました (距離式によって達成されました)。

-Prim のアルゴリズムを使用して、最小スパニング ツリーも実装しました。

今、私が持っている Edmonds Karp 最大フロー アルゴリズムを実装する必要がありますが、次のコードで使用されるアルゴリズムを実装するために、私が持っているデータに基づいて容量グラフを作成する方法について混乱しています:

どんな助けでも大歓迎です、ありがとう!

I've thus far been working with graphs whose vertices have only one directed edge between them. For all the examples I've used to test my implementation, the right answer has been produced. When I use a graph containing vertices which have an edge running both directions, however, I don't produce the right answer. I've been treating such an edge running backward as the backflow between those two vertices, as it seems that the backflow and a different "pipe" running backward would end up being equivalent. Is my assumption here wrong?

有向加重グラフが与えられた場合、頂点のすべてのペア間の最大フロー(または最小エッジ カット) を見つける方法。
単純なアプローチは、ペアごとにの複雑さを持つ Dinic のようなMax Flowアルゴリズムを呼び出すだけです。 したがって、すべてのペアで です。O((V^2)*E)
O((V^4)*E)

O((V^3)*E)いくつかO(V^3)の最適化によって複雑さを軽減することは可能ですか?