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:
“The very dew seemed to hang upon the trees later into the day than usual, as on the sides of mountains.”
—Henry David Thoreau (1817–1862)
“What forests of laurel we bring, and the tears of mankind, to those who stood firm against the opinion of their contemporaries!”
—Ralph Waldo Emerson (1803–1882)