import networkx as nx
import matplotlib.pyplot as plt
G = nx.DiGraph()
capacity = {(0, 1): 5, (0, 2): 8, (1, 4): 8, (2, 1): 2, (2, 3): 5, (3, 4): 6}
for (i, j) in capacity:
G.add_edge(i, j, capacity=capacity[i, j])
pos = {0: (0, 1), 1: (1, 2), 2: (1, 0), 3: (2, 0), 4: (2, 2)}
edge_labels = {}
for (i, j) in G.edges():
edge_labels[i, j] = f"{ G[i][j]['capacity']}"
plt.figure()
nx.draw(G, pos=pos, with_labels=True, node_size=1000)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
最大流問題は，最短路問題と並んでネットワーク理論もっとも基本的な問題のひとつであり， 水や車などをネットワーク上に流すという直接的な応用の他にも， スケジューリングから分子生物学にいたるまで多種多様な応用をもつ．
最短路問題の目的は，ある尺度を最適にする「パス（路）」を求めることであったが， 最大流問題や最小費用流問題の目的は， ある尺度を最適にする「フロー（流）」を求めることである．
最大流問題を，グラフ・ネットワークの用語を使って定義しておこう．
最大流問題（maximum flow problem）
$n$個の点から構成される点集合 $V$ および $m$ 本の枝から構成される枝集合 $E$， $V$ と $E$ から成る有向グラフ $G=(V,E)$， 枝上に定義される非負の容量関数 $u: E \rightarrow \mathbf{R}_+$， 始点 $s \in V$ および終点 $t \in V$ が与えられたとき， 始点 $s$ から終点 $t$ までの「フロー」で， その量が最大になるものを求めよ．
上の問題の定義を完結させるためには，「フロー」を厳密に定義する必要がある．
フロー（flow）とは枝上に定義された実数値関数 $x: E \rightarrow \mathbf{R}$ で， 以下の性質を満たすものを指す．
フロー整合条件: $$ \sum_{j: ji \in E} x_{ji} - \sum_{j: ij \in E} x_{ij} =0 \ \ \ \forall i \in V \setminus \{s,t\} $$
容量制約と非負制約: $$ 0 \leq x_{e} \leq u_{e} \ \ \ \forall e \in E $$
各点 $i \in V$ に対して関数 $f_x(i)$ を $$ f_x(i) = \sum_{j: ji \in E} x_{ji} - \sum_{j: ij \in E} x_{ij} $$ と定義する．これはフローを表すベクトル $x$ によって定まる量であり， 点 $i$ に入ってきた量 $\sum_{j: ji \in E} x_{ji}$ から出ていく量 $\sum_{j: ij \in E} x_{ij}$ を 減じた値であるので，フロー $x$ の点 $i$ における超過（excess）とよばれる．
最大の値をもつフロー $x$ を求めることが最大流問題の目的である． 最大流問題を線形最適化問題として定式化すると以下のようになる．
$$ \begin{array}{l l} maximize & f_x(t) \\ s.t. & f_x(i) =0 \ \ \ \forall i \in V \setminus \{s,t\} \\ & 0 \leq x_{e} \leq u_{e} \ \ \ \forall e \in E \end{array} $$最大流問題は，networkXのmaximum_flow関数で簡単に解くことができる．
value, flow = nx.maximum_flow(G, _s=0, _t=4)
print("value=", value)
flow
edge_labels = {}
for (i, j) in G.edges():
edge_labels[i, j] = flow[i][j]
plt.figure()
nx.draw(G, pos=pos, with_labels=True, node_size=1000)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
最小カット問題
始点 $s$ を含み，終点 $t$ を含まない点の部分集合 $S$ を考える． $S$ から出て $S$ 以外の点に向かう枝の集合をカット(cut)とよび， $$ \delta(S) = \{ (i,j)~|~(i,j) \in E, i \in S, j \not\in S \} $$ と書くことにする．カットに含まれる枝の容量の合計をカット容量とよぶ．
始点 $s$ から終点 $t$ までは，（どんなにがんばっても）カット容量より多くのフローを 流すことはできないので，カット容量はフロー量の上界を与えることがわかる．
すべての可能なカットに対して， カット容量を最小にするものを求める問題は，最小カット問題(minimum cut problem)とよばれる．
最小カット問題は，最大流問題の双対問題であり，以下の線形最適化問題として定式化できる．
$$ \begin{array}{l l l } minimize & \sum_{(i,j) \in E} u_{ij} z_{ij} & \\ s.t. & y_i - y_j \leq z_{ij} & \forall (i,j) \in E \\ & y_s =1, y_t = 0 & \\ & z_{ij} \geq 0 & \forall (i,j) \in E \\ & y_i \in \mathbf{R} & \forall i \in V\setminus \{s,t\} \end{array} $$最大流問題と最小カット問題には，以下の関係（最大フロー・最小カット定理）がある．
最大のフロー量と最小のカット容量は一致する．
実際に，networkXのminimum_cut関数で最小カットを求めて確認する．
value, cut = nx.minimum_cut(G, _s=0, _t=4)
print("value=", value, "cut=", cut)
多端末最大流問題
無向グラフ $G=(V,E)$， 枝上に定義された容量関数 $c: E \rightarrow \mathbf{R}$ に対して，すべての2点間の最大流（最小カット）を求める問題を多端末最大流問題 (multi-terminal maximum flow problem)とよぶ．
Gomory-Huによるアルゴリズムによって，以下の性質を満たすフロー（Gomory-Hu)木 $T$ を得ることができる．
任意の2点間 $s,t$ に対して， $G$ 上での最大流が $T$ 上で $s$ から $t$ に至るパスの最小の容量と一致する．
木 $T$ の最小カット値が， $G$ の最小カット値と一致する．
G = nx.Graph()
G.add_weighted_edges_from(
[
(0, 1, 10),
(0, 2, 8),
(1, 2, 3),
(1, 3, 6),
(1, 4, 2),
(2, 3, 2),
(2, 4, 3),
(2, 5, 2),
(3, 4, 4),
(3, 5, 5),
(4, 5, 7),
]
)
pos = {0: (0, 1), 1: (1, 2), 2: (1, 0), 3: (2, 2), 4: (2, 0), 5: (3, 1)}
edge_labels = {}
for (i, j) in G.edges():
edge_labels[i, j] = str(G[i][j]["weight"])
plt.figure()
nx.draw(G, pos=pos, with_labels=True, node_size=1000)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
T = nx.gomory_hu_tree(G, capacity="weight")
edge_labels = {}
for (i, j) in T.edges():
edge_labels[i, j] = str(T[i][j]["weight"])
plt.figure()
nx.draw(T, pos=pos, with_labels=True, node_size=1000)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.show()
点2と3の間の最小カットを求め，確認する．
nx.minimum_cut_value(G, 2, 3, capacity="weight")