Компоненты сильной связности
Компоненты сильной связности
Мы только что научились топологически сортировать ациклические графы. А что же делать с циклическими графами? Ведь в них тоже хочется найти какую-то структуру.
Для этого обычно вводят такое понятие как "сильная связность". В ориентированных графах две вершины связаны сильно, если существует путь из одной в другую и наоборот. Проще говоря, они обе лежат на каком-то цикле.
Понятно, что такое отношение транзитивно: если А и B сильно связны, и B и C сильно связны, то A и C тоже сильно связны. Поэтому все вершины распадаются на такие компоненты сильной связности - такое разбиение вершин, что внутри одной компоненты все вершины сильно связаны, а между вершинами разных компонент сильно связности нет.
Самый простой пример сильно-связной компоненты - это цикл. Но это может быть и полный граф, и любое сложное пересечение нескольких циклов.
Часто рассматривают граф самих компонент сильной связности. На картинке выше их шесть, и между ними остаются ребра из изначально графа. Очевидно, что такой граф уже будет ациклическим: иначе компоненты на цикле нужно было бы объединить в одну.