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

木構造に残る経路の見極め

物理的につながっている区間と、スパニングツリーとして実際に使われる区間は必ずしも一致しません。問題で問われている隣接関係がどちらを指すのかを意識し、与えられた条件を丁寧に追って判断する姿勢が大切です。

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

この種の問題では、ネットワーク全体の配線図と、ループを避けるために選ばれた論理的な木構造とを頭の中で分けて考えることが求められます。区間コストがどの段階の判断材料になるかを自分で整理してから臨みましょう。

視点

ネットワークの図には、物理的に存在するすべての接続が描かれます。一方でスパニングツリーは、その中からループのない形になるように一部の区間だけを論理的に採用したものです。隣接関係を考えるときは、図に線があるかどうかだけで判断してはいけません。その区間が木の一部として扱われているかという視点で見直すと、混乱を防げます。

確認ポイント

• 問われている隣接関係が、物理的な接続と論理的な木構造のどちらを基準にしているかを確認する
• 区間コストなどの条件が、どの区間を木に含めるかの判断にどう関わるかを自分で整理する
• 結論を出したら、木の中にループが残っていないか、孤立した機器がないかを見直す

正解

エ

解説

Aをルートとして各ノードへの最小コスト経路を比較すると、AからB、BからE、EからC、EからDへ接続する構成になる。そのため、スパニングツリー上でDとEが隣接する。

理由

AからBへは1コスト、AからEへはA-B-Eを通って1＋2＝3コストとなり、直接のA-Eの4コストより小さい。CへはA-B-E-Cで1＋2＋1＝4コスト、DへはA-B-E-Dで1＋2＋3＝6コストとなる。したがって、親子関係はA-B、B-E、E-C、E-Dとなる。各値の単位は図のコスト単位です。

比較

この構成では、AとE、BとC、CとDも元のネットワーク上では辺で結ばれているが、ルートAからの経路コストを小さくする親辺としては採用されない。特にDはAから直接つなぐと7コストだが、Eを経由すると6コストで到達できるため、Dの親はEになる。

選択肢ア

これは不正解だよ。AとEは元のネットワーク上では直接接続されているが、そのコストは4コストである。一方、A-B-Eを経由すれば1＋2＝3コストとなるため、AからEへの親辺として直接のA-Eは選ばれない。

選択肢イ

これは不正解だよ。BとCは4コストで直接接続されているが、AからCへはA-B-E-Cを通ると1＋2＋1＝4コストで到達できる。B経由の直接辺を使う経路は1＋4＝5コストとなり、採用される親子関係とは異なる。

選択肢ウ

これは不正解だよ。CとDの直接辺は3コストだが、AからCまでの最小経路のコスト4コストに加えると、Dまで7コストになる。一方、A-B-E-Dなら1＋2＋3＝6コストなので、Dの親はCではなくEになる。

選択肢エ（正解）

これは正解だよ。AからDへは、A-B-E-Dを通ると1＋2＋3＝6コストで到達でき、A-Dの直接接続7コストより小さい。したがって、Dの親ノードはEとなり、スパニングツリー上でDとEが隣接する。

学習のポイント

ルート付き木では、辺の単純なコスト順ではなく、ルートからの経路と親ノードを比較する。