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

スパニングツリーとは

スパニングツリーとは、ネットワーク内のすべてのノードをループ（環状の経路）なしで接続する木構造のことです。「Aをルートノードとするスパニングツリー」は、起点となるノードAから各ノードへ至る経路の総コストが最小となるように構築されます。

正解の根拠

ノードAをルートとして、各ノードへの総コストが最小となる経路を順に確定してスパニングツリーを構築します。図のコストに基づき、次の手順で経路が決まります。

1. ノードBへの経路:
   ノードAから直接つながるノードのうち、最もコストが小さいのはノードBです（コスト1）。
   これにより「AとB」が隣接します。

2. ノードEへの経路:
   ノードAからEへ直接向かうとコストは4ですが、AからBを経由してEに向かう経路（A→B→E）の総コストは $1 + 2 = 3$ となり、直接向かうよりも小さくなります。
   これにより「BとE」が隣接します。

3. ノードCへの経路:
   ノードBから直接Cへ向かうと総コストは $1 + 4 = 5$ ですが、Eを経由してCへ向かう経路（A→B→E→C）の総コストは $3 + 1 = 4$ となり、より小さくなります。
   これにより「EとC」が隣接します。

4. ノードDへの経路:
   ノードAから直接向かうとコスト7、ノードCを経由すると総コスト $4 + 3 = 7$ です。一方、ノードEを経由する経路（A→B→E→D）の総コストは $3 + 3 = 6$ となり、これが最小の経路です。
   これにより「EとD」が隣接します。

構築されたスパニングツリーで隣接するノードの組み合わせは「AとB」「BとE」「EとC」「EとD」の4組です。この中に含まれるのは「DとE」です。

各選択肢の解説

• ア: AとEは、スパニングツリー上ではノードBを経由して接続されるため、隣接しません。

• イ: BとCは、スパニングツリー上ではノードEを経由して接続されるため、隣接しません。

• ウ: CとDは、スパニングツリー上では共通の隣接ノードであるEを経由して接続されるため、隣接しません。

• エ: DとEは、経路（A→B→E→D）の一部として直接接続されるため、隣接します。