gm learning

木

　植物が枝を伸ばして成長していくような形をしたグラフを木と呼びます．特に，注目する頂点を１つ指定して，そこから生えているように描いた木を 根付き木と呼びます．当然，その指定した頂点が根ですよ．

　次のアプレットは，その根付き木をランダムに生成します．頂点数を入力した後に, 何度も決定ボタンをクリックしてください．いろいろな根付き木が現れます．

　次のアプレットでは，平面格子上に広がって成長していく木をランダムに生成します．平面格子上のという制限があるので，頂点から出でいる辺の本数は４本以下になっています．

　どちらのアプレットでも，左下に表示される辺数は頂点数より１だけ小さい値になっています．

　というのも，初めに根が１つあって，そこから枝を伸ばすたび，辺とその先端の頂点が組になって増えていくので，頂点の方が根の分だけ１つ多いのです．つまり，頂点数が n の木の辺数は n-1 になります．

　誰でも木がどういうグラフなのかわかったでしょう．きっと，グラフを１つ見せられて，それが木なのかどうか判定ができるはずです．でも，正確に木とは何なのかを規定できないものでしょうか？