gm learning
gm learning
まず，下のアプレットの中で，適当にグラフを描いてください． そして，[全域木]ボタンをクリックします．
もし，何も起こらないようなら，ブラウザの下の方を見てください． 「このグラフは非連結です．」というメッセージが 表示されているはずです． これは，グラフがいくつかの塊（連結成分）に分離しているという意味です．
逆に，このメッセージがでなければ， グラフはひとつながりになっているでしょう． つまり，どの２つの頂点の間も， グラフの辺を乗り継いでいって，行き来することができます． そういう全体がつながっているグラフは連結であるといいます．
グラフが連結の場合には，何本かの辺は薄くなって， 残りは青くなります． 青い部分だけ注目すると， 木になっていますよ．
その木はグラフのすべての頂点を含んでいます． つまり，グラフの全域にまたがっている木なので， その木のことをグラフの全域木と呼びます．
もちろん，全域木は１つとはかぎりません． [全域木]を何回もクリックすれば，いろいろな全域木が現れます．
そのその木というは，閉路を含まないグラフでした． 一方，グラフには閉路がたくさん含まれていることがあります． ということは，連結なグラフの全域木を作るには， 閉路を壊すように，辺を取っていく必要がありますね．
逆に，全域木に乗っていない辺を全域木に追加すると， 閉路ができてしまうのです． 実際，どの薄い辺を青い全域木に追加して考えると， 閉路が１つ見つかるはずです．
こう考えていくと，全域木とは，連結グラフの中で，閉路を作らないように 可能なかぎり辺を選んでできるものだということができます．
最初に戻る