TreesTheoremsRooted trees-ary treesCounting verticesTheoremsSpanning trees of undirected graphsTheoremsPrim's algorithm

Trees

A tree is a connected simple undirected graph with no simple circuits.

A forest is a (not necessarily connected) simple undirected graph with no simple circuits.

Theorems


A graph is a tree iff there is a unique simple path between any two vertices of .


Every tree, with , has at least two vertices that have degree 1.


Every tree with vertices has exactly edges.

Rooted trees

A rooted tree is a pair where is a tree, and is a chosen root vertex of the tree. Often, the edges of a rooted tree are viewed as being directed:

For each node the parent is the unique vertex such that . is then called a child of . Two vertices with the same parent are called siblings.

A leaf is a vertex with no children. Non-leaves are called internal vertices. In the example above, are leaves.

The height of a rooted tree is the length of the longest directed path from the root to any leaf. In the example above, the height of the graph is .

The ancestors of a vertex are all vertices such that there is a directed path from to . In the example above, the ancestors of are and .

The descendants of a vertex are all vertices such that there is a directed path from to . In the example above, the descendants of are every other vertex in the graph.

The subtree rooted at , is the subgraph containing and all its descendants, and all directed edges between them.

-ary trees

For , a rooted tree is called a -ary tree if every internal node has at most children.

It is called a full -ary tree if every internal node has exactly children.

An -ary tree with is called a binary tree.

are full binary, 3-ary and 5-ary trees (respectively). is a non-full 3-ary tree, as not every internal node has exactly 3 children.

Note that the root node is considered an internal node.

Counting vertices

Theorems

, every full -ary tree with internal vertices has exactly vertices.

Proof: Every vertex other than the root is a child of an internal vertex. There are thus such children, plus root.


a full -ary tree with:

  1. vertices has internal vertices and leaves.
  2. internal vertices has vertices and leaves.
  3. If , then if the -ary tree has leaves then it has vertices and internal vertices.

Proof: All of these can be derived from and .


There are at most leaves in an -ary tree of height .

Proof: By induction on .


If an -ary tree has leaves, and is its height, then .

Proof: Since , we have . But , so .

Spanning trees of undirected graphs

For a simple undirected graph , a spanning tree of is a subgraph of such that is a tree and contains every vertex of .

The blue heavy edges in this grid graph represent a spanning tree.

Theorems

Every connected graph has a spanning tree.

Proof: While there is a circuit in , remove one edge of the circuit. Repeat until there are no more circuits. Removing one edge of the circuit does not change connoectivity, and eventually no circuits can remain (because there are finitely many edges to be removed). So the end result is a tree which is a subtree of .

Prim's algorithm

Prim's algorithm finds a minimum spanning tree for a weighted undirected graph. This means it find a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

Hegarty Maths