Question 9775 – Sequential-Circuits
December 6, 2023Question 13006 – Data-Structures
December 6, 2023Question 1121 – Nielit Scientist-B CS 22-07-2017
Consider the following graph L and find the bridges, if any.
Correct Answer: B
Question 11 Explanation:
A bridge, ut-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.
If we remove {d,e} edge then there is no way to reach e and the graph is disconnected.
The removal of edges {c,d} and {c,f} makes graph disconnect but this forms a cycle.
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.
If we remove {d,e} edge then there is no way to reach e and the graph is disconnected.
The removal of edges {c,d} and {c,f} makes graph disconnect but this forms a cycle.
No bridges
{d,e}
{c,d}
{c,d} and {c,f}
Subscribe
Login
0 Comments