Trees
Explore the fundamental properties of trees in graph theory, including connectedness, cycle absence, and vertex roles such as leaves and internal nodes. Understand rooted trees and familial relationships like parent, child, ancestor, and sibling. Learn about branchings and forests to build a strong foundation in working with graph structures.
We'll cover the following...
Characteristics of a tree
A tree is a connected graph that has no cycles. The graph below is an example of a tree since it’s connected and does not contain a cycle.
Path graphs are also examples of trees. In the context of trees, an isolated vertex (the trivial path) is called the trivial tree.
A vertex in a tree that has degree is called a leaf of that tree. All other vertices having a degree of at least are called internal nodes. For example, the tree shown above has leaves and ...