最近 DirectShow や GStreamer などのマルチメディアフレームワークを勉強している。これらの特徴を表すキーワードとして pipe-and-filter とか graph-based とか filter chains とかいろいろ出てくるのだが、どうやら filter graph という用語が一般的のようだ (wikipedia に項目としてあるという意味で)。
ところで、グラフという言葉でふと思い出したのが表題の「グラフ(Graph) と 木(Tree) の違い」。グラフ理論の教科書に書いてあるような厳密な定義はおいておいて、要するに一言で言うと違いは何という部分。私なら、
木は各ノードへの入力(親)が必ず一個しかない。そうじゃないのが(親が複数あれば)グラフ。
という説明をする。木をその特殊なケースの二分木のことだと理解していると、子の数や深さを説明に出してしまう。もちろん有向だとか無向だとか、閉路があるとかいろいろ定義はあるが、一言で言うなら親が何個かが一番当を得ていると思う。だから木の場合はノードの数が N 個ならエッジは (N-1) 個になる。
木を使った図はプログラミングに限らず組織図とかいろんな場面で目にするが、木じゃないのに木構造だと言っているのを何回か聞いたことがある。そういう意味ではグラフの方が集合が大きいので、なんでもグラフと呼んでおけば安全だが、木はやっぱり木と呼んでおきたい。
