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:
“Your soul ... is a dark forest. But the trees are of a particular species, they are genealogical trees.”
—Marcel Proust (1871–1922)
“Ye say they all have passed away,
That noble race and brave;
That their light canoes have vanished
From off the crested wave;
That, mid the forests where they roamed,
There rings no hunters’ shout;
But their name is on your waters,
Ye may not wash it out.”
—Lydia Huntley Sigourney (1791–1865)