アンプラグドの学習9「マッディ市(最小全域木)」は、すべての家を最短で
結ぶ道を見つけるために試行錯誤する楽しい学習です。生徒はあれこれ頭
を悩ませながら、友だちと「いくつでできた？」などと情報交換しながら
最小の道を探して行きます。
授業では「敷石の数をいちばん小さくできた人は？」「その数はいくつ？」
「それはどんな道？」「ほかに違う道でできた人はいる？」などと質問し
ながらまとめていきます。
このとき、先生は最小の道を知っている必要がありますので、アンプラグ
ドの日本語版では追補(p114)にプリムのアルゴリズムを紹介しました。こ
のやり方を知っていると、学年等に合わせて問題をアレンジして難易度を
調整できますし、生徒が答えた数に「それが最小ですね」「惜しい、もう
少し短い道があるよ」などとアドバイスできます。
ここでは別の解法であるクルスカルのアルゴリズムを紹介します。
(ルール)
・辺の重み(数字)の小さい順に見て行きます。
・閉路(ループ)を作らないように注意します。
(手順)
・問題(上の左)をグラフの形にします。(上の真ん中)
・いちばん小さい重みである2の辺を選びます。これらは閉路でないので問題ありません。(上の右)
・次の3はたくさんあって、全部選ぶと閉路になってしまいます。そこで1個ずつ見て行きます。
・まず、選ばれていない2個のノード(頂点)を結ぶ辺を選びます。(下の左)
・これで、すべてのノードが選ばれた辺の両端になりました。
・続いて、すべての選ばれた辺がつながるように結んでいきます。まず、結び方が1通りしかない3の辺を結びましょう。(下の真ん中)
・最後に残りの辺を結びます。点は10個なので結ばれる辺は(10-1で)9本、つまりあと3本です。
・結び方は「△」「□」「◎」の辺はそれぞれ2通りあり、どちらを選んでも構いません。つまり、結び方は8通りあることがわかります。(下の右)
生徒は試行錯誤して「すべての家を結ぶ最短の道」を作ってくれます。
最短である長さ23の道を集めてみると、全部で8通りになりそうです。