11/1 学生ゼミ

| コメント(0) | トラックバック(0)

今更ながら記録。

2.4 TREES を読む。
ものすごく簡単にまとめ。

・directed acyclic graph
 閉路を持たない有向グラフ。

・(directed) tree (rooted tree)
 1. root(根)と呼ばれる頂点を一つだけ持つ。根に入る辺は無い。
 2. 根を除くどの頂点も、入る辺を一つだけ持つ(親が一つだけ)。
 3. どの頂点にも根からの経路がある(一つだけ)。
 を満たすdirected acyclic graph。

・forest
 木の集まり。森。

(v, w) is in E → vはwのfather(parent)、wはvのson(child)。
vからwへのpathがあるとき、vはwのancestor、wはvのdescendant。
 さらにv != wなら、vはwのproper ancestor(真の祖先)、wはvのproper descendant(真の子孫)。
proper ancestorを持たない頂点はleaf。
vとそのすべてのdescendantsをsubtreeという。vはsubtreeのroot。

depth of a vertex
height of a vertex
height of a tree
level of a vertex

ordered tree
 子が順序を持つ
binary tree
 子が左と右のどちらかに区別され、それ以外の子を持たないorderd tree。
 深さがkより小さな頂点はすべて左と右の子を持ち、深さがkの頂点がすべてleafであるとき、complete。
   ちょうど2^(k+1)-1個の頂点を持つ。

traverse
preorder
  自分、子の順。
postorder
  子、自分の順。
inorder(binary treeのみ)
  左の子、自分、右の子の順。

undirected tree
 connected(連結・任意の2頂点間にpathが存在する)でacyclicなundirected graph
 rooted undirected treeはある頂点をrootとして区別したもの。

トラックバック(0)

トラックバックURL: http://www-ikn.ist.hokudai.ac.jp/mt/mt-tb.cgi/221

コメントする

2008年11月

            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30