循環の問題

循環問題とその変種は、ネットワークフロー問題の一般化であり、エッジフローに下限制約が課され、ソースとシンクにもフロー保存則が求められる（つまり、特別なノードは存在しない）という制約が追加されている。問題の変種では、ネットワークを流れる複数の商品と、フローにコストが課される。

意味

次のようなフロー ネットワークが与えられます。 ${\displaystyle G(V,E)}$

${\displaystyle l(v,w)}$ 、ノードからノードへのフローの下限、${\displaystyle v}$ ${\displaystyle w}$

${\displaystyle u(v,w)}$ 、ノードからノードへのフローの上限、${\displaystyle v}$ ${\displaystyle w}$

${\displaystyle c(v,w)}$ 、フロー単位のコスト${\displaystyle (v,w)}$

そして制約:

${\displaystyle l(v,w)\leq f(v,w)\leq u(v,w)}$ 、

${\displaystyle \sum _{w\in V}f(u,w)=0}$ (フローはノード内で現れたり消えたりすることはできません)。

制約を満たすフロー割り当てを見つけることで、与えられた循環問題の解決策が得られます。

問題の最小コスト変種では、最小化する。

${\displaystyle \sum _{(v,w)\in E}c(v,w)\cdot f(v,w).}$

多品目循環

複数商品の循環問題では、個々の商品の流れも追跡する必要があります。

${\displaystyle \,f_{i}(v,w)}$	からへの商品の流れ。 ${\displaystyle i}$ ${\displaystyle v}$ ${\displaystyle w}$
${\displaystyle \,f(v,w)=\sum _{i}f_{i}(v,w)}$	総流量。

各商品の流れにも下限があります。

${\displaystyle \,l_{i}(v,w)\leq f_{i}(v,w)}$

保全制約は商品ごとに個別に遵守されなければなりません。

${\displaystyle \ \sum _{w\in V}f_{i}(u,w)=0.}$

解決

循環問題に対しては、多くの多項式アルゴリズムが開発されてきた（例えば、Edmonds–Karpアルゴリズム、1972年；Tarjan 1987-1988年）。Tardosは最初の強多項式アルゴリズムを発見した。^[1]

複数の商品がある場合、整数フローでは問題はNP完全である。^[2]分数フローの場合は、問題を線形計画法として定式化できるため、多項式時間で解くことができる。

関連する問題

以下にいくつかの問題と、上記の一般的な循環設定を使用してそれらを解決する方法を示します。

• 最小コストの複数商品循環問題 - 上記のすべての制約を使用します。
• 最小費用循環問題 - 単一商品を使用する
• 複数商品の循環 - コストを最適化せずに解決します。
• シンプルな循環 - 商品を 1 つ使用するだけなので、コストはかかりません。
• 複数商品フロー-からへの商品の需要を表す場合、すべての商品 についてのエッジを作成します。他のすべてのエッジについては とします。${\displaystyle K_{i}(s_{i},t_{i},d_{i})}$ ${\displaystyle d_{i}}$ ${\displaystyle i}$ ${\displaystyle s_{i}}$ ${\displaystyle t_{i}}$ ${\displaystyle (t_{i},s_{i})}$ ${\displaystyle l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}}$ ${\displaystyle i}$ ${\displaystyle l_{i}(u,v)=0}$
• 最小コストの複数商品フロー問題- 上記と同じですが、コストを最小化します。
• 最小費用フロー問題- 上記と同様、商品が 1 つあります。
• 最大フロー問題- すべてのコストを 0 に設定し、、∞、を使用してシンクからソースへのエッジを追加します。${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle l(t,s)=0}$ ${\displaystyle u(t,s)=}$ ${\displaystyle c(t,s)=-1}$
• 最小費用最大流量問題- まず最大流量を求めます。次に、 と を使って解きます。${\displaystyle m}$ ${\displaystyle l(t,s)=u(t,s)=m}$ ${\displaystyle c(t,s)=0}$
• 単一ソースの最短経路-グラフ内のすべてのエッジを およびとし、およびを持つエッジを追加します。${\displaystyle l(u,v)=0}$ ${\displaystyle c(u,v)=1}$ ${\displaystyle (t,s)}$ ${\displaystyle l(t,s)=u(t,s)=1}$ ${\displaystyle c(t,s)=0}$
• 全ペア最短経路- すべての容量を無制限とし、ノードのペアごとに 1 つの商品に対してフロー 1 を見つけます。${\displaystyle v(v-1)/2}$

参考文献

1. Éva Tardos (1985). 「強力多項式最小コスト循環アルゴリズム」. Combinatorica . 5 (3): 247– 255. doi :10.1007/BF02579369.
2. S. Even、A. Itai、A. Shamir (1976). 「時刻表と複数商品フロー問題の複雑性について」SIAM Journal on Computing . 5 (4). SIAM: 691– 703. doi :10.1137/0205048. 2013年1月12日時点のオリジナルよりアーカイブ。