Задача 6. Лекция. Графы. Компоненты сильной связности ≡

Условие

Связность для ориентированных графов

Что означает связность для ориентированного графа? Тут надо быть аккуратным. Несвязный неориентированный граф можно разбить на связные компоненты, не соединенные друг с другом. С ориентированными графами ситуация сложнее. Граф на рис. 1 нельзя разбить на две части, не соединенные друг с другом. Но мы не будем называть этот граф связным, поскольку в нем нет пути из G в B или из F в A. Дадим такое определение:

Вершины u и v ориентированного графа называются связанными (connected), если в нем есть путь из u в v, а также путь из v в u.

Такое отношение на вершинах разбивает все множество вершин на непересекающиеся подмножества связанных вершин, называемые компонентами сильной связности (strongly connected components). Граф на рис. 1 имеет пять таких компонент.

Стянем теперь каждую компоненту сильной связности в отдельную вершину (метавершину) и оставим только ребра между метавершинами (см. рис. 1), удалив дубликаты. Полученный граф называется метаграфом (meta-graph) (также графом компонент или конденсацией) исходного. Он не содержит циклов: если бы несколько компонент образовывали цикл, то вершины этих компонент были бы в исходном графе достижимы друг из друга и вошли бы в одну компоненту.

Свойство 0. Граф конденсации любого ориентированного графа является ациклическим (и может быть топологически упорядочен).

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

Свойство 1. Процедура Explore, вызванная для вершины u, заканчивает работу, когда посещены все вершины, достижимые из u.

Значит, если вызвать Explore для вершины, которая лежит в компоненте-стоке, то мы обойдем как раз все вершины этой компоненты. Например, граф рис. 1 имеет две такие компоненты, и вызов Explore для вершины K обойдет бОльшую из них.

Остается понять, (а) как найти вершину, которая гарантированно лежит в компоненте-стоке, и (б) что делать после нахождения компоненты-стока.

Для начала ответим на первый вопрос. Сначала покажем, как решать симметричную задачу: найти вершину в компоненте-истоке

Свойство 2. Вершина, которой поиск в глубину присваивает максимальное tout-значение, лежит в компоненте-истоке.

Свойство 3. Пусть C и C′ — компоненты сильной связности графа и в графе есть ориентированное ребро из C в C′. Тогда максимальное tout-значение вершин в C больше, чем максимальное tout-значение вершин в C′.

Доказательство. Дождемся момента, когда при поиске в глубину впервые появится вершина v из C или C′. Если v ∈ C, то вызов Explore(v) не завершится, пока не будут обработаны все вершины обеих компонент (по свойству 1). Поэтому tout[v] будет больше, чем у всех вершин из C′. Если же v ∈ C′, то вызов Explore(v) обойдет все вершины C′, но до C дело еще не дойдет — и максимальное tout-значение в C тоже будет больше.

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

Таким образом, мы научились находить компоненту-исток и вершину в ней. Как найти все вершины только данной компоненты? Рассмотрим обращенный граф G^R, получаемый из G изменением направлений всех ребер (см. рис. 2). В G^R будут те же компоненты сильной связности, как и у G (покажите). Также, найденная вершина компоненты-истока G будет вершиной компоненты-стока графа G^R. Тогда вызов Explore из найденной вершины на графе G^R обойдет только вершины компоненты истока графа G.

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

Заметим, что явно удалять вершины не нужно. Достаточно просто обойти вершины в порядке убывания tout и вызвать Explore из каждой непосещённой.

Итак, мы построили следующий алгоритм выделения компонент сильной связности:

1. Запустить обход в глубину графа G, который вернет вершины в порядке убывания tout. Заметим, что для этого достаточно добавлять вершину в массив при выходе Explore из этой вершины.
2. Построить обращенный граф G^R. Запустить процедуру Explore из каждой непосещённой вершины в порядке убывания tout-значений. Каждое множество вершин, достигнутое в результате очередного запуска обхода, и будет очередной компонентой сильной связности.

Данный алгоритм не просто находит все компоненты связности, но и строит ациклический граф конденсации в порядке топологической сортировки компонент.

---