Graph Theory37 sections · 1633 units
Open in Course

Bridge Tree Example

(Condensing a graph)

Graph: 010-1, 121-2, 202-0, 131-3, 343-4, 434-3. 22-edge-connected components: {0,1,2}\{0,1,2\} (cycle) and {3,4}\{3,4\} (cycle). Bridge: 131-3. Bridge tree: node A={0,1,2}A = \{0,1,2\}, node B={3,4}B = \{3,4\}, edge ABA-B. The bridge tree has two nodes connected by one edge.

You can now solve tree problems (like LCA, diameter, paths) on this compressed structure instead of the original graph. This simplifies many algorithms.