平成24年度秋期 ネットワークスペシャリスト 午前Ⅱ 問4

辺容量と流量を読む視点

ネットワーク図では、各辺が示す制約と、始点から終点へ進む量の関係を一度に判断せず、図の構造を整理してから全体の整合性を考えることが重要です。

この問題で問われていること

一つの辺だけで結論を出さず、始点・終点・中継点のつながりと、各辺に付された条件が流れ全体へどう影響するかを順に確認しましょう。

視点

まず図の向き、分岐と合流、各辺に示された条件の意味を整理し、局所的な制約が経路全体の成立可能性に関係する点へ注目します。

確認ポイント

• 辺の向きと接続関係を正確に読み取れているか
• 始点・終点・中継点の役割を区別できているか
• 個別の条件と全体の流れに矛盾がないか

正解

ウ

解説

この問題は、各論理回線をネットワークの流量として扱う最大流の問題です。10回線を流せる構成を示し、同時にそれ以上流せない切断を確認する。

実現可能性

10回線の流量配分例は、X-A=3、X-B=4、X-C=3、A-D=1、A-B=2、B-D=2、B-E=3、B-C=1、C-F=4、F-E=1、F-G=3、E-Y=3、E-G=1、D-Y=3、G-Y=4です。各辺の容量以下で、各中間地点の流入量と流出量も一致する。

上限の確認

X側をX・A・B・C、Y側をD・E・F・G・Yと分けると、境界を横切る辺はA-D=1、B-D=2、B-E=3、C-F=4です。したがって上限は、1回線＋2回線＋3回線＋4回線＝10回線となり、実現例と合わせて最大10回線です。

選択肢ア

これは不正解だよ。図の容量条件を満たす流量配分によって10回線を実際に構成できるため、8回線は最大値ではない。8という値になる別の計算過程は公式設問の条件から確定できず、少なくとも実現可能な流量より小さい。

選択肢イ

これは不正解だよ。最大流では経路の重複は禁止されず、共有辺の合計が容量以下ならよい。この条件で10回線の配分が可能なので、9回線は最大値ではない。9になる特定の誤計算過程は公式条件だけから断定できない。

選択肢ウ（正解）

これは正解だよ。X-A=3、X-B=4、X-C=3などの配分で、各辺の容量と中間地点の流量保存を満たしながら10回線を流せる。また、A-D、B-D、B-E、C-Fを横切る容量の合計は1＋2＋3＋4＝10回線であり、それ以上は流せない。

選択肢エ

これは不正解だよ。X・A・B・Cと残りの地点の間を横切る容量は、1回線＋2回線＋3回線＋4回線＝10回線である。この切断を同時に通過できる量が10回線に制限されるため、11回線は図の容量条件と一致しない。

学習のポイント

最大流では、実現可能な流量と上限となるカットを両方確認する。