グラフ理論の問題

難易度 4大学院入試の標準レベル大学数学グラフ理論

頂点集合
$V = {s, t, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, b_{1}, b_{2}, b_{3}, b_{4}, b_{5}}$
をもつ有向ネットワーク $N$ を考える。 $N$ の有向辺とその容量は次の $35$ 本である。
- $i = 1, 2, 3, 4, 5$ に対し、辺 $s \to a_{i}$ 。容量は順に $5, 5, 5, 1, 1$
- すべての $i, j \in {1, 2, 3, 4, 5}$ に対し、辺 $a_{i} \to b_{j}$ （ $25$ 本）。容量はすべて $1$
- $j = 1, 2, 3, 4, 5$ に対し、辺 $b_{j} \to t$ 。容量は順に $5, 5, 3, 2, 2$

$N$ における $s$ から $t$ への最大流の流量を求めよ。

この問題で使うもの

最大流最小カット定理（説明と入口の問題）
ネットワークと s-t カットの容量（説明と入口の問題）

この問題を解けるようになるまで（8 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

最大流最小カット定理を使い、 $s$ 側の頂点集合 $S$ に含まれる $a_{i}$ と $b_{j}$ の選び方でカットの容量を表しましょう。

ヒント 2

$S$ に含まれる $a_{i}$ の個数を $k$ とすると、各 $b_{j}$ については $S$ に入れたとき $q_{j}$ 、入れないとき $k$ の容量がかかるので、 $min (q_{j}, k)$ を足せばよくなります。

ヒント 3

容量が $5$ の辺 $s \to a_{1}, a_{2}, a_{3}$ の先の $3$ 頂点をまとめて $S$ に入れた $k = 3$ の場合を調べ、 $b_{4}, b_{5}$ の容量が小さいことに注目しましょう。あとはその値を実現するフローを作ります。

答えと解説

答えを見る

15

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$p = (p_{1}, \dots, p_{5}) = (5, 5, 5, 1, 1)$ 、 $q = (q_{1}, \dots, q_{5}) = (5, 5, 3, 2, 2)$ とおく。最大流最小カット定理より、最大流の流量は $s$ - $t$ カットの容量の最小値に等しい。

カットの容量の計算. $s$ を含み $t$ を含まない頂点集合 $S$ をとり、 $I = {i : a_{i} \in S}$ 、 $J = {j : b_{j} \in S}$ とする。 $S$ から $S$ の外へ向かう辺は
- $s \to a_{i}$ （ $i \in / I$ ）
- $a_{i} \to b_{j}$ （ $i \in I, j \in / J$ ）
- $b_{j} \to t$ （ $j \in J$ ）

なので、カットの容量は
$c (S) = i \in / I \sum p_{i} + ∣ I ∣ \cdot ∣ {1, \dots, 5} ∖ J ∣ + j \in J \sum q_{j}$
である。 $∣ I ∣ = k$ を固定すると、 $J$ については各 $j$ ごとに「 $j \in J$ なら $q_{j}$ 、 $j \in / J$ なら $k$ 」がかかるので最小値は $\sum_{j} min (q_{j}, k)$ 、 $I$ については $p_{i}$ の大きい $k$ 個を $I$ に入れるのが最小である。よって
$f (k) = (小さい方から 5 - k 個の p_{i} の和) + j = 1 \sum 5 min (q_{j}, k)$
の $k = 0, 1, \dots, 5$ での最小値が最小カットの容量である。 $p$ を小さい順に並べると $1, 1, 5, 5, 5$ なので
- $k = 0$ : $17 + 0 = 17$
- $k = 1$ : $(1 + 1 + 5 + 5) + 5 = 17$
- $k = 2$ : $(1 + 1 + 5) + (2 + 2 + 2 + 2 + 2) = 17$
- $k = 3$ : $(1 + 1) + (3 + 3 + 3 + 2 + 2) = 15$
- $k = 4$ : $1 + (4 + 4 + 3 + 2 + 2) = 16$
- $k = 5$ : $0 + (5 + 5 + 3 + 2 + 2) = 17$

最小は $k = 3$ のときの $15$ で、対応するカットは $S = {s, a_{1}, a_{2}, a_{3}, b_{4}, b_{5}}$ （容量 $1 + 1 + 3 \cdot 3 + 2 + 2 = 15$ ）である。よって最大流は $15$ 以下。

流量 $15$ のフローの構成. 次のように流す（使う辺 $a_{i} \to b_{j}$ にはそれぞれ $1$ を流す）。
- $a_{1} \to b_{1}, b_{2}, b_{3}, b_{4}, b_{5}$ 、 $a_{2} \to b_{1}, b_{2}, b_{3}, b_{4}, b_{5}$ 、 $a_{3} \to b_{1}, b_{2}, b_{3}$ 、 $a_{4} \to b_{1}$ 、 $a_{5} \to b_{2}$
- $s \to a_{i}$ の流量は順に $5, 5, 3, 1, 1$ （容量 $5, 5, 5, 1, 1$ 以下）
- $b_{j} \to t$ の流量は順に $4, 4, 3, 2, 2$ （容量 $5, 5, 3, 2, 2$ 以下）

各頂点で流量保存則が成り立ち、総流量は $5 + 5 + 3 + 1 + 1 = 15$ である。

以上より、最大流の流量は $15$ である。

別解

最大フロー最小カット定理を用いる。 $s$ 側に $s$ 、 $a$ の集合 $A$ 、 $b$ の集合 $B$ を含むカットの容量は
$i \in / A \sum c (s, a_{i}) + ∣ A ∣ (5 - ∣ B ∣) + j \in B \sum c (b_{j}, t)$
である。

上界（カット）: $A = {a_{1}, a_{2}, a_{3}}$ 、 $B = {b_{4}, b_{5}}$ とする。 $s \to a_{4}, a_{5}$ の容量は $1 + 1 = 2$ 。 $A$ から $B$ に入らない $b_{1}, b_{2}, b_{3}$ への辺は $3 \times 3 = 9$ 本で容量 9。 $b_{4} \to t, b_{5} \to t$ の容量は $2 + 2 = 4$ 。合計 $2 + 9 + 4 = 15$ 。よって最大流量は 15 以下。

下界（流れの構成）: $a_{1} \to b_{1}, b_{2}, b_{3}, b_{4}, b_{5}$ に各 1（計 5）、 $a_{2} \to b_{1}, b_{2}, b_{3}, b_{4}, b_{5}$ に各 1（計 5）、 $a_{3} \to b_{1}, b_{2}, b_{3}$ に各 1（計 3）、 $a_{4} \to b_{1}$ に 1、 $a_{5} \to b_{2}$ に 1。
各 $b_{j}$ への流入は $b_{1} : 4, b_{2} : 4, b_{3} : 3, b_{4} : 2, b_{5} : 2$ で、それぞれ $b_{j} \to t$ の容量 $5, 5, 3, 2, 2$ 以下。 $s \to a_{i}$ の流量は $5, 5, 3, 1, 1$ で容量 $5, 5, 5, 1, 1$ 以下。保存則も満たす。総流量は $5 + 5 + 3 + 1 + 1 = 15$ 。

よって最大流の流量は 15。
検算: 全容量の和は源側・吸い込み側とも 17 だが、 $a_{1}, a_{2}, a_{3}$ の各辺は容量 1 なので $b_{4}, b_{5}$ は 3 本の入力辺に制限され、 $b_{4}, b_{5}$ の容量が 2 のため、 $b_{1}, b_{2}$ （容量 5）に十分流せない構造により 17 に届かず、カット 15 と一致する。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる