home

# Trees

A tree is a connected acyclic graph. Graphs that contain many trees are termed a forest.

A tree with $$n$$ vertices has $$n - 1$$ edges. Between any two nodes, there is exactly one path.

## Node depth vs height

The depth of the node is the number of edges from the root. The height of a node is the number of edges to it’s lowest leaf.

## Types

### Rooted trees

A rooted tree is when one vertex has been designated as the root and every edge is directed away from this root.

### Spanning trees

A spanning tree of a graph $$G$$ is a connected subgraph of $$G$$ which contains all vertices, but no cycles.

### Minimum spanning tree

The spanning tree that can be formed using the minimum sum of edge weights. See Kruskal’s Algorithm and Prim’s Algorithm.

### M-ary tree

$$m$$-ary trees (binary, ternary, et al) are rooted trees where every vertex has $$m$$ or fewer children. An m-ary tree is regular if all internal nodes have exactly $$m$$ children.

At level $$h$$ there are a maximum $$m^h$$ vertices.

## Isomorphism

General isomorphic trees are as the same as graph isomorphism.

Isomorphic rooted trees must have a mapping form the root of one tree to a root of the other. A isomorphic tree may or may not be isomorphic as a rooted tree.