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

ネットワーク流量を考える視点

ネットワーク図を読むときは、各辺の容量と流量を個別に見るだけでなく、始点から終点までの経路全体で条件がどう関係するかを整理し、局所的な制約と全体の整合性を分けて確認します。

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

今回の確認点は、図中の各接続に割り当てられた容量と、経路上を通る流量の関係を、向きや合流・分岐にも注意しながら一貫した単位で捉えられているか、という一点です。

視点

容量、流量、接続の向き、経路のつながりをそれぞれ整理し、局所的な関係と始点から終点までの全体像を混同しないように確認します。

確認ポイント

• 容量と流量の単位や比較対象がそろっているか確認する
• 始点から終点までの経路と接続の向きを整理する
• 合流や分岐を含め、局所条件と全体の整合性を分けて見る

正解

ウ

解説

これはネットワークの最大フローを求める問題です。A-D、B-D、B-E、C-Fを境界リンクとして見ると、容量は1、2、3、4回線であり、合計は1＋2＋3＋4＝10回線となる。この境界を同時に通過できる回線数が10回線に制限される一方、各リンク容量を超えない10回線の流し方も構成できるため、最大値は10回線です。

理由

X側とY側の間を、A-D、B-D、B-E、C-Fの4リンクが横切るように分けると、それぞれの容量は1回線、2回線、3回線、4回線です。したがって、この境界を通過できる合計は、1＋2＋3＋4＝10回線となり、10回線を超えることはできない。

実現性

10回線は、例えばA-Dに1回線、B-Dに2回線、B-Eに3回線、C-Fに4回線を流す構成を基礎に、各地点内のリンクへ分配できる。C-Fの4回線はF-Eへ2回線、F-Gへ2回線とし、EとGからYへ送ることで、図の各容量を超えずに合計10回線を実現できる。

選択肢ア

これは不正解だよ。8回線は、図のネットワークで実現できる同時回線数の最大値ではない。A-D、B-D、B-E、C-Fを横切る容量の合計は10回線であり、各リンク容量を超えない10回線の分配も可能であるため、8回線では上限を正しく表していない。提示情報だけでは、8という値になった誤計算の過程までは特定できない。

選択肢イ

これは不正解だよ。9回線も最大値より1回線少ない値である。境界となる4リンクの容量は1回線、2回線、3回線、4回線で、合計は10回線となる。さらに、リンクごとの容量制限を守って10回線を流せるため、9回線を最大値とする根拠は公式図の条件と一致しない。

選択肢ウ（正解）

これは正解だよ。A-D、B-D、B-E、C-Fの容量はそれぞれ1回線、2回線、3回線、4回線であり、境界容量は1＋2＋3＋4＝10回線となる。この上限を超えることはできず、C-Fの4回線をF-EとF-Gへ分けるなど、各リンク容量を守って10回線をYへ送れるため、最大値は10回線である。

選択肢エ

これは不正解だよ。11回線は、始点側と終点側を分ける境界の容量上限を1回線超えている。A-D、B-D、B-E、C-Fを横切る容量は合計で1＋2＋3＋4＝10回線なので、どの経路を選んでもその境界を11回線が同時に通過することはできない。したがって11回線は実現不能である。

学習のポイント

最大フローでは、経路の組合せだけでなく、容量カットによる上限と実現可能性を確認する。