Definition:Bridge (Graph Theory)
Jump to navigation
Jump to search
Definition
Let $G = \struct {V, E}$ be a connected graph.
Let $e \in E$ be an edge of $G$ such that the edge deletion $G - e$ is disconnected.
Then $e$ is known as a bridge of $G$.
Example
In the graph below, $CD$ is a bridge.
The graph would be separated into the two components $ABC$ and $DEF$.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 2.4$: Cut-Vertices and Bridges