Definition
A tree is a Graph that contains no cycles. Equivalently, a tree is a connected graph in which any two vertices are connected by exactly one path.
Properties
- A tree with vertices has exactly edges.
- Removing any edge from a tree disconnects it into two components.
- Adding any edge to a tree creates exactly one cycle.
Remarks
Note that the data structure of a tree typically refers to a rooted tree.
Related Concepts
- Rooted Tree: A tree with a designated root vertex.
- Directed Acyclic Graph: A generalization allowing multiple roots.
- Graph: The general structure from which trees are derived.