The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
124 views

i didn't read the concept related to strongly connected components please it describe it for this question

in Graph Theory by Loyal (5.5k points)
edited by | 124 views
0
consider a graph with 3 vertices, A, B, and C. Having directed edges as A-B and B-C. strongly connected components in a graph are three (A, B and C) Adding C-A edge will give us 1 strongly connected component (A-B-C)so statement 1 is FALSE. Not getting counterexample for statement 2 So I think B is the correct choice.
0
b ??
0
why not C ??

they mention "atmost 1 "
0

the number of strongly connected component decreases right ??

+1
@magma

lets consider a example A to B ,B to C in this graph there are total 3 strongly connected component so when we add a edge C to A than it become only 1 strongly connected component            means reduce by 2

so  B is answer
0
yup correct thanks
0

Gurdeep Saini

can you please post the diagram here ??

+1

reduce from 3 to 1

+1
yeah great
0

@gurdeep what about 2 statement its answer is given as d) their explanation

but i think they have taken wrong graph becuase in the given graph there should be three SCC and after adding an edge there will be 2 SCC please correct me if i am wrong

 

0

4 SCC

0
and after adding edge SCC become 2
0
i think option (d) is correct counter example for statement (2) is consider the graph ABCD where path can be given as

$A\rightarrow B ,B\rightarrow C, C\rightarrow D ,A\rightarrow D$ now here there is zero strongly connected component but when we add an edge $C\rightarrow A$ there will be one strongly connected component i.e ABC.

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,339 questions
55,765 answers
192,355 comments
90,815 users