edited by
572 views
6 votes
6 votes

A strongly connected component $(\mathrm{SCC})$ of a directed graph $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ is a maximal set of vertices such that any two vertices in the set are mutually reachable.

Given a directed graph $G=(V, E)$, it is convenient to represent the connectivity properties of $G$ using an associated directed acyclic graph $G^{\prime}=\left(V^{\prime}, E^{\prime}\right)$, where the vertices in $V^{\prime}$ are the strongly connected components of $G$ and for $S, T \in V^{\prime},(S, T)$ is in $E^{\prime}$ if and only if there exist $u \in S$ and $v \in T$ such that $(u, v) \in E$.

Let $G$ be the graph shown below.

Let the number of vertices & edges in its associated directed acyclic graph $G^{\prime}$ be $A, B$ respectively, then what is $A+B?$

edited by

1 Answer

9 votes
9 votes

Strongly Connected Components Concept: https://www.youtube.com/watch?v=Zf3B76-Rncs 

DAG of strongly connected components: https://www.youtube.com/watch?v=TVv5VzZwvnE 

The strongly connected components are {A}, {B, D, E, H}, {C, F}, {G}, {J}, and the DAG is as follows:

Common Mistakes:

  • Many students forgot the edge between {B, D, E, H} and {C, F}.
  • The DAG of the SCCs is not a multi-edge graph. For example, there should not be two edges between {B, D, E, H} and {G}.
  • A strongly connected component may be a single vertex, yes.
edited by
Answer: