Bridges and Cut Vertices

1. Bridges and Cut Vertices

BRIDGES AND CUT VERTICES
Lyzhin Ivan, 2016

2. Definitions

• Bridge – an edge of a graph whose deletion
increases the number of connected
components.
• Cut vertex – a vertex whose deletion
increases the number of connected
components.

3. Example - Bridges

4. Example – Cut Vertices

5. Definitions for Depth-First-Search in undirected graph

• Tree edge –
edge to unvisited vertex.
• Back edge –
edge to visited vertex.
• Parent edge –
edge to parent vertex.

6. Algorithm - Bridges

• Start DFS from unvisited vertex.
•