Skip to content

Files

Latest commit

63f5a27 · Jul 26, 2020

History

History

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