Информатика · объяснение и практика

Сильные компоненты: какие вершины взаимно достижимы

Компоненты сильной связности ориентированного графа: взаимная достижимость, максимальность группы и ациклический граф сжатия.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

В маршруте Графы, разрезы и динамические запросы · 10 тем

Главная мысль

В компоненте сильной связности любая вершина достижима из любой другой по направлению рёбер. Группа должна быть максимальной: добавить ещё вершину без нарушения этого свойства нельзя. Если сжать каждую такую компоненту в одну вершину, получится ориентированный граф без циклов.

Одного направления недостаточно

Представим сеть разрешённых переходов между учебными состояниями. Если из A можно добраться до B,это ещё не означает возможность вернуться обратно. Сильная связность требует обоих направлений достижимости, причём обратный путь может проходить через другие вершины и не обязан быть одним обратным ребром.

Максимальность группы исключает искусственное дробление. Если несколько вершин уже взаимно достижимы, нельзя объявить каждую произвольную пару отдельной полной компонентой, игнорируя остальных подходящих участников. Компоненты не пересекаются и вместе содержат все вершины, в том числе одиночные, которым не нашлось взаимно достижимых соседей.

Разбираем собственную сеть переходов

Пусть рёбра имеют направления 1→2,2→3,3→1,3→4,4→5,5→4,5→6. Первые три вершины образуют цикл и достижимы друг из друга. Вершины 4 и 5 тоже взаимно достижимы. Из первой тройки можно попасть во вторую пару, но пути обратно в условии нет.

Поэтому группы равны{1,2,3},{4,5}и{6}. Наличие пути из 3 в 4 не объединяет первые две группы. Шестая вершина остаётся отдельной компонентой: возможность прийти к ней не создаёт возможности вернуться. Направления надо проверять по исходным рёбрам, а не по визуальной близости вершин на рисунке.

Пример

Компоненты собственной сети: C₁={1,2,3},C₂={4,5},C₃={6}. После сжатия остаются переходы C₁→C₂→C₃.

Ни один межкомпонентный переход не даёт возвращения назад. Внутренние циклы стали свойством сжатых групп, а не циклом между ними.

Почему между сжатыми группами нет цикла

Допустим, несколько разных сжатых компонент образовали направленный цикл. Тогда из каждой можно было бы пройти в следующую и вернуться обратно через остальные. Вместе с внутренней сильной связностью это сделало бы все их вершины одной взаимно достижимой группой, что противоречит максимальности исходных компонент.

Сжатый граф помогает отделить области взаимных переходов от однонаправленных зависимостей между ними. Его уже можно обрабатывать в топологическом порядке. Но такое сжатие не сохраняет автоматически длины всех путей, веса или количество способов движения внутри группы. Для задачи о стоимости либо числе маршрутов нужны дополнительные сведения, а не только номера компонент.

От чтения к действию

А теперь — вы

Есть рёбра A→B,B→A,B→C,а из C нет выходов. Какие компоненты получаются?

Частые вопросы

Если есть путь A→B,вершины уже в одной компоненте?

Нет. Нужен также путь B→A; один из путей может состоять из нескольких рёбер.

Одиночная вершина может быть компонентой сильной связности?

Да. Если её нельзя объединить с другими по взаимной достижимости, она образует отдельную компоненту.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться