Skip to content

Files

Latest commit

f966ef5 · May 21, 2018

History

History

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
May 12, 2018
May 21, 2018
May 12, 2018

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