NIELIT 2017 July Scientist B (CS) - Section B: 11

Question

Consider the following graph $L$ and find the bridges,if any.

• A. No bridge
• B. $\{d,e\}$
• C. $\{c,d\}$
• D. $\{c,d\}$ and $\{c,f\}$

Answer 1

Bridge (or Cut edge): an edge whose removal produces a graph with more connected component than in the original graph.

In the above given graph only {d,e} is a bridge since its removal produces 2 components.

Answer 2

An edge is bridge iff its removal disconnects the graph (or increases the number of disconnected components, if its already disconnected).

Bridge cannot be part of a cycle. So only candidate of bridge is de. (rest all part of cycle). Removal of de disconnects the graph so it is a bridge.

So B is correct.

Answer 3

Opton B) is correct

Removing edge $\{{d,e}\}$ makes graph disconnected, Hence it is the bridge

 

Answer 4

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.

Comments

Equivalently, an edge is a bridge if and only if it is not contained in any cycle.