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