2者グラフ - 売り手と買い手

Question

複数の売り手と買い手がある場合、各売り手には商品の量があり、各買い手は売り手から複数の商品を購入したいと考えています。一部の売り手は一部の買い手と取引できません。買い手が十分な商品を手に入れることができない場合、取引は成功しません。すべてのバイヤーを満足させる戦略があることがわかっている場合、この戦略を見つける方法は？

問題を説明するグラフを描きますが、これは単なる例です。質問は、すべてのバイヤーが必要なだけの十分な製品を得ることができるように、各バイヤーのトランザクション戦略を提供することを望んでいます。 seller buyer example

Answer 1

1つのバイヤーが1つの売り手から複数のものを購入する可能性があります。 1つの項目に変更するのは難しくありません。

これは、最大フローアルゴリズムによって解決できます。バイヤーから接続された売り手への直接的なエッジ。それらのエッジに容量b_iを割り当てます。 B_iは買い手が必要とする金額です。 2つのノードS、Tを追加する。 Sからすべてのバイヤーにエッジを追加します。これらの各エッジに容量b_iを割り当てます。 B_iは買い手が必要とする金額です。各売り手の頂点からTにエッジを追加する。これらのエッジに容量S_iを割り当てる。 S_iは売り手が持っている金額です。 SからTまでの最大流量を求める。それがすべてのバイヤーに必要な金額の合計に等しい場合、問題の解決策が存在し、バイヤーから売り手までのすべての端を通過するフローの量によって見つけることができる（これは積分フロー定理のフォローアップです）。