На основе множественного подхода

Определим вначале понятие «сильно связный граф». Ориентированный граф называется сильно связным, если для любых двух различных вершин x_i и x_j cуществует, по крайней мере, один путь, соединяющий x_i и x_j. Это определение означает также, что любые две вершины такого графа взаимно достижимы.

На основании введенного понятия сильная компонента (СК) графа может быть определена как максимальный (содержащий наибольшее число вершин) сильно связный подграф исходного графа. Поскольку в сильно связном графе произвольная вершина x_j достижима из любой другой вершины x_i, то в ориентированном графе существует одна и только одна СК, содержащая данную вершину x_i.

Таким образом, в СК каждую вершину x_i можно считать одновременно начальной и конечной вершиной пути, определяющего цикл, содержащий x_i. Естественно, что в СК должны оставаться только существенные вершины некоторого цикла, содержащего x_i. Такое множество существенных вершин определяется пересечением RM(x_i) Ç Ç QM(x_i) и задает сильную компоненту, содержащую вершину x_i. Если эти вершины удалить из графа G = (X,Г), то в оставшемся подграфе можно таким же способом выделить новую СК, содержащую x_j Î X – RM(x_i) Ç Ç QM(x_i). Эту процедуру можно повторять до тех пор, пока все вершины графа G не будут сгруппированы в соответствующие СК. После завершения этой процедуры граф G будет разбит на свои сильные компоненты, а граф G^*, отображающий с помощью дуг связь между собой сильных компонент, называют конденсацией графа G.

Подчеркнем, что конденсация G^* не может содержать циклов, поскольку наличие цикла означает, что любые вершины этого цикла взаимно достижимы, а поэтому совокупность всех вершин цикла может принадлежать лишь некоторой СК в G^*.

Определение сильных компонент графа

На основе матричных представлений графа

Процедуру, связанную с нахождением СК графа, можно сделать более удобной, если непосредственно использовать матрицы достижимостей R и обратных достижимостей Q. Определим скоттово (адамарово) произведение (п.1.5.6) R O Q. В полученной матрице R O Q строка x_i содержит единицы только в тех столбцах x_j, для которых выполняется условие: вершины x_i и x_j взаимно достижимы; в других местах строки x_i стоят нули. После определения СК, содержащей вершину x_i, из матрицы R O Q удаляются строки и столбцы, соответствующие вершине СК. Описанную процедуру удаления повторяют каждый раз после определения новой СК.