Spanning Forests
A spanning forest is a type of subgraph that generalises the concept of a spanning tree. However, there are two definitions in common use. One is that a spanning forest is a subgraph that consists of a spanning tree in each connected component of a graph. (Equivalently, it is a maximal cycle-free subgraph.) This definition is common in computer science and optimization. It is also the definition used when discussing minimum spanning forests, the generalization to disconnected graphs of minimum spanning trees. Another definition, common in graph theory, is that a spanning forest is any subgraph that is both a forest (contains no cycles) and spanning (includes every vertex).
Read more about this topic: Spanning Tree
Famous quotes containing the word forests:
“‘Tis chastity, my brother, chastity.
She that has that is clad in complete steel,
And like a quivered nymph with arrows keen
May trace huge forests and unharbored heaths,
Infamous hills and sandy perilous wilds,
Where, through the sacred rays of chastity,
No savage fierce, bandit, or mountaineer
Will dare to soil her virgin purity.”
—John Milton (1608–1674)