令和3年度春期 ネットワークスペシャリスト 午前Ⅱ 問4

辺容量と流量の対応を確認する視点

ネットワーク図では、各辺が表す上限と、始点から終点へ実際に通る量を分けて捉え、全体のつながりの中でどの関係を確認すべきかを整理します。数値を急いで計算する前に、用語と役割の対応を丁寧に確認しましょう。

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

一つの辺に注目し、その容量が示す意味と、経路上で扱われる流量との関係を確認してください。図全体では、始点から終点までの接続と各辺の役割を同じ基準で見比べます。

視点

容量と流量は関連する語ですが、図を読むときは「何を制限する情報か」「どの経路や区間に対応する情報か」を切り分けます。まず対象の辺と流れの向きを対応づけ、局所的な情報と全体の関係を混同しないように整理します。

確認ポイント

• 容量と流量が同じ対象を指しているか確認する
• 始点から終点までの経路と辺の対応を確認する
• 局所的な情報と全体の関係を分けて整理する

正解

ウ

解説

XからYへの最大流量は、X側とY側を分けるカットの容量合計で上限を定め、さらに各辺の容量と中継点の流量保存を満たす配分でその上限を実現できるか確認する。X，A，B，CをX側に置くと、A-D，B-D，B-E，C-Fの容量合計は1+2+3+4=10回線です。したがって最大値は10回線となる。

上限

X，A，B，Cを一方、D，E，F，G，Yを他方に分けると、境界を横切る辺はA-Dの1回線、B-Dの2回線、B-Eの3回線、C-Fの4回線です。したがってカット容量は1+2+3+4=10回線であり、XからYへ同時に流せる量は10回線以下です。

実現可能性

10回線は実際に配分できる。X-Aを3回線、X-Bを4回線、X-Cを3回線、A-Bを2回線、B-Cを1回線とする。さらにA-Dを1回線、B-Dを2回線、B-Eを3回線、C-Fを4回線とする。DからYへ3回線、FからEへ2回線・Gへ2回線、EからYへ3回線・Gへ2回線、GからYへ4回線とすれば、各中継点で流入量と流出量が一致し、全辺の容量以内で合計10回線がYへ到達する。

選択肢ア

これは不正解だよ。公式図の容量条件から、X，A，B，Cとそれ以外を分けるカットは1+2+3+4=10回線である。さらに各辺の容量以内で10回線を実現できるため、8回線は最大値ではない。8になる特定の計算過程は公式条件からは導けない。

選択肢イ

これは不正解だよ。10回線の実現可能な配分があり、カット容量もA-Dの1、B-Dの2、B-Eの3、C-Fの4の合計10回線である。したがって9回線は上限に達しておらず、公式図の容量条件と流量保存から最大値にはならない。

選択肢ウ（正解）

これは正解だよ。X，A，B，CをX側に置くカット容量は、A-D 1回線、B-D 2回線、B-E 3回線、C-F 4回線の合計1+2+3+4=10回線である。各辺の容量を守る流量配分でも10回線をYへ送れるため、最大値は10回線となる。

選択肢エ

これは不正解だよ。公式図では、X，A，B，CからD，E，F，G，Yへ出るカットの容量が1+2+3+4=10回線で、これを超える11回線は送れない。11という値を得るには、このカットの容量制約と矛盾するため、最大値にはならない。

学習のポイント

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