каждой парой вершин
каждой парой вершин i и j. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным. Ориентированный граф сильно связен, если для каждой пары вершин i и j существует по крайней мере один ориентированный путь из i в j и по крайней мере один из j в i. Максимальный связный подграф графа G называется связной компонентой графа G. Максимальный сильно связный подграф называется сильно связной компонентой.
Рассмотрим алгоритм нахождения сильных компонент графа. Идея достаточна проста. Для вышеприведенного примера значение R(1)={1}?{2,5}?{6}?{4}?{7}={1,2,4,5,6,7}, а Q(1)={1} ? {2,5} ?{3}. Пересечение этих множеств дает множество C(1)={1,2,5} вершин графа G, образующих сильную компоненту, которой принадлежит вершина графа с номером 1. Продолжим рассмотрение: R(3)={1,2,3,4,5,6,7}, Q(3)={3} и C(3)={3}; R(4)={4}?{7}?{6}={4,6,7} и Q(4)={4}?{6}?{7}={4,6,7} и С(4)={4,6,7}. Итак, мы нашли сильные компоненты графа G. Граф G*=(V*,E*)
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
