Trees and forests
A tree is a connected graph with no cycles. These are trees:
A forest is a graph with no cycles. It may or may not be connected. So a single tree is a forest, and a forest consists of one or more trees.
Trees are often used for listing possibilities systematically. The tree below shows how a tournament among five teams is organized. The vertices represent the status of teams (playing games, out, bye, champion) at various times; the edges represent the teams.
This tree shows the ways teams A and B could play each other until one wins two games:
Each vertex represents a game, and is labeled with the winner.
Copyright © 1999-2000 SciMathMN