Trees and Forests
A graph with nodes can contain at most bridges, since adding additional edges must create a cycle. The graphs with exactly bridges are exactly the trees, and the graphs in which every edge is a bridge are exactly the forests.
In every undirected graph, there is an equivalence relation on the vertices according to which two vertices are related to each other whenever there are two edge-disjoint paths connecting them. (Every vertex is related to itself via two length-zero paths, which are identical but nevertheless edge-disjoint.) The equivalence classes of this relation are called 2-edge-connected components, and the bridges of the graph are exactly the edges whose endpoints belong to different components. The bridge-block tree of the graph has a vertex for every nontrivial component and an edge for every bridge.
Read more about this topic: Bridge (graph Theory)
Famous quotes containing the words trees and/or forests:
“At twelve, the disintegration of afternoon
Began, the return to phantomerei, if not
To phantoms. Till then, it had been the other way:
One imagined the violet trees but the trees stood green,
At twelve, as green as ever they would be.
The sky was blue beyond the vaultiest phrase.”
—Wallace Stevens (1879–1955)
“The creation of a thousand forests is in one acorn, and Egypt, Greece, Rome, Gaul, Britain, America, lie folded in the first man.”
—Ralph Waldo Emerson (1803–1882)