Mock DFS Q

Question

Consider DFS over undirected graph with 4 vertices <A;B;C;D>. The discovery and finishing times of them in the order A to D are given. Select the option from following showing more than one connected components:
1) <(1,6), (2,5), (3,4), (8,10)>
2) <(6,7), (2,5), (3,4), (8,9)>
3) <(4,5), (2,8), (1,7), (3,6)>
4) <(7,8), (1,2), (5,6), (3,4)>

Comments

1,2,4 all have more than one connected component

---

only case of 3 graph is connected   so only one connected component   1/8,2/7,3/6,4/5.

---

please explain

Answer 1

In this question the given information is:

1. Graph is connected

2. There are 4 vertices  of the graph

3. The DFS algorithm is performed on the given graph, starting from P to S (in this order only)

Now, we need to find the correct option of the DFS traversal, in terms of discovery and finish time. As it is said that graph is connected, this states that from 4 options, 3 DFS traversals will be for not-connected graph.

Call DFS for each option according to there start and Finish time.(<U,V> meaning U is starting time and V is finish time  of vertex)

1)  <(1,6) (2,5) (3,4) (8,10)>:  This option having 2 connected    component as 1/6,2/5,3/4 and 8/10 so not connected graph

2)   <(6,7) (2,5) (3,4) (8,9)>: In this graph having 3 connected component like (2/5,3/4) as one component,(6/7) is second and (8/9) is third component so it also not connected graph.

3)  <(4,5) (2,8) (1,7) (3,6)>: In this graph is connected as having single connected component as 1/8,2/7,3/6,4/5.

4) <(7,8) (1,2) (5,6) (3,4)> : graph having 4 connected component as (1/2),(3/4),(5/6),(7/8).

Only 3rd option is for connected component graph, 1,2,4 are non-connected components.