Skip to content

Files

Latest commit

63f5a27 · Jul 26, 2020

History

History
This branch is 1 commit ahead of trekhleb/javascript-algorithms:master.

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
May 12, 2018
May 21, 2018
Jul 26, 2020

Bridges in Graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases its number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

Bridges in graph

A graph with 16 vertices and 6 bridges (highlighted in red)

Bridgeless

An undirected connected graph with no cut edges

Bridges in graph

Bridges in graph

Bridges in graph

References