木
正式名称
Tree（ツリー）
一言でいうと
連結していて閉路を持たないグラフ
初心者向け説明
木とは、すべての頂点がつながっていて、閉路を持たないグラフです。
例えば、
A
/ \
B C
/ \
D E
は木です。
どの頂点へも移動できますが、一周して元の場所へ戻るような閉路はありません。
頂点がn個ある木では、
辺の数 = n - 1
という重要な性質があります。
ポイント
- 連結している
- 閉路を持たない
- n個の頂点なら辺はn−1本
- 任意の2頂点間の経路は1つ
関連用語
関連記事
- グラフ理論とは？サイクリックグラフや重み付きグラフを基礎から理解しよう
🍯 はちみつメモ
木 = 連結 + 閉路なし