Разработка компиляторов
Сильно связный подграф
увеличить изображение
Сильно связный подграф - это фрагмент, состоящий из взаимно достижимых вершин. Компонента сильной связности - это максимальный сильно связный подграф.
Очевидно, произвольная вершина является сильно связным подграфом. Кроме того, легко показать, что множество компонент сильной связности задает разбиение множества вершин. Это разбиение показано на слайде.
Наконец, множества входных и начальных вершин для компонент сильной связности совпадают.
Как было показано в лекции 11, выделение сильно связных подграфов имеет определяющее значение для реализации чистки циклов.
