1
$\begingroup$

Suppose we have the following graph: A->B

Surely {A,B} is not a strongly connected component because A is not reachable from B. But my question is what are the strongly connected components of this graph?

Is it NULL/{}/None or {A} and {B}?

I think the strongly connected components should be {A} and {B} (because of this algorithm and this answer here for undirected graph: Singleton graph/single node is connected). But I am confused because of two reasons: one this is a directed graph, and two there no self loop on either A or B, so I am confused whether A/B is reachable by A/B. Can someone clarify this? Thanks in advance.

$\endgroup$
3
$\begingroup$

For a strongly connected graph (or component), we desire for any vertices $x,y$ in the graph (component) there exists a directed path from $x$ to $y$.

Remember that a directed path from $v_0$ to $v_k$ is a subgraph $P=(V,E)$ where $V=\{v_0,v_1,v_2,\dots,v_k\}$ and $E=\{v_0v_1,v_1v_2,v_2v_3,\dots,v_{k-1}v_k\}$ and each $v_i$ is distinct. (Here, the notation $v_1v_2$ refers to the directed edge from $v_1$ to $v_2$).

Note that $(\{a\},\emptyset)$ is a perfectly valid path of length zero with both endpoints $a$. Your misconception seems to come with the idea that a path must have length at least one but that is not the case. As there does not exist a directed path from $B$ to $A$ and since singleton vertices count as strongly connected under this definition, your graph does indeed decompose into the two strongly connected components $\{a\}$ and $\{b\}$.

$\endgroup$
3
$\begingroup$

You are correct in thinking that the strongly connected components are the singletons $\{A\}$ and $\{B\}.$ If this were not the case, strong connectivity would not be an equivalence relation and the strongly connected components would not form a partition of the graph's vertices. This is discussed here under the "Definition" heading.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.