多端末最大流問題

無向グラフ $G=(V,E)$， 枝上に定義された容量関数 $c: E \rightarrow \mathbf{R}$ に対して，すべての2点間の最大流（最小カット）を求める問題を多端末最大流問題 (multi-terminal maximum flow problem)とよぶ．

Gomory-Hu (1961) によるアルゴリズムによって，以下の性質を満たすフロー（Gomory-Hu)木 $T$ を得ることができる．

1. 任意の2点間 $s,t$ に対して， $G$ 上での最大流が $T$ 上で $s$ から $t$ に至るパスの最小の容量と一致する．

2. 木 $T$ の最小カット値が， $G$ の最小カット値と一致する．

R.E. Gomory and T.C. Hu, Multi-Terminal Networks Flows, Journal of the Society for Industrial and Applied Mathematics Vol. 9, No. 4 (Dec., 1961), pp. 551-570

import networkx as nx
import matplotlib.pyplot as plt

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()
# nx.draw(G, pos=pos,with_labels=True, node_size=1000)

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()

nx.minimum_cut_value(G, 2, 3, capacity="weight")

15