- Leaf: a vertex of degree 1.
- Tree-graphic: a sequence is said to be tree-graphic if it is a permutation of the degree sequence of a tree.
Every tree with at least 1 edge hase at least 2 leaves.
If the degree of every vertex of a graph is at least 2, then that graph must contain a cycle.
Every tree on n vertices contains exactly n - 1 edges.
A forest G on n vertices has n - 1 - c(G) edges
Any graph G on n vertices has at least n - c(G) egdes
If G is a simple graph with n vertices and k components, then: |EG| <= (n-k)(n-k+1)/2
A simple n-vertex graph with more than (n-1)(n-2)/2 edges must be connected
Let T be a graph with n vertices. Then the following statements are equivalent.
- T is a tree
- T contains no cycle and has n - 1 edges
- T is connected and has n - 1 edges
- T is connected, and every edge is a cut-edge
- Any two vertices of T are connected by exactly one path
- T contains no cycles, and for any new edges e, the graph T + e has exactly one cycle
Let T be a tree with at least 3 vertices. If v is a leaf of T and w is its neightbor, then ecc(v) = ecc(w) + 1. If v is a central vertex of T, then deg(v) >= 2.
Let v and w be two vertices in a tree T such that w is of maximum distance from v (i.e. ecc(v) = d(v, w)). Then w is a leaf
T' be a subtree of T by deleting all its leaves, ecc(v') = ecc(v) - 1 for all vertex v
T' be a subtree of T by deleting all its leaves, Z(T') = Z(T)
The center Z(T) of a tree T is either a single vertex or a single edge
A sequence <d1, d2, ...dn> of n >=2 positive integers is tree-graphic <=> sum of the sequence = 2n - 2
*Let T be any tree on n vertices, and let G be a simple graph such that the minimum degree of the vertices of the graph G >= n - 1 => T is a subgraph of G
- Directed Tree: a directed graph whose underlying graph is a tree.
- Rooted Tree: a tree with a designated vertex called the root.
- Shortest-path Tree for G from v: is a rooted tree T with vertex-set VG and root v such that the unique path in T from v to each vertex w is a shortest path in G from v to w.
- Depth (or Level): the root has depth 0.
- Height: greatest depth of a tree.
- Child, Sibling, Descendant, Ancestor, Leaf, Internal Vertex
- m-Ary Tree: a rooted tree in which every vertex has m or fewer children.
- Complete m-Ary Tree: a rooted tree in which every vertex has m children.
- Isomorphic as Rooted Trees: exists an isomorphism that maps root to root.
- Ordered Tree: a rooted tree in which the children of each vertex are assigned a fixed ordering.
- Standard Plane Drawing, Binary Tree, Left Subtree, Right Subtree
A complete m-ary tree has m^k vertices at level k
An m-ary tree has at most m^k vertices at level k
The complete m-ary tree of height t has (m ^ (h + 1) - 1) / (m - 1)
The complete binary tree of height h has 2 ^ (h + 1) - 1 vertices
Every binary tree of height h has at most 2 ^ (h + 1) - 1 vertices
- Binary Code: an assignment of symbols or other meanings to a set of bitstrings. Each bitstring is reaferred to as a codeword.
- Prefix Code: a binary code with the property that no codeword is an inital substring of any other codeword.
- Average Weighted Depth: of the binary tree T, denoted wt(T), is given by a weight wi. is given by
wt(T) = sum depth(s) * w - Huffman Tree, Huffman Code
If the leaves of a binary tree are assigned weights, and if each internal vertex is assigned a weight equal to the sum of its children's weights, then the tree's average weighted depth equals the sum of the weights of its internal vertices.
For a given list of weights w1, w2, ... , wl, a Huffman tree has the smallest possible average weighted depth among all binary trees whose leaves are assigned those weights.
- Left-complete: the bottom level has no gaps as one traverses from left to right.
- Priority Tree: a left-complete binary tree whose vertices have labels (called priorities) from an poset, such that no vertex has higher proirity than its parent.
- Priority Queue: a set of entries, each of which is assigned a priority. When an entry is to be removed, or dequeued, from the queue, an entry with the highest priority is selected.
- Heap: a representation of priority tree as an array, having the following address pattern.
- index root = 0
- index (leftchild v) = 2 * index v + 1
- index (rightchild v) = 2 * index v + 2
- index (parent v) = floor ( index v - 1 / 2 )
- Prüfer sequence: is of length n - 2, for n >= 2 ...
The number of n-vertex labeled trees is n ^ (n - 2) for n >= 2
Let dk be the number of occurrences of number k in a Prüfer encoding sequence for a labeled tree T. Then the degree of vertex k in T equals tp dk + 1.