[Math] Is single node in directed graph a strongly connected component

connectednessgraph theory

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.

Best Answer

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\}$.