全域木と最小全域木とは？
全域木と最小全域木とは、すべての頂点を閉路なく連結する部分グラフが全域木で、辺の重みの総和が最小になるものが最小全域木である。閉路を作らずに全拠点をつなぐ構造なので、ループを許さないLAN設計や、敷設コスト最小の配線計画の理論的な基礎になる。
ぜんいきぎとさいしょうぜんいきぎ
全域木と最小全域木の意味
すべての頂点を閉路なく連結する部分グラフが全域木で、辺の重みの総和が最小になるものが最小全域木である。閉路を作らずに全拠点をつなぐ構造なので、ループを許さないLAN設計や、敷設コスト最小の配線計画の理論的な基礎になる。
全域木と最小全域木の具体例
5拠点を結ぶ候補リンクごとに敷設費用を置き、最小全域木を求めれば最も安く全拠点をつなぐ組合せが得られる。ただし木構造はどこか1本切れると分断されるため、実務では最小全域木に冗長リンクを足したうえでループ対策を併用する。
全域木と最小全域木は試験でどう引っ掛けられる？
最小全域木は総コスト最小であって、任意の2頂点間が最短になるわけではない。最短経路木とは別物で、2拠点間の遅延が悪化することがある。同じ「木」でも最適化している対象が違う点が混同されやすい。
全域木と最小全域木と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。