Graph Condensation

Компонентой сильной связности называется такое подмножество вершин $C$, что любые две вершины этого подмножества достижимы друг из друга, т.е. для $\forall u, v \in C$ существует путь из $u$ в $v$ и из $v$ в $u$.

Орграфом конденсации для ориентированного графа $D=(V,X)$ называется ориентированный граф$D_0=(V_0,X_0)$, в котором каждая вершина представляет собой компоненту сильной связности графа $D$, а множество его дуг $X_0$ определяется условием: $x_0=(v_0,w_0) \in X_0$ тогда и только тогда, когда в компонентах сильной связности $v_0$ и $w_0$ существуют вершины $v \in v_0$ и $w \in w_0$, для которых $x=(v,w) \in X$.

Более формально, если $G$ - ориентированный граф, то его граф конденсации $C(G)$ - это ориентированный граф полученный из $G$ путём сжатия всех вершин, принадлежащих одной компоненте сильной связности, в одну вершину. Ребро между двумя вершинами $u$ и $v$ в графе конденсации существует тогда и только тогда, когда в графе $G$ существует хотя бы одно ребро из вершины $u$ в вершину $v$.