What is a minimal strongly connected component?

Question

I have a problem that states:

Prove true or false: If G= (V, E) is a directed graph, then the first vertex that becomes black when applying the DFS algorithm on G, belongs to a minimal strongly connected component.

I looked it up on Google (obviously), but could not find any information on a "minimal strongly connected component". I am not sure what the question is asking. Any help?

Thank you

Answer 1

I hope it can help you
Given a graph $G = (V,E)$, a set of vertices $S ⊆ V$ is said to be strongly connected if for any $v_1, v_2 ∈ S$, the graph contains a path through $S$ from $v_1$ to $v_2$.
A loop of a graph is a non-empty, strongly connected set of vertices.

A strongly connected component of G = (V, E) is a maximal subgraph $G′ = (V ′, E′)$ of $G$ such that $V ′$ is strongly connected.

• By $SCC_G$ we denote the set $\{V ′ | G′ = (V ′, E′)$ is a strongly connected component of G$\}$.

We define the $SCC$-partition of $G$, denoted $SCC^+_G$, as the set $SCC_G ∪ \{\{v\}|v\in G $ and $v$ does not occur in a loop of G$\} $. Observe that $SCC^+_G$ indeed forms a partition of $V$ .

We define a relation $≼_G$ on the $SCC$-partition of $G$: for $S_1,S_2 ∈ SCC^+_G$, $S_1 ≼_G S_2$ if for some $v_1 ∈S_1,v_2 ∈S_2$,there is a path in $G$ from $v_2$ to $v_1$, or if $S_1 =S_2 =\{v\}$,where $v$ does not occur in a loop of G.
Note that $≼_G$ is now also defined on the strongly connected components of G, since $SCC_G ⊆ SCC^+_G$.

minimal strongly connected component of $G$: this is a component $G′ = (V′,E′)$ such that there is no $V′′ ∈ SCC_G$ with $V′′ \ne V′$ and $V′′ ≼_G V′$. Note that in general there may be several such minimal components.

---

MODEL GENERATION FOR ID-LOGIC [Prof. Dr. M. DENECKER] Page [$50$], $4.2.3$ Some graph concepts