Trees

Definition 3.1

• acyclic: if there are no cycles or circuits in the graph.
• tree: acyclic and connected.
• forest: acyclic graph.
• leaf: vertex with degree 1.

Spanning Trees

Definition 3.2

A spanning tree is a spanning subgraph that is also a tree.

Definition 3.3

• Given a weighted graph \(G=(V,E,w)\), \(T\) is a minimum spanning tree, or MST, of $G if it is a spanning tree with least total weight.

Kruskal's Algorithm

• Just sort all weighted edges and pick the one with least weight until the graph connected and without any cycle.

Prim's Algorithm

• Randomly pick a root. Add the least weight edge that incident to root. Then find the least weight edge among all edge that incident to the endpoint of \(T\) until \(T\) cotain all vertex and connected.

Tree Properties

Theorem 3.4

Every tree with at least two vertices has a leaf.

Theorem 3.6

A tree with \(n\) vertices has \(n-1\) edges \(\forall n\ge 1\).

Theorem 3.11

Let \(T\) be a graph with \(n\) vertices.
\(T\) is a tree.
\(\iff\) \(T\) is acyclic and contain \(n-1\) edges.
\(\iff\) \(T\) is connected and contain \(n-1\) edges.
\(\iff\) There is a unique path between every pair of distinct vertice in \(T\).
\(\iff\) \(T\) is acyclic and for any edge \(e\) from \(T\), \(T+e\) contains exactly one cycle.

Tree Enumeration

Definition 3.13

Given a tree \(T\) on \(n \gt 2\) vertices(labeld 1,2,...,n), the Prufer sequence of \(T\) is a sequence \((s_{1},s_{2},...,s_{n-2})\) of length \(n-2\) defined as follows: - Let \(l_{1}\) be the leaf of \(T\) with the smallest label. - Define \(T_{1}\) to be \(T-l_{1}\). - For each \(i\ge 1\), define \(T_{i+1}=T_{i}-l_{i+1}\), where \(l_{i+1}\) is the leaf with the smallest label of \(T_{i}\). - Define \(s_{i}\) to be the neighbor of \(l_{i}\).