Tree

Tree

A (free) tree T is a simple graph such that for every pair of vertices v and w there is a unique path from v to w.

A rooted tree is a tree where one of its vertices is designated the root.

Isomorphic rooted trees

Let T1 be a rooted tree with root r1 and let T2 be a rooted tree with root r2. 

The rooted trees T1 and T2 are isomorphic if there is a one-to-one, onto function f from the vertex set of T1 to the vertex set of T2 satisfying the following:

(a) (vi, vj) ∈ T1 if and only if (f(vi), f(vj)) ∈ T2.

(b) f(r1) = r2.

Level & height

The level of a vertex v is the length of the simple path from the root to v.

The height of a rooted tree is the maximum level number of its vertices.

Terminology

Let T be a tree with root v0. Suppose that x, y and z are vertices in T and that (v0, v1, ..., vn) is a simple path in T, then

(a) the parent of v(n) is v(n-1).

(c) a child of v(n-1) is vn.

(b) ancestors of v(n) are v0, ..., v(n-1).

(d) descendants of v(n-2) are v(n-1), vn.

(e) x and y are siblings if x and y are children of z.

(f) a terminal vertex (or a leaf) is a vertex that has no children.

(g) an internal (or branch) vertex is a vertex that has at least one child. 

(h) a subtree T' of a tree T is a graph where

V(T') = { v0 and the descendants of v0 }

E(T') = { e | e is an edge on a simple path from v0 to some vertex in V(T') }

Theorem

Let T be a graph with n vertices. The following are equivalent.

(a) T is a tree.

(b) T is connected and acyclic.

(c) T is connected and has n-1 edges. //vertex들을 연결할 수 있는 최소한의 구조

(d) T is acyclic and has n-1 edges.