Bridge (graph theory)
In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.
Bridge (graph theory) - Wikipedia Jump to content From Wikipedia, the free encyclopedia Edge whose deletion would disconnect a graph A graph with 16 vertices and six bridges (highlighted in red) An undirected connected graph with no bridge edges In graph theory , a bridge , isthmus , cut-edge , or cut arc is an edge of a graph whose deletion increases the graph's number of connected components . [ 1 ] Equivalently, an edge is a bridge if and only if it is not contained in any cycle . For a connected graph, a bridge can uniquely determine a cut . A graph is said to be bridgeless or isthmus-free
related reading
- Spanning tree - Wikipediaen.wikipedia.org
- Graph cheatsheet for coding interviews | Tech Interview Handbooktechinterviewhandbook.org
- Matroiden.wikipedia.org
- Breadth-first search - Wikipediaen.wikipedia.org
- Vertex connectivity - Wikipediaen.wikipedia.org
- Multigraph - Wikipediaen.wikipedia.org
- GraphTheoreticProperties.pdfcs.rice.edu
- Brunnian link - Wikipediaen.wikipedia.org
- Minimum spanning tree - Wikipediaen.wikipedia.org
- Complete graph - Wikipediaen.wikipedia.org
- Matchstick graph - Wikipediaen.wikipedia.org
- Eulerian path - Wikipediaen.wikipedia.org