問題タブ [network-flow]

ネットワーク フローの問題は、線形計画法に帰着できることは誰もが知っています。ただし、ネットワーク フローの問題を解決する場合、フローは常に整数である必要があります。したがって、ネットワークフローは整数線形計画法に縮小する必要があると思います。NP 完全な ILP のおかげで、ネットワーク フローの問題も NP 完全な問題になるはずです。しかし、ネットワーク フローの実行時間は O(Cm) であるため、これは学んだことと矛盾します。どこが間違っていますか？ネットワークフロー問題の実行時間がナップザック問題(Wn)のように疑似多項式時間だからでしょうか? 私は今とても混乱しています！

どういうわけか、フローの値が最小カットの容量によって上限されるという特性の 1 つに違反しているように見えるこのグラフを作成しました。
グラフは次のとおりです。

アルゴリズムが見つける最大フローは 7 です
。
これでどこが間違っているのかわかりません。誰かがこれを修正できますか？

積分定理は、フロー ネットワークのすべての容量が整数である場合、すべての値が整数である最大フローがあることを示しています。

しかし、最も顕著な部分は存在であり、すべての最大フローではありません! つまり、このステートメントは、すべての最大フローが整数値であると主張しているわけではありません

すべての容量が整数の場合、理由がわかりませんが、整数値ではない最大フローが存在します!!

それとも、私に教えようとするこの定理について間違った考えを持っていたのでしょうか?

有向エッジと無向エッジを持つグラフに Max Flow アルゴリズムを実装 (またはライブラリが既に存在する場合は使用) し、それを視覚化することを検討しています。私はJavaScriptに傾倒しています。d3.js と arbor.js がインタラクティブなグラフの視覚化を可能にしていることは認識していますが、ノードからノードへの実際の流れを視覚化するための推奨される方法はありますか? これは、理論的なコンピューター サイエンスの概念を示すためのものです。

理想的なグラフは、エッジ キャパシティ、エッジ コスト (キャパシティとは異なります)、およびノー​​ド名を表示でき、エッジは一方向(有向) または双方向(双方向、両方のノードを指す矢印、または矢印なし) にすることができます。これは2 つの別個の有向辺ではありません)。

グラフの視覚化ツール (エッジからエッジへの流れを確認できるツール) に関するアドバイスをいただければ幸いです。

注: この種の視覚化を可能にする優れたフレームワーク/ライブラリを誰かが知っている場合、Python やその他の言語を使用することに反対しているわけではありません。

ありがとう。

アルゴリズムの解析について勉強しています。私は現在、Network Flowアルゴリズムについて読んでいます。最小コストのNetwork Flow発見に関するアルゴリズムの適用を検討しています。bipartite matchings

• G対応するネットワーク フローを使用してみましょうG'
• になろMうperfect matchingG
• このマッチングG<sub>M</sub>にresidual graph関連付ける

Jon Kleinberg と Eva Tardos のAlgorithm Design 7.13 on page 406 から、

Theorem 7.62状態:

(7.62) M を完全一致とする。G _Mに負のコスト有向サイクル C がある場合、M は最小コストではありません

この定理は理にかなっていますが、 abipartite flow network's residual graphの aperfect matchingが実際にサイクルをどのように含むことができるかについては混乱しています。サイクルを確認できる唯一の方法は、sinkまたはsourceが関係している場合です。

ただし、 にはperfect matching、sourceそこから出るエッジは含まれず、 にsinkは入るエッジは含まれません。また、内部ノードで発生するサイクルは、 a の定義と矛盾するように見えBipartite graphます。

誰かが残差グラフでそのようなサイクルの例を提供できますか?

私は現在、大学でフロー ネットワークを研究しており、私の教授はこの定理を私たちに提示しました。B(e) の ∑(e:u→v) - B(e') の ∑(e':v→u) | ≤ε。

注: この方程式は、すべての v (ネットワーク内のソースでもシンクでもない頂点) に対するものです。e:u→v は、カットセット内の u のセットから v のセットまでのすべてのエッジの B(e) の合計が必要であることを意味します。次に、e':v→u は次のことを意味します。 v のセットから u のセットまで、同じカットセット内にあるすべてのエッジの B(e) の合計が必要です。

グラフのすべてのエッジに対して |F(e)-B(e)|<ε*N (N はグラフの頂点の数) という新しいフロー F が存在します。」</p>

彼は証拠が存在すると主張しましたが、私はその真相を突き止めることができません。イプシロンの下限はグラフの最小カットであるという事実について考えていましたが、私が持っていた他のすべてのアイデアは役に立ちません。助けていただければ幸いです。その証拠をネットで探したのですが、見つかりませんでした。

事前に感謝します, または