問題 No.6537
頂点A、B、C、Dの4つの頂点と、それらを結ぶ無向の辺からなるグラフがある。各辺の重み（コスト）が、辺(A, B) = $2$、辺(A, C) = $4$、辺(A, D) = $1$、辺(B, C) = $3$、辺(B, D) = $5$、辺(C, D) = $6$であるとき、このグラフの最小全域木の重みの総和はいくつになるか。
【正解の解説】
6
これは複数の拠点を最小限の水道管ですべて繋ぐ工事のようなものです。一番安い辺(A,D)の1、次に安い辺(A,B)の2、そして辺(B,C)の3を選びます。これで全ての頂点A,B,C,Dがループなしで繋がり、1+2+3=6となります。
スポンサーリンク
【その他の選択肢の解説】
5
試験では正しい手順を踏まずに適当に小さな辺を選んだり、計算ミスを誘うためにこのようなダミーの数値が用意されています。全域木はすべての頂点が必ず一筆書きのように接続される必要があり、辺の数や選び方のルールを無視するとこの値になってしまいます。
7
最小全域木を作る際、4つの頂点をつなぐために必要な辺の数は「頂点数 - 1」の3本です。もし4本以上の辺を選んでしまうと木ではなくなり、ループ（閉路）ができてしまいます。コストの大きい辺をうっかり混ぜてしまうと、このように正解より大きい数値になってしまいます。
10
すべての辺を網羅するのではなく、最小限のコストですべての頂点を繋ぐのが全域木の目的です。全部の辺をつなぐと通信網でいう二重投資や無駄なルートが発生するため、最もコストがかかる最悪のパターンを計算するとこの数値になってしまいます。